CGAL users discussion list

[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 <> 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 <> 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 <>:

> 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 <> 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