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

Ed Prochak wrote:
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).

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
}

I do not understand the "find all points between D and D+1" part.
I am just saying that to find even one closest point you have to
examine *all* points of V, unless V is organized in some special
way, which was not indicated by the OP.

--
Alex
.

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: 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)
  • Re: How to find closest point(s) around a specific point in point cloud?
    ... point cloud with scattered data. ... if you have an array and do not know about distribution ... for one closest point to P you have to look at all points at least ... current distance = 0 ...
    (comp.programming)