CGAL users discussion list

[Andreas Fabri <>]

Hi Hyungon,

It doesn't surprise me that just Gmpq is too slow.

Can you give the following a try:


#include <CGAL/Lazy_exact_nt.h>

typedef CGAL::Simple_cartesian<CGAL::Lazy_exact_nt<CGAL::Gmpq> > Kernel;

It's a numbertype that encloses the floating point coordinates in  floating
point intervals, does interval arithmetic, and only falls back to the
expensive computation using Gmpq if things fail with floating point 
arithmetic.

andreas



Hyungon Kim wrote:
> Hi Andreas,
>
> I tested Nef_polyhedron 2D boolean operation for four kernels with two 
> simple polygons;
> two of them are inexact (long and double) and others exact (MP_Float and 
> Gmpq).
> The cases of MP_float and Gmpq outputs correct polygons, but long and 
> double crashed.
> The problem of MP_float and Gmpq is too slow to use them and make product.
> More than 16 times slow compared to the package using now.
>
> As you can see the attached picture, simple polygons were tested and 
> then just crashed.
> Is there a way to avoid crash with inexact even when the exact output is 
> not necessary?
>
> Thanks,
> Hyungon Kim
>
> Hyungon Kim wrote:
> > Hi Andreas,
> >
> > I think it is not exact construction problem and also not related to 
> > regularization.
> > create_face_objects in Nef2/PM_overlayer.h crashed with example polygons.
> > And even using exact construct also crashed at same place.
> >
> > Thanks,
> > Hyungon Kim
> >
> > Andreas Fabri wrote:
> > > Hello,
> > >
> > >
> > > Both, Nef and the Regularizded Boolean operations need exact 
> > > constructions.
> > >
> > > In order to decide which of the two packages is the better choice 
> > > depends
> > > on your requirements.  Nef does not regularize, that is it can represent
> > > isolated points, unbounded faces, open faces, antennas sticking out, 
> > > etc.
> > >
> > > andreas
> > >
> > >
> > >
> > >  wrote:
> > > > Hi,
> > > >
> > > > Nef_polyhedron_2 boolean operation crushed for some polygons. 
> > > > However, it is
> > > > fine when trying General_polygon_set with same polygons. Should I use
> > > > General_polygon_set instead of Nef_polyhedron_2 even for simple 
> > > > rectilinear
> > > > polygon?
> > > >
> > > > Thanks,
> > > > Hyungon Kim
> > > >
> > > > #include    <iostream>
> > > > #include    <list>
> > > > using namespace std;
> > > >
> > > > #include    <CGAL/basic.h>
> > > > #include    <CGAL/Gmpq.h>
> > > > #include    <CGAL/Simple_cartesian.h>
> > > > #include    <CGAL/connect_holes.h>
> > > > #include    <CGAL/Bounded_kernel.h>
> > > > #include    <CGAL/Nef_polyhedron_2.h>
> > > > #include    <CGAL/Polygon_2.h>
> > > > #include    <CGAL/Polygon_with_holes_2.h>
> > > > #include    <CGAL/Exact_predicates_inexact_constructions_kernel.h>
> > > >
> > > > #include <CGAL/Boolean_set_operations_2.h>
> > > >
> > > > typedef CGAL::Simple_cartesian<double>            cgalKernel;
> > > > typedef CGAL::Bounded_kernel<cgalKernel>        cgalExtKernel;
> > > >
> > > > typedef CGAL::Nef_polyhedron_2<cgalExtKernel>        cgalNefPolyhedron;
> > > >
> > > > typedef cgalNefPolyhedron::Point            cgalPoint2;
> > > > typedef CGAL::Polygon_2<cgalKernel>            cgalPolygon2;
> > > > typedef CGAL::Polygon_with_holes_2<cgalKernel>        
> > > > cgalPolygonWithHoles2;
> > > >
> > > > typedef 
> > > > CGAL::Exact_predicates_inexact_constructions_kernel           
> > > > cgalExtInextKernel;
> > > > typedef cgalExtInextKernel::Point_2                       
> > > > cgalExtPoint2;
> > > > typedef CGAL::Polygon_2<cgalExtInextKernel>                   
> > > > cgalExtPolygon2;
> > > > typedef CGAL::Polygon_with_holes_2<cgalExtInextKernel>               
> > > > cgalExtPolygonWithHoles2;
> > > >
> > > > main()
> > > > {
> > > >     vector<cgalPoint2>    P1;
> > > >     P1.push_back(cgalPoint2(-48690,20167));
> > > >     P1.push_back(cgalPoint2(-48690,1960));
> > > >     P1.push_back(cgalPoint2(-42690,-4038));
> > > >     P1.push_back(cgalPoint2(-42690,-17679));
> > > >     P1.push_back(cgalPoint2(-17677,-42690));
> > > >     P1.push_back(cgalPoint2(17679,-42690));
> > > >     P1.push_back(cgalPoint2(42690,-17677));
> > > >     P1.push_back(cgalPoint2(42690,-4460));
> > > >     P1.push_back(cgalPoint2(37690,-4460));
> > > >     P1.push_back(cgalPoint2(37690,-15613));
> > > >     P1.push_back(cgalPoint2(15611,-37690));
> > > >     P1.push_back(cgalPoint2(-15613,-37690));
> > > >     P1.push_back(cgalPoint2(-37690,-15611));
> > > >     P1.push_back(cgalPoint2(-37690,-1962));
> > > >     P1.push_back(cgalPoint2(-43690,4040));
> > > >     P1.push_back(cgalPoint2(-43690,18103));
> > > >     P1.push_back(cgalPoint2(-18101,43690));
> > > >     P1.push_back(cgalPoint2(18103,43690));
> > > >     P1.push_back(cgalPoint2(43690,18101));
> > > >     P1.push_back(cgalPoint2(43690,7500));
> > > >     P1.push_back(cgalPoint2(78690,7500));
> > > >     P1.push_back(cgalPoint2(78690,12500));
> > > >     P1.push_back(cgalPoint2(48690,12500));
> > > >     P1.push_back(cgalPoint2(48690,20169));
> > > >     P1.push_back(cgalPoint2(20167,48690));
> > > >     P1.push_back(cgalPoint2(-20169,48690));
> > > >
> > > >     vector<cgalPoint2>    P2;
> > > >     P2.push_back(cgalPoint2(-48690,-1960));
> > > >     P2.push_back(cgalPoint2(-48690,-9460));
> > > >     P2.push_back(cgalPoint2(-43690,-9460));
> > > >     P2.push_back(cgalPoint2(-43690,-4040));
> > > >     P2.push_back(cgalPoint2(-37690,1962));
> > > >     P2.push_back(cgalPoint2(-37690,9460));
> > > >     P2.push_back(cgalPoint2(-42690,9460));
> > > >     P2.push_back(cgalPoint2(-42690,4038));
> > > >
> > > >     cgalNefPolyhedron    N1(P1.begin(), P1.end(),
> > > > cgalNefPolyhedron::EXCLUDED);
> > > >     cgalNefPolyhedron    N2(P2.begin(), P2.end(),
> > > > cgalNefPolyhedron::EXCLUDED);
> > > >     cgalNefPolyhedron N3 = N1+N2;
> > > >
> > > >     /*
> > > >     cgalPolygon2    POLY1(P1.begin(), P1.end());
> > > >     cgalPolygon2    POLY2(P2.begin(), P2.end());
> > > >     cgalPolygonWithHoles2    unionR;
> > > >     CGAL::join(POLY1, POLY2, unionR);
> > > >     */
> > > > }
>
>
> ------------------------------------------------------------------------