Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Nearest Neighbor Search

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Nearest Neighbor Search


Chronological Thread 
  • From: "Fei (Sophie) Che" <>
  • To:
  • Subject: Re: [cgal-discuss] Nearest Neighbor Search
  • Date: Thu, 20 May 2010 10:13:10 -0400

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:


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






Archive powered by MHonArc 2.6.16.

Top of Page