CGAL users discussion list

[Efi Fogel <>]

On Wed, Aug 14, 2013 at 5:39 PM, ax487 <> wrote:

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

The algorithm used is a variation of the plane-sweep algorithmic framework. It's complexity is O(k log n) where n is the complexity of the input and k is the complexity of the output.
 

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?

You must use an exact-predicate and exact-construction kernel.

There are always way to expedite things. The first that comes to mind when using an exact kernel is decreasing the bit lengths of the input numbers by truncation. Subsection 4.2.2 (A Note on the Input Precision) of the book "CGAL Arrangements and Their Applications" explains this. Here you can find links to all examples and code excerpts listed in this book. The header numerical_cast.h may come in handy.

ax487

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