CGAL users discussion list

[Dmitriy Morozov <>]

Wow, that's one hell of a bug. I guess I'll wait till ArchLinux upgrades to 4.8.3, but this is very good to know. Thanks.

On Thu, Dec 19, 2013 at 9:38 PM, Guillaume Damiand <> wrote:

Le 20/12/2013 05:16, Dmitriy Morozov a écrit :

Just tried it on a Mac. No errors, and number_of_vertices() returns 10000, both with and without info. Very strange.

There  is a bug in g++ 4.8 (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800).

You need to update your libstdc++.

Guillaume

On Thu, Dec 19, 2013 at 8:10 PM, Dmitriy Morozov <> wrote:

I've added srand(0). The behavior is reproducible every time. In fact, with this seed, it suffices to insert only 10000 points.

If I drop the info part (i.e., just do Delaunay_triangulation_3<K>), everything works great (and initialization with range, in particular). The only catch is that the number_of_vertices() reports 9932, rather than 10000. (This is a surprise to me, is this the expected behavior?)

I'm doing this on Linux. The compiler is GCC 4.8.2, but I get the same error with CLang 3.3.

gdb backtrace follows, in case it helps:

#0  0x0000000000438bb7 in CGAL::CartesianKernelFunctors::Less_x_3<CGAL::internal::Static_filters<CGAL::Filtered_kernel_base<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double, CGAL::Epick>, CGAL::Epick> >, true> >::operator() (this=0x7fffffffd6a0, p=..., q=...)

    at /usr/include/CGAL/Cartesian/function_objects.h:3777  

#1  0x0000000000433967 in CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*>::Less_x_3::operator() (this=0x7fffffffd6a0, 

    p=673369, q=4713449849867993088) at /usr/include/CGAL/Spatial_sort_traits_adapter_3.h:55

#2  0x0000000000430073 in CGAL::internal::Hilbert_cmp_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*>, 0, false>::operator()  

    (this=0x7fffffffd6f0, p=@0x185fc68: 673369, q=@0x18a28e0: 4713449849867993088) at /usr/include/CGAL/Hilbert_sort_median_3.h:57

#3  0x00000000004346ae in CGAL::internal::Hilbert_cmp_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*>, 0, true>::operator() (

    this=0x7fffffffd710, p=@0x18a28e0: 4713449849867993088, q=@0x185fc68: 673369) at /usr/include/CGAL/Hilbert_sort_median_3.h:43  

#4  0x0000000000434939 in std::__unguarded_partition<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > >, long, CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::Cmp<0, true> > (__first=4713449849867993088, __last=451862, 

    __pivot=@0x185fc68: 673369, __comp=...) at /usr/include/c++/4.8.2/bits/stl_algo.h:2263  

#5  0x0000000000431a15 in std::__unguarded_partition_pivot<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > >, CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::Cmp<0, true> > (__first=673369, __last=451862, __comp=...)

    at /usr/include/c++/4.8.2/bits/stl_algo.h:2296  

#6  0x000000000042bd27 in std::__introselect<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > >, long, CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::Cmp<0, true> > (__first=673369, __nth=673369, __last=451862, 

    __depth_limit=2, __comp=...) at /usr/include/c++/4.8.2/bits/stl_algo.h:2394  

#7  0x0000000000427a32 in std::nth_element<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > >, CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::Cmp<0, true> > (__first=67816, __nth=673369, __last=451862, __comp=...)

    at /usr/include/c++/4.8.2/bits/stl_algo.h:5417  

#8  0x00000000004230a7 in CGAL::internal::hilbert_split<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > >, CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::Cmp<0, true> > (begin=67816, end=451862, cmp=...)

    at /usr/include/CGAL/Hilbert_sort_base.h:38 

#9  0x0000000000423bd8 in CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::sort<1, false, true, true, __gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > > > (this=0x7fffffffe0c0, begin=427480, end=983157)

    at /usr/include/CGAL/Hilbert_sort_median_3.h:122

#10 0x00000000004233bc in CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::sort<2, false, true, true, __gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > > > (this=0x7fffffffe0c0, begin=192203, end=983157)

    at /usr/include/CGAL/Hilbert_sort_median_3.h:132

#11 0x000000000041cca2 in CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::sort<0, false, true, true, __gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > > > (this=0x7fffffffe0c0, begin=556745, end=983157)

    at /usr/include/CGAL/Hilbert_sort_median_3.h:132

#12 0x0000000000419916 in CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::sort<0, false, false, false, __gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > > > (this=0x7fffffffe0c0, begin=234690, end=271534)

    at /usr/include/CGAL/Hilbert_sort_median_3.h:128

#13 0x000000000041d29e in CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::sort<2, true, true, false, __gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > > > (this=0x7fffffffe0c0, begin=944620, end=4713449849867993088)

    at /usr/include/CGAL/Hilbert_sort_median_3.h:130

#14 0x0000000000419996 in CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::sort<0, false, false, false, __gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > > > (this=0x7fffffffe0c0, begin=763473, end=4713449849867993088)

    at /usr/include/CGAL/Hilbert_sort_median_3.h:132

#15 0x00000000004159e5 in CGAL::Hilbert_sort_median_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> >::operator()<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > > > (this=0x7fffffffe0c0, begin=763473, end=4713449849867993088)

    at /usr/include/CGAL/Hilbert_sort_median_3.h:138

#16 0x000000000041299e in CGAL::Multiscale_sort<CGAL::Hilbert_sort_3<CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*>, CGAL::Hilbert_policy<CGAL::Median> > >::operator()<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > > > (this=0x7fffffffe0c0, begin=25905,  

    end=4713449849867993088) at /usr/include/CGAL/Multiscale_sort.h:52

#17 0x0000000000410c79 in CGAL::internal::spatial_sort<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > >, CGAL::Hilbert_policy<CGAL::Median>, CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> > (begin=25905, end=4713449849867993088, k=..., 

---Type <return> to continue, or q <return> to quit---

    threshold_hilbert=8, threshold_multiscale=64, ratio=0.125) at /usr/include/CGAL/spatial_sort.h:81

#18 0x000000000040e8d6 in CGAL::spatial_sort<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > >, CGAL::Hilbert_policy<CGAL::Median>, CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> > (begin=25905, end=4713449849867993088, k=..., policy=..., 

    threshold_hilbert=0, threshold_multiscale=0, ratio=0) at /usr/include/CGAL/spatial_sort.h:122

#19 0x000000000040bfc9 in CGAL::spatial_sort<__gnu_cxx::__normal_iterator<long*, std::vector<long, std::allocator<long> > >, CGAL::Spatial_sort_traits_adapter_3<CGAL::Epick, CGAL::Point_3<CGAL::Epick>*> > (begin=25905, end=4713449849867993088, k=..., threshold_hilbert=0, threshold_multiscale=0, ratio=0)

    at /usr/include/CGAL/spatial_sort.h:165

#20 0x000000000040918c in CGAL::Delaunay_triangulation_3<CGAL::Epick, CGAL::Triangulation_data_structure_3<CGAL::Triangulation_vertex_base_with_info_3<unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> > >, CGAL::Triangulation_ds_cell_base_3<void> >, CGAL::Default>::insert_with_info<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int>, __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int> > > > > (

    this=0x7fffffffe3c0, first=..., last=...) at /usr/include/CGAL/Delaunay_triangulation_3.h:281

#21 0x0000000000407b55 in CGAL::Delaunay_triangulation_3<CGAL::Epick, CGAL::Triangulation_data_structure_3<CGAL::Triangulation_vertex_base_with_info_3<unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> > >, CGAL::Triangulation_ds_cell_base_3<void> >, CGAL::Default>::insert<__gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int> > > > > (this=0x7fffffffe3c0, first=..., last=...)

    at /usr/include/CGAL/Delaunay_triangulation_3.h:307

#22 0x0000000000405d57 in CGAL::Delaunay_triangulation_3<CGAL::Epick, CGAL::Triangulation_data_structure_3<CGAL::Triangulation_vertex_base_with_info_3<unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> > >, CGAL::Triangulation_ds_cell_base_3<void> >, CGAL::Default>::Delaunay_triangulation_3<__gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, unsigned int> > > > > (this=0x7fffffffe3c0, first=..., last=..., gt=...)

    at /usr/include/CGAL/Delaunay_triangulation_3.h:219

#23 0x000000000040216b in main () at test-info.cpp:23

On Thu, Dec 19, 2013 at 2:54 PM, Sebastien Loriot (GeometryFactory) <> wrote:

Everything works fine here. Does it crashes at every run?
If no it would help to get the random seed.

Have you tried to run it without the info
(using the insert by range without the info)?

what is your platform?

Sebastien.

On 12/19/2013 10:57 PM, Dmitriy Morozov wrote:

Hi,

I'm trying to construct a Delaunay triangulation where each vertex
stores its own index. I copied the example from the CGAL documentation,
except I've increased the number of points from 6 to 10^6. The code
(attached) segfaults with CGAL 4.3 during the spatial sort (I insert the
range of points in the constructor). I can work around the problem by
inserting points one by one, but that, of course, sacrifices efficiency.

Does anyone have any idea what's going on and whether I could somehow
fix this?

Thanks.
Dmitriy

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

-- 
===================================================================
Guillaume DAMIAND

CNRS, LIRIS  UMR 5205
Université Claude Bernard
Bâtiment Nautibus (710)
43 Boulevard du 11 Novembre 1918
69622 Villeurbanne Cedex (France)
-------------------------------------------------------------------
Phone: +33 (0)4.72.43.26.62               Fax: +33 (0)4.72.43.15.36
Mail: 
===================================================================