Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Polygon_2 intersection

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Polygon_2 intersection


Chronological Thread 
  • From: ax487 <>
  • To:
  • Subject: Re: [cgal-discuss] Polygon_2 intersection
  • Date: Wed, 14 Aug 2013 16:39:50 +0200

On 07.08.2013 16:22, Efi Fogel wrote:
> You need to use CGAL::Exact_predicates_exact_constructions_kernel
>
> ____ _ ____ _
> /_____/_) o /__________ __ //
> (____ ( ( ( (_/ (_/-(-'_(/
> _/
>
>
>
>
> On Wed, Aug 7, 2013 at 5:17 PM, ax487
> <>
> wrote:
>
>> Hello all,
>>
>> I am trying to intersect two Polygon_2's using the CGAL::intersection
>> subroutine from CGAL/Boolean_set_operations_2.h.
>> Unfortunately, I get the following error:
>>
>> terminate called after throwing an instance of
>> 'CGAL::Precondition_exception'
>> what(): CGAL ERROR: precondition violation!
>> Expr: ! _predP->is_valid() || comp_f(object, _predP->object) != SMALLER
>> File: /usr/include/CGAL/Multiset.h
>> Line: 2143
>>
>> The error is deep inside the stack (what does that error message mean
>> anyways?), I am not at all familiar with the way that CGAL computes the
>> intersection of polygons (could you give me some literature reference)?
>> My Polygon_2 instances are:
>>
>> 0.150000000000000, 0.950000000000000
>> 0.096033821847732, 0.896033821847732
>> 0.150000000000000, 0.850000000000000
>> 0.203966178152268, 0.803966178152268
>> 0.250000000000000, 0.850000000000000
>> 0.300000000000000, 0.900000000000000
>> 0.250000000000000, 0.950000000000000
>> 0.200000000000000, 1.000000000000000
>>
>> and
>>
>> 0.150000000000000, 0.950000000000000
>> 0.037954613459116, 0.945576109694670
>> 0.150000000000000, 0.850000000000000
>> 0.200000000000000, 0.800000000000000
>> 0.250000000000000, 0.850000000000000
>> 0.300000000000000, 0.900000000000000
>> 0.250000000000000, 0.950000000000000
>> 0.200000000000000, 1.000000000000000
>>
>> I am using the CGAL::Exact_predicates_inexact_constructions_kernel and
>> CGAL 4.2. Could anyone explain to me what is going on and how I can get
>> this subroutine to work properly?
>>
>> ax487
>>
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>
>>
>>

Thank you for your help so far; after porting to the different kernel
everything seems to work fine. However, I would still be interested to
know how the intersection algorithm is implemented and what its
complexity is. The kernel that you recommend uses exact arithmetic. This
seems to have some rather problematic impact on the overall performance
of my application. Is there any way of making everything work with
floating point arithmetic or any other way to improve the performance?

ax487



Archive powered by MHonArc 2.6.18.

Top of Page