CGAL users discussion list

[Manuel Holtgrewe <>]

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 
<>:
> 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 
> <>
> 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
>
>
// File:   test_dh_finger.cpp
// Author: Manuel Holtgrewe 
<>

#include <tr1/random>
#include <vector>

#include <CGAL/Circle_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_hierarchy_2.h>
#include <CGAL/Real_timer.h>

// The Kernel we will use in our datastructures.
struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};

// Define some geometric primitive types.
typedef K::Circle_2                                       Circle;
typedef K::Vector_2                                       Vector;

// The datastructures for the Delaunay triangulation hierarchy.
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;
typedef Triangulation_hierarchy::Vertex                   Vertex;
typedef Triangulation_hierarchy::Vertex_handle            Vertex_handle;
typedef Triangulation_hierarchy::Face_handle              Face_handle;

const int seed = 42;


int main(int argc, char **argv)
{
  std::tr1::mt19937 mt(seed);
  int m = 1 << 16; // Number of queries.
  printf("Delaunay Hierarchy:  finger query vs. non-finger query\n");
  printf("%10s %14s %14s %14s %14s %14s %14s %14s %14s\n", "n", "dt_build",
         "dt_no_finger", "dt_finger", "dt_speedup", "dh_build",
         "dh_no_finger", "dh_finger", "dh_speedup");

  // Create the queries on a line (0, 0) to (1, 1).
  std::vector<Point> queries;
  for (int i = 0; i < m; ++i) {
    double x = 1.0 * i / (m - 1);
    queries.push_back(Point(x, x));
  }

  for (int k = 1; k <= 23; ++k) {
    int n = 1 << k;  // number of points
    printf("%10d", n);

    // Create points.
    std::vector<Point> points;
    for (int i = 0; i < n; ++i)
      points.push_back(Point(1.0 * mt() / mt.max(), 1.0 * mt() / mt.max()));

    // Delaunay triangulation.
    {
      Dt dt;
      // Insert points into Delaunay triangulation.
      {
        CGAL::Real_timer timer;
        timer.start();
        dt.insert(points.begin(), points.end());
        timer.stop();
        printf(" %14f", timer.time());
      }

      // Perform queries without finger.
      double no_finger_time;
      {
        CGAL::Real_timer timer;
        timer.start();
        for (int j = 0, jend = queries.size(); j < jend; ++j)
          dt.nearest_vertex(queries[j]);
        timer.stop();
        no_finger_time = timer.time();
        printf(" %14f", timer.time());
      }

      // Perform queries with finger.
      double finger_time;
      {
        CGAL::Real_timer timer;
        timer.start();
        Vertex_handle v = dt.nearest_vertex(queries[0]);
        Face_handle f = v->face();
        for (int j = 1, jend = queries.size(); j < jend; ++j) {
          v = dt.nearest_vertex(queries[j], f);
          f = v->face();
        }
        timer.stop();
        finger_time = timer.time();
        printf(" %14f", timer.time());
      }

      printf(" %14f", no_finger_time / finger_time);
    }

    // Delaunay hierarchy.
    {
      Triangulation_hierarchy dh;
      // Insert points into Delaunay hierarchy.
      {
        CGAL::Real_timer timer;
        timer.start();
        dh.insert(points.begin(), points.end());
        timer.stop();
        printf(" %14f", timer.time());
      }

      // Perform queries without finger.
      double no_finger_time;
      {
        CGAL::Real_timer timer;
        timer.start();
        for (int j = 0, jend = queries.size(); j < jend; ++j)
          dh.nearest_vertex(queries[j]);
        timer.stop();
        no_finger_time = timer.time();
        printf(" %14f", timer.time());
      }

      // Perform queries with finger.
      double finger_time;
      {
        CGAL::Real_timer timer;
        timer.start();
        Vertex_handle v = dh.nearest_vertex(queries[0]);
        Face_handle f = v->face();
        for (int j = 1, jend = queries.size(); j < jend; ++j) {
          v = dh.nearest_vertex(queries[j], f);
          f = v->face();
        }
        timer.stop();
        finger_time = timer.time();
        printf(" %14f", timer.time());
      }

      printf(" %14f", no_finger_time / finger_time);
    }

    printf("\n");
  }
  return 0;
}