CGAL users discussion list

[杨成林 <>]

Why Delaunay triangulation is needed?

2010/5/20, 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 <http://www.cs.umd.edu/%7Emount/ANN/> is a
>> good nearest neighbor searching package, and Zhou has suggested
>> STANN<http://sites.google.com/a/compgeom.com/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
>>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>


-- 
杨成林
Yang Chenglin