CGAL users discussion list

[Jintack Lim <>]

Thanks Sebastien.

I know code is not so elegant,

however the concept can be adapted!

Here's the profiling result using valgrind.

You can check how much cycles are consumed by aforementioned functions.

For the same spatial query, improved version only takes around 40% of cycles.

Before optimization

After optimization

Looking forward to hearing from you :)

Jintack

On Mon, Aug 4, 2014 at 1:48 AM, Sebastien Loriot (GeometryFactory) <> wrote:

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

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