CGAL users discussion list

[Manuel Caroli <>]

Hi,

the weighted Delaunay triangulation has some additional overhead due to 
points that can be hidden. If you have a lot of hidden points this might 
have a considerable effect on running times. Also maybe you profit from 
some optimizations in Delaunay triangulation but not in the weighted 
Delaunay triangulation.

Without more information about your problem and your code and I cannot 
tell you more than the above speculations.

best

Manuel


400555 wrote:
> Hello !
>
> Could you say your opinion about:
>
> I tried to compare performance between using CGAL Delaunay and Regular 
> triangulation with weighted points.
>
> I rebuilt it 200.000 times for moving points (I know that rebuilding is 
> not best option) and Delaunay takes 17 sec but weighted one - 64 seconds.
> I don't understand why, difference is only that weighted one considers 
> about weight which is included in determinant (which defines "in circle" 
> criteria), please correct me if I am wrong.
> So I was not expected so much time difference between them.
>
> Do you know why it happen?
>
> Thank you.
>
>
> On Wed, Aug 12, 2009 at 7:02 PM, 400555 < 
> <mailto:>> wrote:
>
>     Dear Sebastien, thank you very much!
>
>     Now it works!
>
>
>     On Wed, Aug 12, 2009 at 6:50 PM, Sebastien Loriot
>     
> <
>     
> <mailto:>>
>  wrote:
>
>         Hello,
>
>         The vertex type you are using is for triangulation.
>         You should use CGAL::Regular_triangulation_vertex_base_2 instead.
>         Then to add info you can follow what is done for the case of the
>         triangulation of point in
>         Triangulation_vertex_base_with_info_2.h
>
>         S.
>         
> <http://www.cgal.org/Manual/last/doc_html/cgal_manual/Triangulation_2_ref/Class_Regular_triangulation_vertex_base_2.html#Cross_link_anchor_1161>
>         400555 wrote:
>
>             Dear Manuel,
>
>             thank you for help!
>
>             Now I have problem, when I am trying to insert points.
>             I do it like this:
>
>             typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
>             typedef CGAL::Regular_triangulation_filtered_traits_2<K> Traits;
>             typedef CGAL::Triangulation_vertex_base_with_info_2<int, K> Vb;
>             typedef CGAL::Regular_triangulation_face_base_2<K> Fb;
>             typedef CGAL::Triangulation_data_structure_2<Vb, Fb> Tds;
>             typedef CGAL::Regular_triangulation_2<Traits, Tds> RegularTr;
>
>                    typedef K::Point_2 Point;
>             typedef RegularTr::Weighted_point WPoint;
>
>                    .....
>
>             RegularTr T;
>             WPoint wp(Point(1,2), 2);
>             T.insert(wp);  // If delete this line - no compiler errors !!!
>
>             I tried to modify type of Kernel and way how I define
>             Weighted_point, but it doesn't work
>             Could you please help me?
>
>             
> //////////////////////////////////////////////////////////////////////////////////////
>
>             /usr/bin/c++    -frounding-math -O3 -DNDEBUG
>             -I/storage/usr/people/400555/MD
>             -I/storage/usr/people/400555/CGAL-3.4/include   -o
>             CMakeFiles/main.dir/main.o -c
>             /storage/usr/people/400555/MD/main.cpp
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:
>             In member function 'void CGAL::Regular_triangulation_2<Gt,
>             Tds>::hide_vertex(typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Face_handle, typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Vertex_handle) [with Gt =
>             
> CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >, Tds =
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >]':
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:1082:
>              instantiated from 'typename
>             CGAL::Regular_triangulation_2<Gt, Tds>::Vertex_handle
>             CGAL::Regular_triangulation_2<Gt, Tds>::insert(const
>             typename Gt::Weighted_point_2&, typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Locate_type, typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Face_handle, int) [with Gt =
>             
> CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >, Tds =
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >]'
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:1050:
>              instantiated from 'typename
>             CGAL::Regular_triangulation_2<Gt, Tds>::Vertex_handle
>             CGAL::Regular_triangulation_2<Gt, Tds>::insert(const
>             typename Gt::Weighted_point_2&, typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Face_handle) [with Gt =
>             
> CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >, Tds =
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >]'
>             
> /storage/usr/people/400555/MD/CMDModeling_weighted_Delaunay_CGAL_2D.h:95:
>              instantiated from here
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:1787:
>             error: 'class
>             CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_ds_vertex_base_2<CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > > > > >'
>             has no member named 'is_hidden'
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:1788:
>             error: 'class
>             CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_ds_vertex_base_2<CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > > > > >'
>             has no member named 'set_hidden'
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:
>             In member function 'bool CGAL::Regular_triangulation_2<Gt,
>             Tds>::Hidden_tester::operator()(const typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Finite_vertices_iterator&) [with Gt =
>             
> CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >, Tds =
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >]':
>             /storage/usr/people/400555/CGAL-3.4/include/CGAL/iterator.h:510:
>               instantiated from 'CGAL::Filter_iterator<I,
>             P>::Filter_iterator(I, const P&, I) [with I =
>             
> CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > > >,
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >
>              >::Finite_vertices_iterator, P =
>             
> CGAL::Regular_triangulation_2<CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >,
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >
>              >::Hidden_tester]'
>             /storage/usr/people/400555/CGAL-3.4/include/CGAL/iterator.h:556:
>               instantiated from 'CGAL::Filter_iterator<I, P>
>             CGAL::filter_iterator(I, const P&, I) [with I =
>             
> CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > > >,
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >
>              >::Finite_vertices_iterator, P =
>             
> CGAL::Regular_triangulation_2<CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >,
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >
>              >::Hidden_tester]'
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:1994:
>              instantiated from 'typename
>             CGAL::Regular_triangulation_2<Gt,
>             Tds>::Finite_vertices_iterator
>             CGAL::Regular_triangulation_2<Gt,
>             Tds>::finite_vertices_begin() const [with Gt =
>             
> CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >, Tds =
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >]'
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:2003:
>              instantiated from 'typename
>             CGAL::Regular_triangulation_2<Gt, Tds>::Vertex_handle
>             CGAL::Regular_triangulation_2<Gt, Tds>::finite_vertex()
>             const [with Gt =
>             
> CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >, Tds =
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >]'
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:1066:
>              instantiated from 'typename
>             CGAL::Regular_triangulation_2<Gt, Tds>::Vertex_handle
>             CGAL::Regular_triangulation_2<Gt, Tds>::insert(const
>             typename Gt::Weighted_point_2&, typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Locate_type, typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Face_handle, int) [with Gt =
>             
> CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >, Tds =
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >]'
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:1050:
>              instantiated from 'typename
>             CGAL::Regular_triangulation_2<Gt, Tds>::Vertex_handle
>             CGAL::Regular_triangulation_2<Gt, Tds>::insert(const
>             typename Gt::Weighted_point_2&, typename
>             CGAL::Triangulation_2<CGAL::Weighted_point_mapper_2<Gt>,
>             Tds>::Face_handle) [with Gt =
>             
> CGAL::Regular_triangulation_filtered_traits_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              > >, Tds =
>             
> CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > >]'
>             
> /storage/usr/people/400555/MD/CMDModeling_weighted_Delaunay_CGAL_2D.h:95:
>              instantiated from here
>             
> /storage/usr/people/400555/CGAL-3.4/include/CGAL/Regular_triangulation_2.h:105:
>             error: 'class
>             CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_ds_vertex_base_2<CGAL::Triangulation_data_structure_2<CGAL::Triangulation_vertex_base_with_info_2<int,
>             CGAL::Filtered_kernel<CGAL::Simple_cartesian<double> >,
>             
> CGAL::Triangulation_vertex_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_vertex_base_2<void> > >,
>             
> CGAL::Regular_triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >,
>             
> CGAL::Triangulation_face_base_2<CGAL::Filtered_kernel<CGAL::Simple_cartesian<double>
>              >, CGAL::Triangulation_ds_face_base_2<void> > > > > > >'
>             has no member named 'is_hidden'
>             make[2]: *** [CMakeFiles/main.dir/main.o] Error 1
>
>
>
>
>             On Tue, Aug 11, 2009 at 7:54 PM, Manuel Caroli
>             
> <
>             
> <mailto:>
>             
> <mailto:
>             
> <mailto:>>>
>  wrote:
>
>                400555 wrote:
>
>                    Hello everyone !
>
>                    Is it possible to have weighted Delaunay
>             triangulation with
>                    info with using CGAL ?
>
>                    And am I correct that CGAL regular triangulation of a
>             set of
>                    weighted points gives me weighted Delaunay ? ...but
>             how to add
>                    info to it, I don't know
>
>                sorry I forgot: yes, the CGAL regular triangulations
>             correspond to
>                weighted Delaunay triangulations.
>
>
>                    Can you help me, please?
>
>                    Thank you.
>
>
>                --    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