Using finger search with Delaunay Triangulation Hierarchy

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

Using finger search with Delaunay Triangulation Hierarchy

Manuel Holtgrewe-3
Hi,

I am trying to perform finger search with the delaunay hierarchy code
from CGAL. That is, I have a random point set which is added as the
points of a delaunay hierarchy / triangulation. Then, I have a list of
query points which lie along a line through this point set. I want to
query for the nearest neighbours of the points on the line.

This sequence of queries should offer good locality, i.e. if I know
the nearest neighbour x of point i on the line, the nearest neighbour
y of point i+1 should be very close to x. Thus, I am trying to use the
second parameter to Delaunay_triangulation_2::nearest_vertex(const
Point& p, Face_handle f= Face_handle()) const.

Will the following code do this, i.e. when calling x->face() (where x
is the nearest neighbour of the i-th query point i), will this return
a face adjacent to x and this helps to speed up the queries?

Thanks,
Manuel

// typedefs/aliases
struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};

typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
typedef CGAL::Triangulation_face_base_2<K>                Fb;
typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;

typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
typedef CGAL::Triangulation_hierarchy_2<Dt>
Triangulation_hierarchy;
typedef Triangulation_hierarchy::Vertex_circulator
Vertex_circulator_hierarchy;
typedef Triangulation_hierarchy::Point                    Point_hierarchy;
typedef Triangulation_hierarchy::Vertex                   Vertex_hierarchy;
typedef Triangulation_hierarchy::Vertex_handle
Vertex_hierarchy_handle;
typedef Triangulation_hierarchy::Face_handle
Face_hierarchy_handle;

void foo(const std::vector<Point_hierarchy> &points, const
std::vector<Point_hierarchy> &queries) {
 Triangulation_hierarchy dh;
  dh.insert(points.begin(), points.end());
  Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
  Face_hierarchy_handle f = v->face();
  for (int j = 1, jend = queries.size(); j < jend; ++j) {
    v = dh.nearest_vertex(queries[j], f);
    f = v->face();
  }
}
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Damian Sheehy
Hi Manuel,

Based on visual inspection, your code looks correct. You do not have
to special case the first nearest_vertex search; just pass a default
Face_handle in the first iteration of the loop and start the loop from
zero.

Regards,

Damian

On 4/17/09, Manuel Holtgrewe <[hidden email]> wrote:

> Hi,
>
> I am trying to perform finger search with the delaunay hierarchy code
> from CGAL. That is, I have a random point set which is added as the
> points of a delaunay hierarchy / triangulation. Then, I have a list of
> query points which lie along a line through this point set. I want to
> query for the nearest neighbours of the points on the line.
>
> This sequence of queries should offer good locality, i.e. if I know
> the nearest neighbour x of point i on the line, the nearest neighbour
> y of point i+1 should be very close to x. Thus, I am trying to use the
> second parameter to Delaunay_triangulation_2::nearest_vertex(const
> Point& p, Face_handle f= Face_handle()) const.
>
> Will the following code do this, i.e. when calling x->face() (where x
> is the nearest neighbour of the i-th query point i), will this return
> a face adjacent to x and this helps to speed up the queries?
>
> Thanks,
> Manuel
>
> // typedefs/aliases
> struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
>
> typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
> typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
> typedef CGAL::Triangulation_face_base_2<K>                Fb;
> typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;
>
> typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
> typedef CGAL::Triangulation_hierarchy_2<Dt>
> Triangulation_hierarchy;
> typedef Triangulation_hierarchy::Vertex_circulator
> Vertex_circulator_hierarchy;
> typedef Triangulation_hierarchy::Point                    Point_hierarchy;
> typedef Triangulation_hierarchy::Vertex                   Vertex_hierarchy;
> typedef Triangulation_hierarchy::Vertex_handle
> Vertex_hierarchy_handle;
> typedef Triangulation_hierarchy::Face_handle
> Face_hierarchy_handle;
>
> void foo(const std::vector<Point_hierarchy> &points, const
> std::vector<Point_hierarchy> &queries) {
>  Triangulation_hierarchy dh;
>   dh.insert(points.begin(), points.end());
>   Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
>   Face_hierarchy_handle f = v->face();
>   for (int j = 1, jend = queries.size(); j < jend; ++j) {
>     v = dh.nearest_vertex(queries[j], f);
>     f = v->face();
>   }
> }
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Manuel Holtgrewe-3
Hi Damian,

Thank you for your answer.

I have written a little program with which I am trying to measure the
speedup that the fingers give me. The source code is attached, I
tested it with CGAL 3.4 on a machine with Intel Xeon processors
@2.3Ghz.

I get the following output:

Delaunay Hierarchy:  finger query vs. non-finger query
         n      build  no_finger     finger    speedup
         2   0.000012   0.424343   0.425491   0.997302
         4   0.000018   0.086763   0.086414   1.004036
         8   0.000015   0.100489   0.099627   1.008651
        16   0.000033   0.114695   0.105578   1.086352
        32   0.000066   0.128658   0.123606   1.040871
        64   0.000134   0.135320   0.116303   1.163512
       128   0.000270   0.178627   0.143877   1.241526
       256   0.000539   0.174100   0.122833   1.417371
       512   0.001070   0.168988   0.150091   1.125904
      1024   0.002091   0.173133   0.160160   1.080999
      2048   0.004395   0.185442   0.175380   1.057372
      4096   0.008549   0.207307   0.195271   1.061638
      8192   0.017413   0.216792   0.208223   1.041154
     16384   0.033093   0.246830   0.232705   1.060700
     32768   0.067720   0.198592   0.188638   1.052769
     65536   0.135914   0.207161   0.195284   1.060819
    131072   0.281401   0.243547   0.232596   1.047081
    262144   0.561701   0.254221   0.240915   1.055233
    524288   1.137475   0.238146   0.225836   1.054509
   1048576   2.287607   0.250391   0.238223   1.051078
   2097152   4.772575   0.252274   0.239942   1.051396
   4194304   9.628133   0.282821   0.270887   1.044055
   8388608  19.543273   0.305526   0.292194   1.045627

As you can see, I could only measure very small speedups. I would
expect them to be much bigger. Am I doing something wrong?

-- Manuel



2009/4/17 Damian Sheehy <[hidden email]>:

> Hi Manuel,
>
> Based on visual inspection, your code looks correct. You do not have
> to special case the first nearest_vertex search; just pass a default
> Face_handle in the first iteration of the loop and start the loop from
> zero.
>
> Regards,
>
> Damian
>
> On 4/17/09, Manuel Holtgrewe <[hidden email]> wrote:
>> Hi,
>>
>> I am trying to perform finger search with the delaunay hierarchy code
>> from CGAL. That is, I have a random point set which is added as the
>> points of a delaunay hierarchy / triangulation. Then, I have a list of
>> query points which lie along a line through this point set. I want to
>> query for the nearest neighbours of the points on the line.
>>
>> This sequence of queries should offer good locality, i.e. if I know
>> the nearest neighbour x of point i on the line, the nearest neighbour
>> y of point i+1 should be very close to x. Thus, I am trying to use the
>> second parameter to Delaunay_triangulation_2::nearest_vertex(const
>> Point& p, Face_handle f= Face_handle()) const.
>>
>> Will the following code do this, i.e. when calling x->face() (where x
>> is the nearest neighbour of the i-th query point i), will this return
>> a face adjacent to x and this helps to speed up the queries?
>>
>> Thanks,
>> Manuel
>>
>> // typedefs/aliases
>> struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
>>
>> typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
>> typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
>> typedef CGAL::Triangulation_face_base_2<K>                Fb;
>> typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;
>>
>> typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
>> typedef CGAL::Triangulation_hierarchy_2<Dt>
>> Triangulation_hierarchy;
>> typedef Triangulation_hierarchy::Vertex_circulator
>> Vertex_circulator_hierarchy;
>> typedef Triangulation_hierarchy::Point                    Point_hierarchy;
>> typedef Triangulation_hierarchy::Vertex                   Vertex_hierarchy;
>> typedef Triangulation_hierarchy::Vertex_handle
>> Vertex_hierarchy_handle;
>> typedef Triangulation_hierarchy::Face_handle
>> Face_hierarchy_handle;
>>
>> void foo(const std::vector<Point_hierarchy> &points, const
>> std::vector<Point_hierarchy> &queries) {
>>  Triangulation_hierarchy dh;
>>   dh.insert(points.begin(), points.end());
>>   Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
>>   Face_hierarchy_handle f = v->face();
>>   for (int j = 1, jend = queries.size(); j < jend; ++j) {
>>     v = dh.nearest_vertex(queries[j], f);
>>     f = v->face();
>>   }
>> }
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

test_dh_finger.cpp (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Damian Sheehy
Hi Manuel,
 
The Delaunay hierarchy is very fast search structure in and of itself, particularly if a start hint cannot be provided for each query. The purpose of the search hierarchy is to compute a good start location from which to walk. In your case you already have a very good starting location (Face_handle) for each query point. So why would you expect the search hierarchy to do anything for you? (Take a look at the paper: Google Olivier Devillers Delaunay hierarchy).
 
You are not really leveraging functionality of the search hierarchy, but you are paying the overhead of building and maintaining it. Try your search without the hierarchy, providing the start hint as before. If that's not fast enough consider exploiting the structure of your problem; you know that your query points are distributed along a straight line. CGAL provides a very powerful function called a line walk that allows you to compute the set of triangles intersected by a line segment. It may help to take a close look at that. You may be able to set up an interval list from the line walk and replace your N queries by a single line walk plus a subsequent search for an interval.
 
 
All the best!
 
Damian

 
On Sat, Apr 18, 2009 at 12:16 PM, Manuel Holtgrewe <[hidden email]> wrote:
Hi Damian,

Thank you for your answer.

I have written a little program with which I am trying to measure the
speedup that the fingers give me. The source code is attached, I
tested it with CGAL 3.4 on a machine with Intel Xeon processors
@2.3Ghz.

I get the following output:

Delaunay Hierarchy:  finger query vs. non-finger query
        n      build  no_finger     finger    speedup
        2   0.000012   0.424343   0.425491   0.997302
        4   0.000018   0.086763   0.086414   1.004036
        8   0.000015   0.100489   0.099627   1.008651
       16   0.000033   0.114695   0.105578   1.086352
       32   0.000066   0.128658   0.123606   1.040871
       64   0.000134   0.135320   0.116303   1.163512
      128   0.000270   0.178627   0.143877   1.241526
      256   0.000539   0.174100   0.122833   1.417371
      512   0.001070   0.168988   0.150091   1.125904
     1024   0.002091   0.173133   0.160160   1.080999
     2048   0.004395   0.185442   0.175380   1.057372
     4096   0.008549   0.207307   0.195271   1.061638
     8192   0.017413   0.216792   0.208223   1.041154
    16384   0.033093   0.246830   0.232705   1.060700
    32768   0.067720   0.198592   0.188638   1.052769
    65536   0.135914   0.207161   0.195284   1.060819
   131072   0.281401   0.243547   0.232596   1.047081
   262144   0.561701   0.254221   0.240915   1.055233
   524288   1.137475   0.238146   0.225836   1.054509
  1048576   2.287607   0.250391   0.238223   1.051078
  2097152   4.772575   0.252274   0.239942   1.051396
  4194304   9.628133   0.282821   0.270887   1.044055
  8388608  19.543273   0.305526   0.292194   1.045627

As you can see, I could only measure very small speedups. I would
expect them to be much bigger. Am I doing something wrong?

-- Manuel



2009/4/17 Damian Sheehy <[hidden email]>:
> Hi Manuel,
>
> Based on visual inspection, your code looks correct. You do not have
> to special case the first nearest_vertex search; just pass a default
> Face_handle in the first iteration of the loop and start the loop from
> zero.
>
> Regards,
>
> Damian
>
> On 4/17/09, Manuel Holtgrewe <[hidden email]> wrote:
>> Hi,
>>
>> I am trying to perform finger search with the delaunay hierarchy code
>> from CGAL. That is, I have a random point set which is added as the
>> points of a delaunay hierarchy / triangulation. Then, I have a list of
>> query points which lie along a line through this point set. I want to
>> query for the nearest neighbours of the points on the line.
>>
>> This sequence of queries should offer good locality, i.e. if I know
>> the nearest neighbour x of point i on the line, the nearest neighbour
>> y of point i+1 should be very close to x. Thus, I am trying to use the
>> second parameter to Delaunay_triangulation_2::nearest_vertex(const
>> Point& p, Face_handle f= Face_handle()) const.
>>
>> Will the following code do this, i.e. when calling x->face() (where x
>> is the nearest neighbour of the i-th query point i), will this return
>> a face adjacent to x and this helps to speed up the queries?
>>
>> Thanks,
>> Manuel
>>
>> // typedefs/aliases
>> struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
>>
>> typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
>> typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
>> typedef CGAL::Triangulation_face_base_2<K>                Fb;
>> typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;
>>
>> typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
>> typedef CGAL::Triangulation_hierarchy_2<Dt>
>> Triangulation_hierarchy;
>> typedef Triangulation_hierarchy::Vertex_circulator
>> Vertex_circulator_hierarchy;
>> typedef Triangulation_hierarchy::Point                    Point_hierarchy;
>> typedef Triangulation_hierarchy::Vertex                   Vertex_hierarchy;
>> typedef Triangulation_hierarchy::Vertex_handle
>> Vertex_hierarchy_handle;
>> typedef Triangulation_hierarchy::Face_handle
>> Face_hierarchy_handle;
>>
>> void foo(const std::vector<Point_hierarchy> &points, const
>> std::vector<Point_hierarchy> &queries) {
>>  Triangulation_hierarchy dh;
>>   dh.insert(points.begin(), points.end());
>>   Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
>>   Face_hierarchy_handle f = v->face();
>>   for (int j = 1, jend = queries.size(); j < jend; ++j) {
>>     v = dh.nearest_vertex(queries[j], f);
>>     f = v->face();
>>   }
>> }
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Damian Sheehy
Hi Manuel,

I realized that the line walk may not be of much help since you are performing a nearest-vertex search and not a point-location search. But, if an approximate nearest-vertex search is acceptable for your application, this is something you could consider. If the triangles in your triangulation are reasonably well shaped, equilateral being the perfect shape, then you could compute an approximate nearest-vertex search by selecting the closest vertex from the enclosing triangle. This improves performance by eliminating the many incircle tests that you would otherwise need to compute the exact result.
 
All the best,
 
Damian
On Sat, Apr 18, 2009 at 11:51 PM, Damian Sheehy <[hidden email]> wrote:
Hi Manuel,
 
The Delaunay hierarchy is very fast search structure in and of itself, particularly if a start hint cannot be provided for each query. The purpose of the search hierarchy is to compute a good start location from which to walk. In your case you already have a very good starting location (Face_handle) for each query point. So why would you expect the search hierarchy to do anything for you? (Take a look at the paper: Google Olivier Devillers Delaunay hierarchy).
 
You are not really leveraging functionality of the search hierarchy, but you are paying the overhead of building and maintaining it. Try your search without the hierarchy, providing the start hint as before. If that's not fast enough consider exploiting the structure of your problem; you know that your query points are distributed along a straight line. CGAL provides a very powerful function called a line walk that allows you to compute the set of triangles intersected by a line segment. It may help to take a close look at that. You may be able to set up an interval list from the line walk and replace your N queries by a single line walk plus a subsequent search for an interval.
 
 
All the best!
 
Damian

 
On Sat, Apr 18, 2009 at 12:16 PM, Manuel Holtgrewe <[hidden email]> wrote:
Hi Damian,

Thank you for your answer.

I have written a little program with which I am trying to measure the
speedup that the fingers give me. The source code is attached, I
tested it with CGAL 3.4 on a machine with Intel Xeon processors
@2.3Ghz.

I get the following output:

Delaunay Hierarchy:  finger query vs. non-finger query
        n      build  no_finger     finger    speedup
        2   0.000012   0.424343   0.425491   0.997302
        4   0.000018   0.086763   0.086414   1.004036
        8   0.000015   0.100489   0.099627   1.008651
       16   0.000033   0.114695   0.105578   1.086352
       32   0.000066   0.128658   0.123606   1.040871
       64   0.000134   0.135320   0.116303   1.163512
      128   0.000270   0.178627   0.143877   1.241526
      256   0.000539   0.174100   0.122833   1.417371
      512   0.001070   0.168988   0.150091   1.125904
     1024   0.002091   0.173133   0.160160   1.080999
     2048   0.004395   0.185442   0.175380   1.057372
     4096   0.008549   0.207307   0.195271   1.061638
     8192   0.017413   0.216792   0.208223   1.041154
    16384   0.033093   0.246830   0.232705   1.060700
    32768   0.067720   0.198592   0.188638   1.052769
    65536   0.135914   0.207161   0.195284   1.060819
   131072   0.281401   0.243547   0.232596   1.047081
   262144   0.561701   0.254221   0.240915   1.055233
   524288   1.137475   0.238146   0.225836   1.054509
  1048576   2.287607   0.250391   0.238223   1.051078
  2097152   4.772575   0.252274   0.239942   1.051396
  4194304   9.628133   0.282821   0.270887   1.044055
  8388608  19.543273   0.305526   0.292194   1.045627

As you can see, I could only measure very small speedups. I would
expect them to be much bigger. Am I doing something wrong?

-- Manuel



2009/4/17 Damian Sheehy <[hidden email]>:
> Hi Manuel,
>
> Based on visual inspection, your code looks correct. You do not have
> to special case the first nearest_vertex search; just pass a default
> Face_handle in the first iteration of the loop and start the loop from
> zero.
>
> Regards,
>
> Damian
>
> On 4/17/09, Manuel Holtgrewe <[hidden email]> wrote:
>> Hi,
>>
>> I am trying to perform finger search with the delaunay hierarchy code
>> from CGAL. That is, I have a random point set which is added as the
>> points of a delaunay hierarchy / triangulation. Then, I have a list of
>> query points which lie along a line through this point set. I want to
>> query for the nearest neighbours of the points on the line.
>>
>> This sequence of queries should offer good locality, i.e. if I know
>> the nearest neighbour x of point i on the line, the nearest neighbour
>> y of point i+1 should be very close to x. Thus, I am trying to use the
>> second parameter to Delaunay_triangulation_2::nearest_vertex(const
>> Point& p, Face_handle f= Face_handle()) const.
>>
>> Will the following code do this, i.e. when calling x->face() (where x
>> is the nearest neighbour of the i-th query point i), will this return
>> a face adjacent to x and this helps to speed up the queries?
>>
>> Thanks,
>> Manuel
>>
>> // typedefs/aliases
>> struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
>>
>> typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
>> typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
>> typedef CGAL::Triangulation_face_base_2<K>                Fb;
>> typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;
>>
>> typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
>> typedef CGAL::Triangulation_hierarchy_2<Dt>
>> Triangulation_hierarchy;
>> typedef Triangulation_hierarchy::Vertex_circulator
>> Vertex_circulator_hierarchy;
>> typedef Triangulation_hierarchy::Point                    Point_hierarchy;
>> typedef Triangulation_hierarchy::Vertex                   Vertex_hierarchy;
>> typedef Triangulation_hierarchy::Vertex_handle
>> Vertex_hierarchy_handle;
>> typedef Triangulation_hierarchy::Face_handle
>> Face_hierarchy_handle;
>>
>> void foo(const std::vector<Point_hierarchy> &points, const
>> std::vector<Point_hierarchy> &queries) {
>>  Triangulation_hierarchy dh;
>>   dh.insert(points.begin(), points.end());
>>   Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
>>   Face_hierarchy_handle f = v->face();
>>   for (int j = 1, jend = queries.size(); j < jend; ++j) {
>>     v = dh.nearest_vertex(queries[j], f);
>>     f = v->face();
>>   }
>> }
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Manuel Holtgrewe-3
In reply to this post by Damian Sheehy
Hi Damian,

Sorry, this was me being stupid. I was accidently using a strange
patch (I did not write myself) to Triangulation_hierarchy_2.

However, I really appreciate your comprehensive answers. I also had a
look at Olivier Deviller's paper.

I am confident that I am now compiling against the official 3.4
release of CGAL. For some reason, however, the delaunay triangulation
is very close to the delaunay hierarchy in the queries and the
construction. I attached the benchmark program's source file for any
debunking.

Do the times make sense or would you expect the delaunay hierarchy
being faster than the delaunay triangulation?

Delaunay Hierarchy:  finger query vs. non-finger query
         n       dt_build   dt_no_finger      dt_finger     dt_speedup
      dh_build   dh_no_finger      dh_finger     dh_speedup
         2       0.000011       0.404763       0.403647       1.002765
      0.000002       0.405436       0.405328       1.000266
         4       0.000009       0.089347       0.088662       1.007728
      0.000004       0.088971       0.088810       1.001812
         8       0.000012       0.041551       0.040761       1.019384
      0.000007       0.041474       0.040800       1.016520
        16       0.000025       0.164201       0.158971       1.032899
      0.000016       0.165585       0.160771       1.029943
        32       0.000032       0.069689       0.058045       1.200605
      0.000031       0.069807       0.058301       1.197357
        64       0.000068       0.089519       0.105669       0.847164
      0.000070       0.089585       0.105138       0.852070
       128       0.000138       0.117457       0.084255       1.394065
      0.000136       0.092525       0.064825       1.427303
       256       0.000286       0.118400       0.064962       1.822601
      0.000290       0.118712       0.064920       1.828590
       512       0.000559       0.140097       0.064911       2.158288
      0.000572       0.140355       0.064893       2.162870
      1024       0.001152       0.184033       0.081685       2.252957
      0.001178       0.184366       0.081764       2.254856
      2048       0.002357       0.249846       0.067586       3.696715
      0.002420       0.249937       0.067444       3.705851
      4096       0.004706       0.339099       0.073331       4.624231
      0.004792       0.339403       0.073350       4.627173
      8192       0.009519       0.470756       0.073420       6.411840
      0.009998       0.470833       0.073425       6.412451
     16384       0.019473       0.639252       0.066725       9.580394
      0.020252       0.640028       0.066687       9.597512
     32768       0.040319       0.907107       0.070604      12.847796
      0.042462       0.899606       0.067399      13.347467
     65536       0.082370       1.240469       0.067532      18.368593
      0.087055       1.242859       0.069638      17.847420
    131072       0.169797       1.758881       0.070463      24.961786
      0.178655       1.756205       0.069502      25.268456
    262144       0.345318       2.509199       0.071552      35.068168
      0.362546       2.516872       0.072444      34.742214
    524288       0.715394       3.665781       0.071931      50.962377
      0.750623       3.674317       0.071780      51.188616
   1048576       1.466444       6.713272       0.072994      91.970195
      1.532415       6.730648       0.072908      92.317098
   2097152       3.033258      15.357660       0.075456     203.531586
      3.172991      15.327048       0.075358     203.390026
   4194304       6.165663      30.508426       0.078001     391.128543
      6.438287      30.560829       0.078401     389.802267
   8388608      12.615620      52.426141       0.081205     645.603242
     13.192613      52.019313       0.081088     641.516262


-- Manuel



2009/4/19 Damian Sheehy <[hidden email]>:

> Hi Manuel,
>
> The Delaunay hierarchy is very fast search structure in and of itself,
> particularly if a start hint cannot be provided for each query. The purpose
> of the search hierarchy is to compute a good start location from which to
> walk. In your case you already have a very good starting location
> (Face_handle) for each query point. So why would you expect the search
> hierarchy to do anything for you? (Take a look at the paper: Google Olivier
> Devillers Delaunay hierarchy).
>
> You are not really leveraging functionality of the search hierarchy, but you
> are paying the overhead of building and maintaining it. Try your search
> without the hierarchy, providing the start hint as before. If that's not
> fast enough consider exploiting the structure of your problem; you know that
> your query points are distributed along a straight line. CGAL provides a
> very powerful function called a line walk that allows you to compute the set
> of triangles intersected by a line segment. It may help to take a close look
> at that. You may be able to set up an interval list from the line walk and
> replace your N queries by a single line walk plus a subsequent search for an
> interval.
>
>
> All the best!
>
> Damian
>
> On Sat, Apr 18, 2009 at 12:16 PM, Manuel Holtgrewe <[hidden email]>
> wrote:
>>
>> Hi Damian,
>>
>> Thank you for your answer.
>>
>> I have written a little program with which I am trying to measure the
>> speedup that the fingers give me. The source code is attached, I
>> tested it with CGAL 3.4 on a machine with Intel Xeon processors
>> @2.3Ghz.
>>
>> I get the following output:
>>
>> Delaunay Hierarchy:  finger query vs. non-finger query
>>         n      build  no_finger     finger    speedup
>>         2   0.000012   0.424343   0.425491   0.997302
>>         4   0.000018   0.086763   0.086414   1.004036
>>         8   0.000015   0.100489   0.099627   1.008651
>>        16   0.000033   0.114695   0.105578   1.086352
>>        32   0.000066   0.128658   0.123606   1.040871
>>        64   0.000134   0.135320   0.116303   1.163512
>>       128   0.000270   0.178627   0.143877   1.241526
>>       256   0.000539   0.174100   0.122833   1.417371
>>       512   0.001070   0.168988   0.150091   1.125904
>>      1024   0.002091   0.173133   0.160160   1.080999
>>      2048   0.004395   0.185442   0.175380   1.057372
>>      4096   0.008549   0.207307   0.195271   1.061638
>>      8192   0.017413   0.216792   0.208223   1.041154
>>     16384   0.033093   0.246830   0.232705   1.060700
>>     32768   0.067720   0.198592   0.188638   1.052769
>>     65536   0.135914   0.207161   0.195284   1.060819
>>    131072   0.281401   0.243547   0.232596   1.047081
>>    262144   0.561701   0.254221   0.240915   1.055233
>>    524288   1.137475   0.238146   0.225836   1.054509
>>   1048576   2.287607   0.250391   0.238223   1.051078
>>   2097152   4.772575   0.252274   0.239942   1.051396
>>   4194304   9.628133   0.282821   0.270887   1.044055
>>   8388608  19.543273   0.305526   0.292194   1.045627
>>
>> As you can see, I could only measure very small speedups. I would
>> expect them to be much bigger. Am I doing something wrong?
>>
>> -- Manuel
>>
>>
>>
>> 2009/4/17 Damian Sheehy <[hidden email]>:
>> > Hi Manuel,
>> >
>> > Based on visual inspection, your code looks correct. You do not have
>> > to special case the first nearest_vertex search; just pass a default
>> > Face_handle in the first iteration of the loop and start the loop from
>> > zero.
>> >
>> > Regards,
>> >
>> > Damian
>> >
>> > On 4/17/09, Manuel Holtgrewe <[hidden email]> wrote:
>> >> Hi,
>> >>
>> >> I am trying to perform finger search with the delaunay hierarchy code
>> >> from CGAL. That is, I have a random point set which is added as the
>> >> points of a delaunay hierarchy / triangulation. Then, I have a list of
>> >> query points which lie along a line through this point set. I want to
>> >> query for the nearest neighbours of the points on the line.
>> >>
>> >> This sequence of queries should offer good locality, i.e. if I know
>> >> the nearest neighbour x of point i on the line, the nearest neighbour
>> >> y of point i+1 should be very close to x. Thus, I am trying to use the
>> >> second parameter to Delaunay_triangulation_2::nearest_vertex(const
>> >> Point& p, Face_handle f= Face_handle()) const.
>> >>
>> >> Will the following code do this, i.e. when calling x->face() (where x
>> >> is the nearest neighbour of the i-th query point i), will this return
>> >> a face adjacent to x and this helps to speed up the queries?
>> >>
>> >> Thanks,
>> >> Manuel
>> >>
>> >> // typedefs/aliases
>> >> struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
>> >>
>> >> typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
>> >> typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
>> >> typedef CGAL::Triangulation_face_base_2<K>                Fb;
>> >> typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;
>> >>
>> >> typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
>> >> typedef CGAL::Triangulation_hierarchy_2<Dt>
>> >> Triangulation_hierarchy;
>> >> typedef Triangulation_hierarchy::Vertex_circulator
>> >> Vertex_circulator_hierarchy;
>> >> typedef Triangulation_hierarchy::Point
>> >>  Point_hierarchy;
>> >> typedef Triangulation_hierarchy::Vertex
>> >> Vertex_hierarchy;
>> >> typedef Triangulation_hierarchy::Vertex_handle
>> >> Vertex_hierarchy_handle;
>> >> typedef Triangulation_hierarchy::Face_handle
>> >> Face_hierarchy_handle;
>> >>
>> >> void foo(const std::vector<Point_hierarchy> &points, const
>> >> std::vector<Point_hierarchy> &queries) {
>> >>  Triangulation_hierarchy dh;
>> >>   dh.insert(points.begin(), points.end());
>> >>   Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
>> >>   Face_hierarchy_handle f = v->face();
>> >>   for (int j = 1, jend = queries.size(); j < jend; ++j) {
>> >>     v = dh.nearest_vertex(queries[j], f);
>> >>     f = v->face();
>> >>   }
>> >> }
>> >> --
>> >> You are currently subscribed to cgal-discuss.
>> >> To unsubscribe or access the archives, go to
>> >> https://lists-sop.inria.fr/wws/info/cgal-discuss
>> >>
>> > --
>> > You are currently subscribed to cgal-discuss.
>> > To unsubscribe or access the archives, go to
>> > https://lists-sop.inria.fr/wws/info/cgal-discuss
>> >
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

test_dh_finger.cpp (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Damian Sheehy
Hi Manuel,
 
For a random set of points the Delaunay hierarchy should build a triangulation in much less time than the conventional Delaunay without a hierarchy. The numbers do not reflect that, so something is wrong. I will run your example tomorrow and see what I get. . .
Regards,
 
Damian
 
 
On Sun, Apr 19, 2009 at 7:08 AM, Manuel Holtgrewe <[hidden email]> wrote:
Hi Damian,

Sorry, this was me being stupid. I was accidently using a strange
patch (I did not write myself) to Triangulation_hierarchy_2.

However, I really appreciate your comprehensive answers. I also had a
look at Olivier Deviller's paper.

I am confident that I am now compiling against the official 3.4
release of CGAL. For some reason, however, the delaunay triangulation
is very close to the delaunay hierarchy in the queries and the
construction. I attached the benchmark program's source file for any
debunking.

Do the times make sense or would you expect the delaunay hierarchy
being faster than the delaunay triangulation?

Delaunay Hierarchy:  finger query vs. non-finger query
        n       dt_build   dt_no_finger      dt_finger     dt_speedup
     dh_build   dh_no_finger      dh_finger     dh_speedup
        2       0.000011       0.404763       0.403647       1.002765
     0.000002       0.405436       0.405328       1.000266
        4       0.000009       0.089347       0.088662       1.007728
     0.000004       0.088971       0.088810       1.001812
        8       0.000012       0.041551       0.040761       1.019384
     0.000007       0.041474       0.040800       1.016520
       16       0.000025       0.164201       0.158971       1.032899
     0.000016       0.165585       0.160771       1.029943
       32       0.000032       0.069689       0.058045       1.200605
     0.000031       0.069807       0.058301       1.197357
       64       0.000068       0.089519       0.105669       0.847164
     0.000070       0.089585       0.105138       0.852070
      128       0.000138       0.117457       0.084255       1.394065
     0.000136       0.092525       0.064825       1.427303
      256       0.000286       0.118400       0.064962       1.822601
     0.000290       0.118712       0.064920       1.828590
      512       0.000559       0.140097       0.064911       2.158288
     0.000572       0.140355       0.064893       2.162870
     1024       0.001152       0.184033       0.081685       2.252957
     0.001178       0.184366       0.081764       2.254856
     2048       0.002357       0.249846       0.067586       3.696715
     0.002420       0.249937       0.067444       3.705851
     4096       0.004706       0.339099       0.073331       4.624231
     0.004792       0.339403       0.073350       4.627173
     8192       0.009519       0.470756       0.073420       6.411840
     0.009998       0.470833       0.073425       6.412451
    16384       0.019473       0.639252       0.066725       9.580394
     0.020252       0.640028       0.066687       9.597512
    32768       0.040319       0.907107       0.070604      12.847796
     0.042462       0.899606       0.067399      13.347467
    65536       0.082370       1.240469       0.067532      18.368593
     0.087055       1.242859       0.069638      17.847420
   131072       0.169797       1.758881       0.070463      24.961786
     0.178655       1.756205       0.069502      25.268456
   262144       0.345318       2.509199       0.071552      35.068168
     0.362546       2.516872       0.072444      34.742214
   524288       0.715394       3.665781       0.071931      50.962377
     0.750623       3.674317       0.071780      51.188616
  1048576       1.466444       6.713272       0.072994      91.970195
     1.532415       6.730648       0.072908      92.317098
  2097152       3.033258      15.357660       0.075456     203.531586
     3.172991      15.327048       0.075358     203.390026
  4194304       6.165663      30.508426       0.078001     391.128543
     6.438287      30.560829       0.078401     389.802267
  8388608      12.615620      52.426141       0.081205     645.603242
    13.192613      52.019313       0.081088     641.516262


-- Manuel



2009/4/19 Damian Sheehy <[hidden email]>:
> Hi Manuel,
>
> The Delaunay hierarchy is very fast search structure in and of itself,
> particularly if a start hint cannot be provided for each query. The purpose
> of the search hierarchy is to compute a good start location from which to
> walk. In your case you already have a very good starting location
> (Face_handle) for each query point. So why would you expect the search
> hierarchy to do anything for you? (Take a look at the paper: Google Olivier
> Devillers Delaunay hierarchy).
>
> You are not really leveraging functionality of the search hierarchy, but you
> are paying the overhead of building and maintaining it. Try your search
> without the hierarchy, providing the start hint as before. If that's not
> fast enough consider exploiting the structure of your problem; you know that
> your query points are distributed along a straight line. CGAL provides a
> very powerful function called a line walk that allows you to compute the set
> of triangles intersected by a line segment. It may help to take a close look
> at that. You may be able to set up an interval list from the line walk and
> replace your N queries by a single line walk plus a subsequent search for an
> interval.
>
>
> All the best!
>
> Damian
>
> On Sat, Apr 18, 2009 at 12:16 PM, Manuel Holtgrewe <[hidden email]>
> wrote:
>>
>> Hi Damian,
>>
>> Thank you for your answer.
>>
>> I have written a little program with which I am trying to measure the
>> speedup that the fingers give me. The source code is attached, I
>> tested it with CGAL 3.4 on a machine with Intel Xeon processors
>> @2.3Ghz.
>>
>> I get the following output:
>>
>> Delaunay Hierarchy:  finger query vs. non-finger query
>>         n      build  no_finger     finger    speedup
>>         2   0.000012   0.424343   0.425491   0.997302
>>         4   0.000018   0.086763   0.086414   1.004036
>>         8   0.000015   0.100489   0.099627   1.008651
>>        16   0.000033   0.114695   0.105578   1.086352
>>        32   0.000066   0.128658   0.123606   1.040871
>>        64   0.000134   0.135320   0.116303   1.163512
>>       128   0.000270   0.178627   0.143877   1.241526
>>       256   0.000539   0.174100   0.122833   1.417371
>>       512   0.001070   0.168988   0.150091   1.125904
>>      1024   0.002091   0.173133   0.160160   1.080999
>>      2048   0.004395   0.185442   0.175380   1.057372
>>      4096   0.008549   0.207307   0.195271   1.061638
>>      8192   0.017413   0.216792   0.208223   1.041154
>>     16384   0.033093   0.246830   0.232705   1.060700
>>     32768   0.067720   0.198592   0.188638   1.052769
>>     65536   0.135914   0.207161   0.195284   1.060819
>>    131072   0.281401   0.243547   0.232596   1.047081
>>    262144   0.561701   0.254221   0.240915   1.055233
>>    524288   1.137475   0.238146   0.225836   1.054509
>>   1048576   2.287607   0.250391   0.238223   1.051078
>>   2097152   4.772575   0.252274   0.239942   1.051396
>>   4194304   9.628133   0.282821   0.270887   1.044055
>>   8388608  19.543273   0.305526   0.292194   1.045627
>>
>> As you can see, I could only measure very small speedups. I would
>> expect them to be much bigger. Am I doing something wrong?
>>
>> -- Manuel
>>
>>
>>
>> 2009/4/17 Damian Sheehy <[hidden email]>:
>> > Hi Manuel,
>> >
>> > Based on visual inspection, your code looks correct. You do not have
>> > to special case the first nearest_vertex search; just pass a default
>> > Face_handle in the first iteration of the loop and start the loop from
>> > zero.
>> >
>> > Regards,
>> >
>> > Damian
>> >
>> > On 4/17/09, Manuel Holtgrewe <[hidden email]> wrote:
>> >> Hi,
>> >>
>> >> I am trying to perform finger search with the delaunay hierarchy code
>> >> from CGAL. That is, I have a random point set which is added as the
>> >> points of a delaunay hierarchy / triangulation. Then, I have a list of
>> >> query points which lie along a line through this point set. I want to
>> >> query for the nearest neighbours of the points on the line.
>> >>
>> >> This sequence of queries should offer good locality, i.e. if I know
>> >> the nearest neighbour x of point i on the line, the nearest neighbour
>> >> y of point i+1 should be very close to x. Thus, I am trying to use the
>> >> second parameter to Delaunay_triangulation_2::nearest_vertex(const
>> >> Point& p, Face_handle f= Face_handle()) const.
>> >>
>> >> Will the following code do this, i.e. when calling x->face() (where x
>> >> is the nearest neighbour of the i-th query point i), will this return
>> >> a face adjacent to x and this helps to speed up the queries?
>> >>
>> >> Thanks,
>> >> Manuel
>> >>
>> >> // typedefs/aliases
>> >> struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
>> >>
>> >> typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
>> >> typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
>> >> typedef CGAL::Triangulation_face_base_2<K>                Fb;
>> >> typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;
>> >>
>> >> typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
>> >> typedef CGAL::Triangulation_hierarchy_2<Dt>
>> >> Triangulation_hierarchy;
>> >> typedef Triangulation_hierarchy::Vertex_circulator
>> >> Vertex_circulator_hierarchy;
>> >> typedef Triangulation_hierarchy::Point
>> >>  Point_hierarchy;
>> >> typedef Triangulation_hierarchy::Vertex
>> >> Vertex_hierarchy;
>> >> typedef Triangulation_hierarchy::Vertex_handle
>> >> Vertex_hierarchy_handle;
>> >> typedef Triangulation_hierarchy::Face_handle
>> >> Face_hierarchy_handle;
>> >>
>> >> void foo(const std::vector<Point_hierarchy> &points, const
>> >> std::vector<Point_hierarchy> &queries) {
>> >>  Triangulation_hierarchy dh;
>> >>   dh.insert(points.begin(), points.end());
>> >>   Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
>> >>   Face_hierarchy_handle f = v->face();
>> >>   for (int j = 1, jend = queries.size(); j < jend; ++j) {
>> >>     v = dh.nearest_vertex(queries[j], f);
>> >>     f = v->face();
>> >>   }
>> >> }
>> >> --
>> >> You are currently subscribed to cgal-discuss.
>> >> To unsubscribe or access the archives, go to
>> >> https://lists-sop.inria.fr/wws/info/cgal-discuss
>> >>
>> > --
>> > You are currently subscribed to cgal-discuss.
>> > To unsubscribe or access the archives, go to
>> > https://lists-sop.inria.fr/wws/info/cgal-discuss
>> >
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Sylvain Pion
Administrator
Hi Damian,

Damian Sheehy a écrit :
> For a random set of points the Delaunay hierarchy should build a
> triangulation in much less time than the conventional Delaunay without a
> hierarchy. The numbers do not reflect that, so something is wrong. I
> will run your example tomorrow and see what I get. . .

This is not true anymore in recent CGAL releases, more precisely
since the introduction of a spatial sorting preprocessing phase (BRIO).

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Damian Sheehy
Sylvain,
 
Thank you for enlightening me!  :)
 
Manuel,
 
Your non-hierarchical triangulation (dt_build in your notation) calls the dt.insert(begin, end) interface. This interface performs preprocessing to sort the points along a Hilbert curve which improves the performance of insertion. I did not factor this in when I compared computation times for the Delaunay and the Delaunay+hierarchy construction. To perform an apple-to-apple comparison of the performance of these two algorithms you should use the dt/dh.insert(Point) interface.
 
So in summary, the hierarchy is not being leveraged during construction because the sort ensures the resulting sequence of points is in close geometric proximity; the hierarchy is not being leveraged during nearest_vertex queries because you are already providing a good starting hint. Conclusion, the hierarchy is not doing anything for you so you don't need it.
 
 
Best regards,
 
Damian
 
On Sun, Apr 19, 2009 at 8:10 AM, Sylvain Pion <[hidden email]> wrote:
Hi Damian,

Damian Sheehy a écrit :

For a random set of points the Delaunay hierarchy should build a triangulation in much less time than the conventional Delaunay without a hierarchy. The numbers do not reflect that, so something is wrong. I will run your example tomorrow and see what I get. . .

This is not true anymore in recent CGAL releases, more precisely
since the introduction of a spatial sorting preprocessing phase (BRIO).

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Manuel Holtgrewe-3
Sylvain,

thanks for your answer. However, please have another look at the data
(I cut out the lesse interesting columns so the table is not wrapped.

Note that I am also performing a query without hints. In this case, I
would expect the delaunay hierarchy to be faster than the delaunay
triangulation.

Could someone compile the source file (reattached in this email) and
verify my results?

Somehow, I have the impression that the same code is called for the
delaunay triangulation and the delaunay hierarchy.

Bests,
Manuel

      n   dt_no_finger  dt_finger  dh_no_finger  dh_finger
      2       0.505304   0.477886      0.475679   0.475234
      4       0.103188   0.102858      0.102885   0.101524
      8       0.042936   0.041076      0.043392   0.041294
     16       0.056725   0.047944      0.056533   0.048035
     32       0.075375   0.059116      0.075654   0.059563
     64       0.088672   0.062105      0.088614   0.062050
    128       0.132514   0.086989      0.132462   0.087279
    256       0.140531   0.078194      0.140511   0.078217
    512       0.175971   0.064753      0.173778   0.064725
   1024       0.222064   0.069129      0.221879   0.069079
   2048       0.299477   0.067341      0.298769   0.067386
   4096       0.392608   0.066532      0.393548   0.066462
   8192       0.547986   0.069801      0.546512   0.069839
  16384       0.741440   0.066260      0.741307   0.066181
  32768       1.080815   0.067014      1.084949   0.066969
  65536       1.518390   0.066989      1.512893   0.067106
 131072       2.312096   0.070554      2.320022   0.071241
 262144       3.690626   0.072124      3.677720   0.071980
 524288       6.416665   0.072153      6.279038   0.071597
1048576      13.649976   0.072951     13.965254   0.074540
2097152      27.961286   0.075513     27.911974   0.075280
4194304      48.720407   0.079028     49.280193   0.078284

-- Manuel



2009/4/20 Damian Sheehy <[hidden email]>:

> Sylvain,
>
> Thank you for enlightening me!  :)
>
> Manuel,
>
> Your non-hierarchical triangulation (dt_build in your notation) calls the
> dt.insert(begin, end) interface. This interface performs preprocessing to
> sort the points along a Hilbert curve which improves the performance of
> insertion. I did not factor this in when I compared computation times for
> the Delaunay and the Delaunay+hierarchy construction. To perform an
> apple-to-apple comparison of the performance of these two algorithms you
> should use the dt/dh.insert(Point) interface.
>
> So in summary, the hierarchy is not being leveraged during construction
> because the sort ensures the resulting sequence of points is in close
> geometric proximity; the hierarchy is not being leveraged during
> nearest_vertex queries because you are already providing a good starting
> hint. Conclusion, the hierarchy is not doing anything for you so you don't
> need it.
>
>
> Best regards,
>
> Damian
>
> On Sun, Apr 19, 2009 at 8:10 AM, Sylvain Pion <[hidden email]>
> wrote:
>>
>> Hi Damian,
>>
>> Damian Sheehy a écrit :
>>>
>>> For a random set of points the Delaunay hierarchy should build a
>>> triangulation in much less time than the conventional Delaunay without a
>>> hierarchy. The numbers do not reflect that, so something is wrong. I will
>>> run your example tomorrow and see what I get. . .
>>
>> This is not true anymore in recent CGAL releases, more precisely
>> since the introduction of a spatial sorting preprocessing phase (BRIO).
>>
>> --
>> Sylvain Pion
>> INRIA Sophia-Antipolis
>> Geometrica Project-Team
>> CGAL, http://cgal.org/
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

test_dh_finger.cpp (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Manuel Caroli
Hi Manuel,

you are right. Unlike point location the nearest vertex query is not
overloaded by the triangulation hierarchy. Followingly the one from DT
is called.

Best

Manuel


Manuel Holtgrewe wrote:

> Sylvain,
>
> thanks for your answer. However, please have another look at the data
> (I cut out the lesse interesting columns so the table is not wrapped.
>
> Note that I am also performing a query without hints. In this case, I
> would expect the delaunay hierarchy to be faster than the delaunay
> triangulation.
>
> Could someone compile the source file (reattached in this email) and
> verify my results?
>
> Somehow, I have the impression that the same code is called for the
> delaunay triangulation and the delaunay hierarchy.
>
> Bests,
> Manuel
>
>       n   dt_no_finger  dt_finger  dh_no_finger  dh_finger
>       2       0.505304   0.477886      0.475679   0.475234
>       4       0.103188   0.102858      0.102885   0.101524
>       8       0.042936   0.041076      0.043392   0.041294
>      16       0.056725   0.047944      0.056533   0.048035
>      32       0.075375   0.059116      0.075654   0.059563
>      64       0.088672   0.062105      0.088614   0.062050
>     128       0.132514   0.086989      0.132462   0.087279
>     256       0.140531   0.078194      0.140511   0.078217
>     512       0.175971   0.064753      0.173778   0.064725
>    1024       0.222064   0.069129      0.221879   0.069079
>    2048       0.299477   0.067341      0.298769   0.067386
>    4096       0.392608   0.066532      0.393548   0.066462
>    8192       0.547986   0.069801      0.546512   0.069839
>   16384       0.741440   0.066260      0.741307   0.066181
>   32768       1.080815   0.067014      1.084949   0.066969
>   65536       1.518390   0.066989      1.512893   0.067106
>  131072       2.312096   0.070554      2.320022   0.071241
>  262144       3.690626   0.072124      3.677720   0.071980
>  524288       6.416665   0.072153      6.279038   0.071597
> 1048576      13.649976   0.072951     13.965254   0.074540
> 2097152      27.961286   0.075513     27.911974   0.075280
> 4194304      48.720407   0.079028     49.280193   0.078284
>
> -- Manuel
>
>
>
> 2009/4/20 Damian Sheehy <[hidden email]>:
>> Sylvain,
>>
>> Thank you for enlightening me!  :)
>>
>> Manuel,
>>
>> Your non-hierarchical triangulation (dt_build in your notation) calls the
>> dt.insert(begin, end) interface. This interface performs preprocessing to
>> sort the points along a Hilbert curve which improves the performance of
>> insertion. I did not factor this in when I compared computation times for
>> the Delaunay and the Delaunay+hierarchy construction. To perform an
>> apple-to-apple comparison of the performance of these two algorithms you
>> should use the dt/dh.insert(Point) interface.
>>
>> So in summary, the hierarchy is not being leveraged during construction
>> because the sort ensures the resulting sequence of points is in close
>> geometric proximity; the hierarchy is not being leveraged during
>> nearest_vertex queries because you are already providing a good starting
>> hint. Conclusion, the hierarchy is not doing anything for you so you don't
>> need it.
>>
>>
>> Best regards,
>>
>> Damian
>>
>> On Sun, Apr 19, 2009 at 8:10 AM, Sylvain Pion <[hidden email]>
>> wrote:
>>> Hi Damian,
>>>
>>> Damian Sheehy a écrit :
>>>> For a random set of points the Delaunay hierarchy should build a
>>>> triangulation in much less time than the conventional Delaunay without a
>>>> hierarchy. The numbers do not reflect that, so something is wrong. I will
>>>> run your example tomorrow and see what I get. . .
>>> This is not true anymore in recent CGAL releases, more precisely
>>> since the introduction of a spatial sorting preprocessing phase (BRIO).
>>>
>>> --
>>> Sylvain Pion
>>> INRIA Sophia-Antipolis
>>> Geometrica Project-Team
>>> CGAL, http://cgal.org/
>>> --
>>> You are currently subscribed to cgal-discuss.
>>> To unsubscribe or access the archives, go to
>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Laurent Rineau (GeometryFactory)
On Wednesday 22 April 2009 13:29:31 Manuel Caroli wrote:
> Hi Manuel,
>
> you are right. Unlike point location the nearest vertex query is not
> overloaded by the triangulation hierarchy. Followingly the one from DT
> is called.

That is a bug, in my opinion. Would it be easy to overload the nearest vertex
query?

--
Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Sylvain Pion
Administrator
Laurent Rineau (GeometryFactory) wrote:
> On Wednesday 22 April 2009 13:29:31 Manuel Caroli wrote:
>> Hi Manuel,
>>
>> you are right. Unlike point location the nearest vertex query is not
>> overloaded by the triangulation hierarchy. Followingly the one from DT
>> is called.
>
> That is a bug, in my opinion. Would it be easy to overload the nearest vertex
> query?

I'm working on it.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Laurent Rineau (GeometryFactory)
On Wednesday 22 April 2009 13:48:01 Sylvain Pion wrote:

> Laurent Rineau (GeometryFactory) wrote:
> > On Wednesday 22 April 2009 13:29:31 Manuel Caroli wrote:
> >> Hi Manuel,
> >>
> >> you are right. Unlike point location the nearest vertex query is not
> >> overloaded by the triangulation hierarchy. Followingly the one from DT
> >> is called.
> >
> > That is a bug, in my opinion. Would it be easy to overload the nearest
> > vertex query?
>
> I'm working on it.

In my opinion we should use the *template pattern* (from the book of
Gamma&al.), maybe using a CRTP, so that all methods of the triangulation that
depend on the "locate" function are accelerated in the hierarchy.

--
Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Manuel Holtgrewe-3
In reply to this post by Manuel Caroli
Hi Manuel,

Thanks for your answer.

I have attached the now hopefully correct program for leveraging the
Delaunay Hierarchy in nearest neighbour queries.

Maybe it is of use to someone. Here are the juicy bits of the
program's output on my machine:

$>./test_dh_finger
Delaunay Hierarchy:  finger query vs. non-finger query
         n dt_no_finger  dt_finger  dh_no_finger  dh_finger  dh_speedup
         2     0.550073   0.494133      0.499732   0.492765    1.014139
         4     0.180180   0.143496      0.150785   0.145044    1.039580
         8     0.042447   0.040908      0.048284   0.040934    1.179556
        16     0.187192   0.181526      0.194100   0.180929    1.072796
        32     0.072436   0.058800      0.078396   0.058778    1.333770
        64     0.146741   0.123116      0.154736   0.123907    1.248807
       128     0.131286   0.088024      0.136889   0.088209    1.551872
       256     0.144457   0.086384      0.150825   0.086563    1.742375
       512     0.186457   0.084601      0.192442   0.084808    2.269152
      1024     0.215611   0.069493      0.116932   0.069964    1.671317
      2048     0.297175   0.074581      0.141820   0.074778    1.896554
      4096     0.383350   0.069184      0.169974   0.069191    2.456590
      8192     0.527038   0.068528      0.177454   0.068764    2.580625
     16384     0.708779   0.066241      0.150414   0.066194    2.272327
     32768     1.047828   0.072765      0.165167   0.072591    2.275306
     65536     1.481253   0.069943      0.178241   0.069794    2.553818
    131072     2.243405   0.070851      0.196017   0.070185    2.792864
    262144     3.585705   0.072495      0.222337   0.071803    3.096482
    524288     6.232107   0.071436      0.255025   0.070398    3.622623
   1048576    13.459370   0.073421      0.200260   0.072325    2.768890

-- Manuel



2009/4/22 Manuel Caroli <[hidden email]>:

> Hi Manuel,
>
> you are right. Unlike point location the nearest vertex query is not
> overloaded by the triangulation hierarchy. Followingly the one from DT is
> called.
>
> Best
>
> Manuel
>
>
> Manuel Holtgrewe wrote:
>>
>> Sylvain,
>>
>> thanks for your answer. However, please have another look at the data
>> (I cut out the lesse interesting columns so the table is not wrapped.
>>
>> Note that I am also performing a query without hints. In this case, I
>> would expect the delaunay hierarchy to be faster than the delaunay
>> triangulation.
>>
>> Could someone compile the source file (reattached in this email) and
>> verify my results?
>>
>> Somehow, I have the impression that the same code is called for the
>> delaunay triangulation and the delaunay hierarchy.
>>
>> Bests,
>> Manuel
>>
>>      n   dt_no_finger  dt_finger  dh_no_finger  dh_finger
>>      2       0.505304   0.477886      0.475679   0.475234
>>      4       0.103188   0.102858      0.102885   0.101524
>>      8       0.042936   0.041076      0.043392   0.041294
>>     16       0.056725   0.047944      0.056533   0.048035
>>     32       0.075375   0.059116      0.075654   0.059563
>>     64       0.088672   0.062105      0.088614   0.062050
>>    128       0.132514   0.086989      0.132462   0.087279
>>    256       0.140531   0.078194      0.140511   0.078217
>>    512       0.175971   0.064753      0.173778   0.064725
>>   1024       0.222064   0.069129      0.221879   0.069079
>>   2048       0.299477   0.067341      0.298769   0.067386
>>   4096       0.392608   0.066532      0.393548   0.066462
>>   8192       0.547986   0.069801      0.546512   0.069839
>>  16384       0.741440   0.066260      0.741307   0.066181
>>  32768       1.080815   0.067014      1.084949   0.066969
>>  65536       1.518390   0.066989      1.512893   0.067106
>>  131072       2.312096   0.070554      2.320022   0.071241
>>  262144       3.690626   0.072124      3.677720   0.071980
>>  524288       6.416665   0.072153      6.279038   0.071597
>> 1048576      13.649976   0.072951     13.965254   0.074540
>> 2097152      27.961286   0.075513     27.911974   0.075280
>> 4194304      48.720407   0.079028     49.280193   0.078284
>>
>> -- Manuel
>>
>>
>>
>> 2009/4/20 Damian Sheehy <[hidden email]>:
>>>
>>> Sylvain,
>>>
>>> Thank you for enlightening me!  :)
>>>
>>> Manuel,
>>>
>>> Your non-hierarchical triangulation (dt_build in your notation) calls the
>>> dt.insert(begin, end) interface. This interface performs preprocessing to
>>> sort the points along a Hilbert curve which improves the performance of
>>> insertion. I did not factor this in when I compared computation times for
>>> the Delaunay and the Delaunay+hierarchy construction. To perform an
>>> apple-to-apple comparison of the performance of these two algorithms you
>>> should use the dt/dh.insert(Point) interface.
>>>
>>> So in summary, the hierarchy is not being leveraged during construction
>>> because the sort ensures the resulting sequence of points is in close
>>> geometric proximity; the hierarchy is not being leveraged during
>>> nearest_vertex queries because you are already providing a good starting
>>> hint. Conclusion, the hierarchy is not doing anything for you so you
>>> don't
>>> need it.
>>>
>>>
>>> Best regards,
>>>
>>> Damian
>>>
>>> On Sun, Apr 19, 2009 at 8:10 AM, Sylvain Pion
>>> <[hidden email]>
>>> wrote:
>>>>
>>>> Hi Damian,
>>>>
>>>> Damian Sheehy a écrit :
>>>>>
>>>>> For a random set of points the Delaunay hierarchy should build a
>>>>> triangulation in much less time than the conventional Delaunay without
>>>>> a
>>>>> hierarchy. The numbers do not reflect that, so something is wrong. I
>>>>> will
>>>>> run your example tomorrow and see what I get. . .
>>>>
>>>> This is not true anymore in recent CGAL releases, more precisely
>>>> since the introduction of a spatial sorting preprocessing phase (BRIO).
>>>>
>>>> --
>>>> Sylvain Pion
>>>> INRIA Sophia-Antipolis
>>>> Geometrica Project-Team
>>>> CGAL, http://cgal.org/
>>>> --
>>>> You are currently subscribed to cgal-discuss.
>>>> To unsubscribe or access the archives, go to
>>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>>>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

test_dh_finger.cpp (8K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Using finger search with Delaunay Triangulation

Sylvain Pion
Administrator
In reply to this post by Sylvain Pion
Sylvain Pion wrote:

> Laurent Rineau (GeometryFactory) wrote:
>> On Wednesday 22 April 2009 13:29:31 Manuel Caroli wrote:
>>> Hi Manuel,
>>>
>>> you are right. Unlike point location the nearest vertex query is not
>>> overloaded by the triangulation hierarchy. Followingly the one from DT
>>> is called.
>>
>> That is a bug, in my opinion. Would it be easy to overload the nearest
>> vertex query?
>
> I'm working on it.

Something like the following patch should do it.


Index: include/CGAL/Triangulation_hierarchy_2.h
===================================================================
--- include/CGAL/Triangulation_hierarchy_2.h (révision 48856)
+++ include/CGAL/Triangulation_hierarchy_2.h (copie de travail)
@@ -38,7 +38,7 @@
 
 template < class Tr>
 class Triangulation_hierarchy_2
-: public Tr
+  : public Tr
 {
  public:
   typedef Tr                                   Tr_Base;
@@ -52,6 +52,8 @@
   typedef typename Tr_Base::Finite_vertices_iterator  Finite_vertices_iterator;
   //typedef typename Tr_Base::Finite_faces_iterator     Finite_faces_iterator;
 
+  typedef typename Tr_Base::Weighted_tag       Weighted_tag;
+
 #ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_2
   using Tr_Base::geom_traits;
 #endif
@@ -147,7 +149,30 @@
   locate(const Point &p,
  Face_handle start = Face_handle()) const;
 
+  Vertex_handle
+  nearest_vertex(const Point& p, Face_handle start = Face_handle()) const
+  {
+    return nearest_vertex_dispatch<Tr>(p, start, Weighted_tag());
+  }
+
 private:
+
+  template < typename T >
+  Vertex_handle
+  nearest_vertex_dispatch(const Point& p, Face_handle start, Tag_false) const
+  {
+    return T::nearest_vertex(p, start != Face_handle() ? start : locate(p));
+  }
+
+  // There is no nearest_vertex() for Regular.
+  template < typename T >
+  Vertex_handle
+  nearest_vertex_dispatch(const Point&, Face_handle, Tag_true) const
+  {
+    CGAL_triangulation_assertion(false);
+    return Vertex_handle();
+  }
+
   void  locate_in_all(const Point& p,
       Locate_type& lt,
       int& li,
@@ -234,9 +259,9 @@
       if (it->up() != Vertex_handle()) V[ it->up()->down() ] = it;
     }
   }
-  typename Tr_Base::Weighted_tag tag;
-  add_hidden_vertices_into_map(tag,V);
 
+  add_hidden_vertices_into_map(Weighted_tag(), V);
+
   {
     for(int i=1;i<Triangulation_hierarchy_2__maxlevel;++i) {
       for( Finite_vertices_iterator it=hierarchy[i]->finite_vertices_begin();
@@ -535,7 +560,6 @@
   pos[0]=hierarchy[0]->locate(p,lt,li,loc == Face_handle() ? position : loc);  // at level 0
 }
 
-
 template <class Tr>
 int
 Triangulation_hierarchy_2<Tr>::


--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss