CGAL users discussion list

["Fei (Sophie) Che" <>]

Actually, CGAL does have 3D voronoi by calling dual() from a 3D delaunay triangulation...

You may want to use the point location in delaunay and here is its running time analysis:

http://www.cgal.org/Manual/last/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Subsection_37.6.1

Best,

~Sophie

On May 20, 2010, at 1:23 AM, Panagiotis Foteinos wrote:

It gives you the nearest neighbor of a point in almost constant time. Like the (dual) Voronoi diagram. 3D Voronoi is not implemented in CGAL though.

Actually, the Hausdorff distance calculated in this way took less than 3 secs for a set of 90,000 points and a set for 150,000 points.
 
Regards,
Panagiotis

2010/5/20 杨成林 <>

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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss