CGAL users discussion list

[Hyungon Kim <>]

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);
> > >     */
> > > }

#include    <iostream>
#include    <list>
using namespace std;

#include    <CGAL/basic.h>
#include    <CGAL/Gmpq.h>
#include    <CGAL/Simple_cartesian.h>
#include        <CGAL/MP_Float.h>
#include        <CGAL/Quotient.h>
#include    <CGAL/Bounded_kernel.h>
#include    <CGAL/Nef_polyhedron_2.h>

// CASE1: crashed
typedef CGAL::Simple_cartesian<long>            Kernel;

// CASE2: crashed
// typedef CGAL::Simple_cartesian<double>       Kernel;

// CASE3
// typedef CGAL::Quotient<CGAL::MP_Float>       FT;
// typedef CGAL::Simple_cartesian<FT>       Kernel;

// CASE4
// typedef CGAL::Simple_cartesian<CGAL::Gmpq>   Kernel;

typedef CGAL::Bounded_kernel<Kernel>                    Extended_kernel;
typedef CGAL::Nef_polyhedron_2<Extended_kernel> Nef_polyhedron;
typedef Nef_polyhedron::Point                   Point;

main()
{
        vector<Point>   P1;
        P1.push_back(Point( 37690000,-1962000));
        P1.push_back(Point(-43690000, 4040000));
        P1.push_back(Point(-43690000,12807000));
        P1.push_back(Point(-48690000,12807000));
        P1.push_back(Point(-48690000, 1960000));
        P1.push_back(Point(-42690000,-4038000));
        P1.push_back(Point(-42690000,-14365000));
        P1.push_back(Point(-37690000,-14365000));

        vector<Point>   P2;
        P2.push_back(Point(-48690000,-9460000));
        P2.push_back(Point(-43690000,-9460000));
        P2.push_back(Point(-43690000,-4040000));
        P2.push_back(Point(-37690000, 1962000));
        P2.push_back(Point(-37690000, 9460000));
        P2.push_back(Point(-42690000, 9460000));
        P2.push_back(Point(-42690000, 4038000));
        P2.push_back(Point(-48690000,-1960000));

        Nef_polyhedron  N1(P1.begin(), P1.end(), Nef_polyhedron::EXCLUDED);
        Nef_polyhedron  N2(P2.begin(), P2.end(), Nef_polyhedron::EXCLUDED);
        Nef_polyhedron  N3 = N1+N2;
}