CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Hi Jintack,

thanks a lot for your patches.
We'll have a look soon and post updates here.

Sebastien.

On 08/02/2014 12:26 AM, Jintack Lim wrote:
> Dear all,
>
> while I'm using k nearest neighbor library,
> I found there is some room to optimize this library.
> With this optimization, I saved up to 60% of execution time.
> Source code is available below.
>
> My basic observation is that
> 1) When calculating distance from a query point to a node, the same
> iterators for a query is created over and over. Since query itself is
> not changing, making only one iterator per query will do.
>
> min_distance_to_rectangle function in
> <CGAL-4.4/include/CGAL/Manhattan_distance_iso_box_point.h>
> <CGAL-4.4/include/CGAL/Euclidean_distance.h>
>
> 2) Calculating distance from a query to each of sub rectangle is not
> necessary. What is necessary is to pick a farther rectangle and
> calculate that distance for a branch function.
> To pick a farther rectangle, it is enough to check the query's
> coordinate and rectangle's separator. (Just like a orthogonal kNN does)
>
> compute_neighbors_general function in
> <CGAL-4.4/include/CGAL/K_neighbor_search.h>
>
> 3) creating and deleting kd_tree_rectangle objects takes significant
> time in a query processing. At each node, CGAL makes two sub rectangle
> objects. However, by using a parent's rectangle object, we can save one
> rectangle construction/destruction.
>
> compute_neighbors_general function in
> <CGAL-4.4/include/CGAL/K_neighbor_search.h>
>
> Here's the like to those files.
> https://dl.dropboxusercontent.com/u/30008069/Euclidean_distance.h
> https://dl.dropboxusercontent.com/u/30008069/K_neighbor_search.h
> https://dl.dropboxusercontent.com/u/30008069/Manhattan_distance_iso_box_point.h
>
> Best Regards,
> Jintack