Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Using finger search with Delaunay Triangulation

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Using finger search with Delaunay Triangulation


Chronological Thread 
  • From: Manuel Holtgrewe <>
  • To:
  • Cc: Johannes Singler <>
  • Subject: Re: [cgal-discuss] Using finger search with Delaunay Triangulation
  • Date: Sat, 18 Apr 2009 18:16:21 +0200
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type; b=stMi4zvlxrz85/OCBhxttKHbLZbbeUeKHRfLA87ndRoTHyzAYij9IRXMb34Newq3sM z92CIOW9ovUHF3BqjUSnEMJAjzn0LfgMUB7AsbgRAeape81ehLgze6Iyf9WGkjl8h6ch uhY0+WHFVHve/8TR4l6VFnQxAnczmYfi+v5Pg=

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
>

Attachment: test_dh_finger.cpp
Description: Binary data




Archive powered by MHonArc 2.6.16.

Top of Page