On 3/31/2011 12:33 PM, Trevor G Quayle wrote:
> stbenge<"egnebts<-inverted"@hotmail.com>  wrote:
>>
>> I'm trying to find an efficient way to test all points within a set
>> against each other.
>
> When you say testing points against each other, what exactly are you trying to
> do?  Find equal points?
>

Basically I want to find close neighbors. They don't even have to be the 
nearest ones for what I'm doing.

One case would involve placing spheres in 3D space without having any 
one sphere intersect another. I *could* simply reference all the points 
every time a point is added, but the parse time is compounded as new 
points are introduced.

In another case I would have a number of points generated from a mesh. 
For each point there would be a blob, and each blob would be subtracted 
by blob components based on close points.

For the second scenario I might take up Christian Froeschlin's idea of 
sorting everything along one direction and then just testing the array 
in a padded fashion. That would probably be the easiest implementation, 
but for higher-density point sets and blobs with large radii, it might 
not be very efficient.

Directional sorting has got to be better than what I'm doing now, though...

Sam

Post a reply to this message