CGAL users discussion list

[Efi Fogel <>]

 wrote:

> Thank you. It worked! However I have a problem I don't seem to be  
> able to work around. Using  
> Exact_predicates_exact_constructions_kernel slows don't the code so  
> much that it becomes almost unusable. Is there a way around this? I  
> don't really care for accuracy. What I need is the code to not crash/ 
> fail. I would prefer if I could use double for the intersection test  
> but that it didn't give assertion failures in the degenerate cases.  
> E.g. it would be ok if the code just chose not to treat those cases.

We rely on an exact number type not only to produce exact results but 
also to make the code robust. Since our algorithms construct new 
objects, e.g., intersection points, both predicates and constructions 
must be exact. You can still do several experiments to try and expedite 
your code:
1. Try to use different combinations of (exact) number types and 
kernels. If you use a cartesian kernel you need a field number type (one 
that supports exact add, sub, mul, and div). In general you have the 
internal number type CGAL::Quotient<CGAL::MP_float. CGAL::Gmpq does a 
good job and the leda library also offers one. In addition you can use 
filters and such. In general these are constructs that attempt to use 
the exact number type only when necessary, and an alternative non-exact 
number type otherwise. Read for example the "Number Type Support" chapter.
2. If you can allow yourself to slighly alter the input, and in your 
case it sounds that you can, try to lessen the number of bits used to 
represent the coordinates of the input. For example, provide the 
numerator and denominator explicitly as integers. For example, instead 
of a floating point x, provide round(x * 1024), 1024.

> On  20 Jan 2007, at 10:30 AM, Efi Fogel wrote:
>
> > Sounds like a classic case of  limited precision problem.
> > Try to use an exact number type. For example:
> >
> > #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
> >
> > typedef CGAL::Exact_predicates_exact_constructions_kernel  Kernel;
> >
> > Erik Engheim wrote:
> >
> > > I am using the Polygon_2 class. But I don't seem to get  
> > > intersection  tests with "do_intersect" from  
> > > "Boolean_set_operations_2.h" to work  properly. Most of the time  it 
> > > works but it doesn't seem to handle  degenerate cases. In my  case 
> > > when the corner of a polygon intersects  a line segment on  another 
> > > polygon.
> > >
> > > I get the following assertion failure:
> > > CGAL error: assertion violation!
> > > Expr: *slIter == curve
> > > File: /Users/Shared/CGAL-3.2.1/include/CGAL/Basic_sweep_line_2.h
> > > Line: 591
> > >
> > > Sometimes I have gotten this failure:
> > > CGAL error: precondition violation!
> > > Expr: Segment_assertions::_assert_is_point_on (p, cv,   
> > > Has_exact_division()) && compare_xy(cv.left(), p) == SMALLER &&   
> > > compare_xy(cv.right(), p) == LARGER
> > > File: /Users/Shared/CGAL-3.2.1/include/CGAL/Arr_segment_traits_2.h
> > > Line: 730
> > >
> > > The program below demonstrates the problem. When run I get the  
> > > first  assertion failure. Any suggestions to what is causing this?  
> > > Am I  using the library wrong or is this a bug in CGAL?
> > >
> > > Cheers,
> > > Erik
> > >
> > > #include <CGAL/Cartesian.h>
> > > #include <CGAL/basic.h>
> > > #include <CGAL/Point_2.h>
> > >
> > > #include <CGAL/Boolean_set_operations_2.h>
> > >
> > > #include <iostream>
> > >
> > > using namespace std;
> > > using namespace CGAL;
> > >
> > > typedef Cartesian<double> K;
> > > typedef Point_2<K> Point2;
> > > typedef Polygon_2<K> Polygon2;
> > >
> > > int main()
> > > {
> > >   Point2 small[] = {
> > >     Point2(3.0721924234843    , -1.0673205240039),
> > >     Point2(5.067320524004, -0.9278075765157),
> > >     Point2(4.9278075765157, 1.0673205240039),
> > >     Point2(2.9326794759961, 0.9278075765157)};
> > >
> > >   Point2 large[] = {Point2(-3,-3),
> > >                     Point2(3,-3),
> > >                     Point2(3,3),
> > >                     Point2(-3,3)};
> > >
> > >   Polygon2 smallPoly(small, small+4);
> > >   Polygon2 largePoly(large, large+4);
> > >
> > >   cout << "do intersect? " << do_intersect(smallPoly, largePoly)  
> > > <<  endl;
> > >   return 0;
> > > }
--
  ____  _        ____             _
 /_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                        _/