Re: How to find closest point(s) around a specific point in point cloud?
- From: alex <alex@xxxxxxxxxxx>
- Date: Mon, 31 Mar 2008 09:22:49 -0400
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
.
- Follow-Ups:
- References:
- Prev by Date: Re: How to find closest point(s) around a specific point in point cloud?
- Next by Date: Re: How to find closest point(s) around a specific point in point cloud?
- Previous by thread: Re: How to find closest point(s) around a specific point in point cloud?
- Next by thread: Re: How to find closest point(s) around a specific point in point cloud?
- Index(es):
Relevant Pages
|
