CGAL users discussion list

[Panagiotis Foteinos <>]

Thank you for your reply. 

It seems that the best way is to construct the Delaunay triangulation of these two point sets and then ask for the nearest vertex of the first set from any point of the other. An initial spatial reordering of the point sets (before they are inserted into the Delaunay triangulation) will speed up things. Also, different queries do not change the underlying Delaunay structure (this is not the case for the K-neighbor search).

Regards,
Panagiotis Foteinos

On Wed, May 19, 2010 at 9:21 AM, 杨成林 <> wrote:

The spatial searching package in CGAL is not very efficient, though I have not test the new version. ANN is a good nearest neighbor searching package, and Zhou has suggested STANN. To compute Hausdorff distance, if you implement the search algorithm yourself, you can terminate the search early to save time. Let d be the current hausdorff distance, then if the search process get distance less than d, the search can be terminated.

2010/5/19 Panagiotis Foteinos <>

Hello yall.

I would like to compute the Hausdorff distance of two 3D point sets. I am thinking of using the K nearest neighbor algorithm of CGAL with K equal to 1 for each point on the first set and for each point on the second set (two-sided Hausdorff distance).

Each point set is expected to contain no more than 100,000 points.

Has anyone benchmarked the K nearest neighbor package? Is it reasonably fast? Any comments would be appreciated.


Best Regards,
Panagiotis Foteinos

--
杨成林
Yang Chenglin