CGAL users discussion list

[Roger House <>]

CGAL seems to have trouble with a polygon which has a hole with a vertex
of the hole on the outer boundary of the polygon.

Specifically, if G is a square with a triangular hole with the top vertex
of the triangle on the top edge of the hole, and R is a rectangle inside
the square, disjoint from the square and the hole, then join(G,R) blows
up.  If the top vertex of the triangle is moved slightly inside the square,
everything works fine.

Below is the output produced by the attached test program.

By the way, using CGAL::Exact_predicates_exact_constructions_kernel still
resulted in a blow up.

Roger House
Software Developer

The following was sent to stderr by CGAL

CGAL warning: check violation!
Expr: is_simple
File: 
c:\users\roghouse\332\build\projects\cgal_eesof\include\cgal\boolean_set_operations_2\gps_polygon_validation.h
Line: 190
Explanation:The polygon is not simple.
CGAL error: precondition violation!
Expr: m_traits->is_valid_2_object()(pgn_with_holes)
File: 
c:\users\roghouse\332\build\projects\cgal_eesof\include\cgal\general_polygon_set_2.h
Line: 207
Explanation:


The following was sent to stdout by edgehole.cpp

Top vertex of triangle hole is inside square:  Works
Square with triangle hole
 { Outer boundary =
 [ 4 vertices: (0 0) (4 0) (4 4) (0 4) ]
  is simple
  is convex
  is counterclockwise
  has area 16

   1 holes:
   Hole #1 =
 [ 3 vertices: (2 3.9) (3 3) (1 3) ]
  is simple
  is convex
  is clockwise
  has area -0.9

 }

Rectangle inside G square
 { Outer boundary =
 [ 4 vertices: (1 1) (3 1) (3 2) (1 2) ]
  is simple
  is convex
  is counterclockwise
  has area 2

   0 holes:
 }

Union of G and R
 { Outer boundary =
 [ 4 vertices: (0 0) (4 0) (4 4) (0 4) ]
  is simple
  is convex
  is counterclockwise
  has area 16

   1 holes:
   Hole #1 =
 [ 3 vertices: (3 3) (1 3) (2 3.9) ]
  is simple
  is convex
  is clockwise
  has area -0.9

 }

Top vertex of triangle hole is on square edge:  Blows up
Square with triangle hole
 { Outer boundary =
 [ 4 vertices: (0 0) (4 0) (4 4) (0 4) ]
  is simple
  is convex
  is counterclockwise
  has area 16

   1 holes:
   Hole #1 =
 [ 3 vertices: (2 4) (3 3) (1 3) ]
  is simple
  is convex
  is clockwise
  has area -1

 }

Rectangle inside G square
 { Outer boundary =
 [ 4 vertices: (1 1) (3 1) (3 2) (1 2) ]
  is simple
  is convex
  is counterclockwise
  has area 2

   0 holes:
 }

EXCEPTION THROWN!
CGAL ERROR: precondition violation!
Expr: m_traits->is_valid_2_object()(pgn_with_holes)
File: 
c:\users\roghouse\332\build\projects\cgal_eesof\include\cgal\general_polygon_set_2.h
Line: 207
Press any nonwhitespace key and Enter to terminate

// edgehole.cpp  --  Demonstration of bug in CGAL:  Hole vertex on outer
//                     boundary of polygon causes blow up 

#include "CGAL\Cartesian.h"
#include "CGAL\Polygon_2.h"
#include <CGAL\Boolean_set_operations_2.h>
#include <CGAL\Polygon_set_2.h>
#include <CGAL\connect_holes.h>
#include <iostream>
#include <list>
#include <cassert>

using namespace std;

typedef CGAL::Cartesian<double>       K;
typedef K::Point_2                    Point;
typedef list<Point>                   Point_list;
typedef CGAL::Polygon_2<K>            Polygon_2;
typedef CGAL::Polygon_set_2<K>        Polygon_set_2;
typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes_2;
typedef list<Polygon_with_holes_2>    Pwh_list_2;


void print_polygon(const Polygon_2 &poly)
{
    Polygon_2::Vertex_const_iterator vit;

    cout << "[ " << poly.size() << " vertices:";
    for (vit = poly.vertices_begin(); vit != poly.vertices_end(); ++vit)
        cout << " (" << *vit << ')';
    cout << " ]" << endl;
}


void print_polygon_info(const Polygon_2 &poly, const string &name, const 
string &desc)
{
    bool isSimple = poly.is_simple();
    bool isConvex = poly.is_convex();
    bool isCCW    = false;
    if (isSimple)
        isCCW = poly.is_counterclockwise_oriented();
    double area = poly.area();

    cout << desc << endl;
    cout << "  ";
    print_polygon(poly);
    cout << "  " << name << " is " << (isSimple ? "" : "not ") << "simple" << 
endl;
    cout << "  " << name << " is " << (isConvex ? "" : "not ") << "convex" << 
endl;
    if (isSimple)
    cout << "  " << name << " is " << (isCCW    ? "counterclockwise" : 
"clockwise") << endl;
    cout << "  " << name << " has area " << area << endl;
    cout << endl;
}


void print_polygon_with_holes(const Polygon_with_holes_2 &pwh)
{
    if (!pwh.is_unbounded())
    {
//      cout << "  { Outer boundary = ";
        cout << "  { ";
        print_polygon_info (pwh.outer_boundary(), "", "Outer boundary = ");
    }
    else
    {
        cout << "  { Unbounded polygon" << endl;
    }

    Polygon_with_holes_2::Hole_const_iterator hit;

    unsigned int k = 1;
    cout << "    " << pwh.number_of_holes() << " holes:" << endl;

    for (hit = pwh.holes_begin(); hit != pwh.holes_end(); ++hit, ++k)
    {
        cout << "    Hole #" << k << " = ";
        print_polygon_info(*hit, "", "");
    }

    cout << "  }" << endl;

}   // end print_polygon_with_holes


void print_polygon_with_holes_info(const Polygon_with_holes_2 &poly, const 
string &name, const string &desc)
{
    cout << desc << endl;
    print_polygon_with_holes(poly);
    cout << endl;
}


void print_list_of_polygons_with_holes_info(const Pwh_list_2 &pwh_list, const 
string &name, const string &desc)
{
    cout << desc << endl;

    Pwh_list_2::const_iterator it;

    for (it = pwh_list.begin();  it !=  pwh_list.end();  ++it)
    {
        print_polygon_with_holes(*it);
    }

    if ( pwh_list.begin() == pwh_list.end())
        cout << "  the list of polygons with holes is empty" << endl;

    cout << endl;
}


void show_bug(Point &top_of_triangle)
{
    Polygon_with_holes_2 G;
    G.outer_boundary().push_back( Point(0, 0) );
    G.outer_boundary().push_back( Point(4, 0) );
    G.outer_boundary().push_back( Point(4, 4) );
    G.outer_boundary().push_back( Point(0, 4) );

    Polygon_2 holeG;
    holeG.push_back( top_of_triangle );
    holeG.push_back( Point(3, 3) );
    holeG.push_back( Point(1, 3) );

    G.add_hole(holeG);

    Polygon_with_holes_2 R;
    R.outer_boundary().push_back( Point(1, 1) );
    R.outer_boundary().push_back( Point(3, 1) );
    R.outer_boundary().push_back( Point(3, 2) );
    R.outer_boundary().push_back( Point(1, 2) );

    print_polygon_with_holes_info(G, "G", "Square with triangle hole");
    print_polygon_with_holes_info(R, "R", "Rectangle inside G square");

    Polygon_with_holes_2 unionGandR;
    bool disjoint = !CGAL::join(G, R, unionGandR);
    assert(!disjoint);
    print_polygon_with_holes_info(unionGandR, "unionGandR", "Union of G and 
R");

}   //  end show_bug


int main()
{
    try
    { 
        cout << "Top vertex of triangle hole is inside square:  Works" << 
endl;
        show_bug( Point(2, 3.9) );  // This will work
        cout << "Top vertex of triangle hole is on square edge:  Blows up" << 
endl;
        show_bug( Point(2, 4  ) );  // This blows up
    }
    catch (exception& e)
    {
        cout << "EXCEPTION THROWN!" << endl;
        cout << e.what() << endl;
    }

    cout << "Press any nonwhitespace key and Enter to terminate"  << endl;

    string c;
    cin >> c;

}   // end main

// end edgehole.cpp