nearest neighbor in 2D
G.J.Giezeman
geert at cs.uu.nl
Tue Nov 4 09:32:38 CET 2003
Isaac To wrote:
>>>>>>"John" == John Hunter <jdhunter at ace.bsd.uchicago.edu> writes:
>
>
> John> Given a new point x,y, I would like to find the point in the list
> John> closest to x,y. I have to do this a lot, in an inner loop, and
> John> then I add each new point x,y to the list. I know the range of x
> John> and y in advance.
>
> John> One solution that comes to mind is to partition to space into
> John> quadrants and store the elements by quadrant. When a new element
> John> comes in, identify it's quadrant and only search the appropriate
> John> quadrant for nearest neighbor. This could be done recursively, a
> John> 2D binary search of sorts....
>
> By recursion your solution would work in O(log n) time. The construction
> would take O(n log n) time. Unluckily, it can return the wrong point, as
> the nearest point within the nearest quadrant might not be the nearest
> point.
>
> The problem is a well-studied basic computational geometry problem, although
> I don't really know any Python code that actually do it. Try to look at the
> web for "Voronoi diagrams" and "radial triangulation" to understand how to
> solve it properly in the above mentioned (perhaps randomized) time
> complexity.
>
> Regards,
> Isaac.
A solution in C++ is using the CGAL-library (www.cgal.org). Look in the
index of the basic library and search for 'nearest'. It will point you
to Delaunay triangulations, which, together with a triangulation
hierarchy, will give O(log n) time complexity, except in pathological
cases. You can call C++ code from python.
B.t.w., there will be a new release of the CGAL library very soon
(probably this week).
More information about the Python-list
mailing list