Re: How to find closest point(s) around a specific point in point cloud?

On Mar 31, 8:22 am, alex <a...@xxxxxxxxxxx> wrote:
Robert Karlsson wrote:
I can't find any site with information about the simplest way to
locate the n number of closest points adjacent to a point in a 3d
point cloud with scattered data.

Basically, I've got an array, call it V, with a couple of hundred
positions [x,y,z] and a value (eg [0-100).

Let's say I wanted to pick the 5 closest points around a specific
point, call it P, with a value like [x,y,z] = [10,20,30]

In general, if you have an array and do not know about distribution
of points, you cannot do better than linear time: even if you look
for one closest point to P you have to look at all points at least
once or the one you miss just might be the closest. If you need
k closest, just keep k closest points found so far as you scan
through the array.

If you need to do this multiple times for different P's there are
algorithms to significantly speed things up by preprocessing the
arrays. Search geometric computational algorithms for details.
I am curious, why/if you care about performance for ~200 point data
sets (unless this is a homework problem).

--
Alex

Wait. Why suggest a linear search of the entire array?

what's wrong with this pseudocode algorithm?
Given point (P,Q,R)

number of points found = 0
current distance = 0
while number of points found < 10
{
searcharray=find all points in shell between current distance and
current distance + 1
for each in searcharray
if conditition met,
then
add to result array
increment number of points found
exit for loop if number of points found >= 10
endif
}

That should find things faster. Defining the "find all points in
shell" function can be tricky since the array in rectilinear but the
shell is circular. some points are not exactly integer distances away.
But it could just return a sorted array so the for loop can find the
right ones and stop without scanning the whole list.

Note: I left it as "condition met" since that OP did not really say
what the condition was. (must the value at the point be >0? >10? >50?)
Ed
.

Relevant Pages

  • Re: lookup tables
    ... Roger Govier ... array is descending at first and then begins to rise. ... Bernard V Liengme ... the closest value is 18. ...
    (microsoft.public.excel)
  • Re: lookup tables
    ... Lots of blushes - I didn't press CSE when I switched from -1 to 0!!!!! ... the ABSof the difference between the test and the array ... Bernard V Liengme ... the closest value is 18. ...
    (microsoft.public.excel)
  • Re: How to find closest point(s) around a specific point in point cloud?
    ... point cloud with scattered data. ... Let's say I wanted to pick the 5 closest points around a specific ... if you have an array and do not know about distribution ... current distance = 0 ...
    (comp.programming)
  • Re: RegExp array problem
    ... > tried to add the RegExp into there hasn't worked as yet. ... var filteredArray = new Array; ... That is, however, not the closest matches, it is returning the items with ...
    (comp.lang.javascript)
  • Re: How to find closest point(s) around a specific point in point cloud?
    ... point cloud with scattered data. ... Basically, I've got an array, call it V, with a couple of hundred ... Let's say I wanted to pick the 5 closest points around a specific ... The best thing I can think of is to use a voxel bounding box ...
    (comp.programming)