Nearest neighbour using voronoi

[hidayat]

Hi everyone,

I implement Shane o Sullivan (http://www.skynet.ie/~sos/mapviewer/voronoi.php) code to generate voronoi diagram from a set of points and store the edges in a .txt file. My question is how to find the nearest point given a random point using this file. Thanks

[ne555]

good morning, the search reduces to find in wich cell your query point lies. However could only find generic point location algorithms.

By instance (Geometric Data Structures for computer Graphics (Zachmann \and Langetepe))

We draw a horizontal line through every vertex of the diagram and sort the lines in O(n log n) time. The lines decompose the diagram into slabs. For every slab we sort the set of crossing edges of the Voronoi diagram in linear time. Altogether we need O(n^2) time for the simple construction.

For a query point x we locate its slab in O(logn) time and afterwards its region in O(logn) time by binary search.

[coder777]

Take a look at boost:

http://www.boost.org/doc/libs/1_59_0/libs/polygon/doc/index.htm

[hidayat]

Hi ne555,

Thanks for the reply. It seems that n^2 is a bit expensive. However do you have/know C++ code sample doing that work. I would really appreciate that. Thanks.

[hidayat]

hi coder777,

I check the link, however I couldn't find what i'm looking for (find the nearest object using voronoi edges file). Would you please help? Thanks