CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Philippe GAMBRON wrote:
> Hi Sébastien,
>
> Thank you very much for your quick reply.
>
>
> > For your first question using k-nearest neighbor search with k=1 will 
> > make it (insert your points in the tree and make the query with your
> > point). See example here:
> > http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching/Chapter
> > _main.html#Subsection_59.3.1
>
> This is what I was looking for.
>
>
> > For the second one, a naive method is to use the first method 
> > iteratively over all the points of one set and take the pair with
> > smallest distance. If you have performance issues, probably filtering
> > points with bbox should be more efficient.
One idea is to use one kd-tree for each point set and to compare 
distances between bboxes (since it is bounding the distance between 
points contained).

The walk on nodes of a kd-tree is an advanced feature.

Doc of the tree (use root() method to get the first node):
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching_ref/Class_Kd_tree.html#Cross_link_anchor_1622
Doc of the node class:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching_ref/Class_Kd_tree_node.html#Cross_link_anchor_1623

S.

> I will explore that because I have indeed performance issues.
>
> Thank you!
>
> Best regards,
>
> Philippe