CGAL users discussion list

[Ben Supnik <>]

Hi,

Just my 0.02...you can approach the problem of precision vs. performance 
in 3 ways:

1. Use an inexact kernel and pray, as you have proposed.

2. Use something like a lazy kernel, as the CGAL developers have 
suggested.  (BTW, I think that dev assert may indicate an uninitialized 
variable somewhere...it looks vaguely familiar to me.)

3. Rewrite your algorithms to take advantage of the things CGAL does 
well...when using exact algos and CGAL, the time complexity of the 
library is near ideal, but the constant factor for exact math is expensive.

I have tried all 3 of these for my own code, and can say from 
experience: if you're going to be working on your code for a while, 
choices 2 and 3 are preferable to 1.

The problem with 'working around' exact constructions is that it breaks 
the abstraction of the library - the library gives you a clean set of 
operations that 'always work', but it makes no guarantees about wen they 
'sometimes work' for inexact math....thus it will be a lot harder to 
guarantee that the code works in all cases with technique 1.

cheers
Ben

T.vanLankveld wrote:
> I have tried Exact_predicates_exact_kernel, in which case no errors occur,
> but the program does become too slow.
>
>
> However, I have found another way around the problem: these errors seem to
> only occur when the polygons A and B share an edge. Therefore, before doing
> a boolean operation, I remove each duplicate edge by creating a helper
> polygon that covers the edge and subtracting it from A (I keep track the
> part of the helper polygon that was part of polygon A).
>
>
> an example for symmetric difference is:
> "
> void symmetric_difference(Polygon_set_2& A, const Polygon_set_2& B) {
>         Polygon_set_2 toRemove;
>
>         Arrangement_2 AA = A.arrangement();
>         for (Arrangement_2::Edge_iterator it = AA.edges_begin(); it !=
> AA.edges_end(); ++it)
>                 if (contains(B, *it)) {
>                         Point_2 s = it->source()->point(), t = 
> it->target()->point();
>
>                         Polygon_2 bar;
>                         Vector_2 along(s, t);
>                         along= 0.05 * (along/ 
> CGAL::sqrt(along.squared_length()));
>                         Vector_2 perp = along.perpendicular(CGAL::CLOCKWISE);
>
>                         bar.push_back(s-along-perp);
>                         bar.push_back(s-along+perp);
>                         bar.push_back(t+along+perp);
>                         bar.push_back(t+along-perp);
>
>                         Polygon_set_2 rem(bar);
>                         rem.difference(A);
>                         rem.difference(B);
>                         toRemove.join(rem);
>
>                         A.join(bar);
>                 }
>
>         A.symmetric_difference(B);
>         A.difference(toRemove);
> }
> "
>
> Even though toRemove shares a number of edges with A^B, this does not
> produce errors.
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Boolean-set-operation-assertion-tp3396262p3397095.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://www.x-plane.com/blog/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: