Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Problems with Minkowski sums

Subject: CGAL users discussion list

List archive

[cgal-discuss] Problems with Minkowski sums


Chronological Thread 
  • From: <>
  • To:
  • Subject: [cgal-discuss] Problems with Minkowski sums
  • Date: Mon, 2 Nov 2009 23:18:57 +0100 (CET)
Hi,

I get the following error when I try to do the minkowski sum of two non-convex
polygons:

CGAL error: precondition violation!
Expr: nodeP != NULL
File: C:\Program Files\CGAL-3.3.1\include\CGAL/Multiset.h
Line: 296

Does anybody have an idea about the reason why this is happening?

Thanks.

Cláudio Alves


PS:

The stack trace looks as follows:



msvcp90d.dll!std::_Debug_message(const wchar_t * message=0x661c2818,
const wchar_t * file=0x661c19d0, unsigned int line=1094) Line 24 C++

msvcp90d.dll!std::_Debug_pointer<tm>(const tm * _First=0x00000000,
const wchar_t * _File=0x661c19d0, unsigned int _Line=1094) Line 1539 + 0x12
bytes C++


msvcp90d.dll!std::basic_string<char,std::char_traits<char>,std::allocator<char>
>::assign(const char * _Ptr=0x00000000) Line 1094 + 0x13 bytes C++


msvcp90d.dll!std::basic_string<char,std::char_traits<char>,std::allocator<char>
>::basic_string<char,std::char_traits<char>,std::allocator<char> >(const char
>*
_Ptr=0x00000000) Line 664 C++

nest.exe!CGAL::precondition_fail(const char * expr=0x00558fb0, const
char * file=0x00558e44, int line=296, const char * msg=0x00000000) Line 138 +
0x17 bytes C++


nest.exe!CGAL::Multiset<CGAL::Sweep_line_subcurve<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> > >
*,CGAL::Status_line_curve_less_functor<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,CGAL::Sweep_line_subcurve<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> > > >,std::allocator<int> >::iterator::operator++() Line 298 C++


nest.exe!?_sort_left_curves@?$Basic_sweep_line_2@V?$Arr_labeled_traits_2@V?$Arr_segment_traits_2@U?$Cartesian@VGmpq@CGAL@@@CGAL@@@CGAL@@@CGAL@@V?$Arr_construction_visitor@V?$Arr_labeled_traits_2@V?$Arr_segment_traits_2@U?$Cartes@$$Fe2dab050da84ac51abdf5e5fd2f5e280()
Line 678 + 0x8 bytes C++

nest.exe! ?? :: ?? ::_handle_left_curves() Line 266 C++

nest.exe! ?? :: ?? ::_sweep() Line 398 C++

nest.exe!??$sweep@V?$_Iterator@$0A@@?$list@VX_monotone_curve_2@?$Arr_labeled_traits_2@V?$Arr_segment_traits_2@U?$Cartesian@VGmpq@CGAL@@@CGAL@@@CGAL@@@CGAL@@V?$allocator@VX_monotone_curve_2@?$Arr_labeled_traits_2@V?$Arr_segment_t@$$F2483155f95bd566b5869ff12d3ef8768(std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* curves_begin = 0x00128C28,
std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* curves_end = 0x00128C1C) Line 228
> >
C++


nest.exe!CGAL::Arr_construction<CGAL::Arrangement_2<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,CGAL::Arr_face_extended_dcel<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,int,CGAL::Arr_vertex_base<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::Point_2>,CGAL::Arr_halfedge_base<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2>,CGAL::Arr_face_base> >
>::insert_x_curves<std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>
>(std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* begin = 0x00128FDC,
std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* end = 0x00128FD0) Line 125 + 0x74
bytes C++


nest.exe!CGAL::insert_x_monotone_curves<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,CGAL::Arr_face_extended_dcel<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,int,CGAL::Arr_vertex_base<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::Point_2>,CGAL::Arr_halfedge_base<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2>,CGAL::Arr_face_base>,std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>
>(CGAL::Arrangement_2<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,CGAL::Arr_face_extended_dcel<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,int,CGAL::Arr_vertex_base<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::Point_2>,CGAL::Arr_halfedge_base<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2>,CGAL::Arr_face_base> >& arr = {...},
std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* begin = 0x0012952C,
std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* end = 0x00129520) Line 293 + 0x6b
bytes C++


nest.exe!CGAL::Union_of_cycles_2<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >
>::_construct_arrangement<std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>
>(std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* begin = 0x001297A8,
std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* end = 0x0012979C,
CGAL::Arrangement_2<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,CGAL::Arr_face_extended_dcel<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,int,CGAL::Arr_vertex_base<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::Point_2>,CGAL::Arr_halfedge_base<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2>,CGAL::Arr_face_base> >& arr = {...}) Line 91 C++


nest.exe!CGAL::Union_of_segment_cycles_2<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>,CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > >
>::operator()<std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2>
>::_Iterator<0>,std::back_insert_iterator<std::list<CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > >
>,std::allocator<CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > > > > >
>(std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* begin = 0x00129D8C,
std::list<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
>
>::X_monotone_curve_2,std::allocator<CGAL::Arr_labeled_traits_2<CGAL::Arr_segment_traits_2<CGAL::Cartesian<CGAL::Gmpq>
> >::X_monotone_curve_2> >::_Iterator<0>* end = 0x00129D80,
CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > >& out_bound
>=
{...},
std::back_insert_iterator<std::list<CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > >
>,std::allocator<CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > > > > > holes
= {...}) Line 85 C++


nest.exe!CGAL::Minkowski_sum_by_convolution_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > >
>::operator()<std::back_insert_iterator<std::list<CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > >
>,std::allocator<CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > > > > >
>(CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > >& pgn1 =
{...},
CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > >& pgn2 =
{...},
CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > >& sum_bound
>=
{...},
std::back_insert_iterator<std::list<CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > >
>,std::allocator<CGAL::Polygon_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > > > > >
sum_holes = {...}) Line 334 + 0xa7 bytes C++


nest.exe!CGAL::minkowski_sum_2<CGAL::Cartesian<CGAL::Gmpq>,std::vector<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq>
>,std::allocator<CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > > > >() Line 50 +
0x7a bytes C++
  • [cgal-discuss] Problems with Minkowski sums, claudio, 11/02/2009

Archive powered by MHonArc 2.6.16.

Top of Page