CGAL users discussion list

[Roger House <>]

The function connect_holes seems to be failing in certain situations.  
Specifically, if P is a square, and a diamond shape Q is subtracted from
it, resulting in a square with a diamond hole, then connect_holes returns
a small triangle rather than the expected output.  

Below is the output produced by the attached program.

Roger House
Software Developer

A square
 [ 4 vertices: (-1 -1) (1 -1) (1 1) (-1 1) ]
 P is simple
 P is convex
 P is counterclockwise
 P has area 4

A diamond inside the square P above
 [ 4 vertices: (-1 0) (0 -1) (1 0) (0 1) ]
 Q is simple
 Q is convex
 Q is counterclockwise
 Q has area 2

Difference P - Q above
 { Outer boundary = [ 8 vertices: (-1 -1) (0 -1) (1 -1) (1 0) (1 1) (0 
1) (-1 1) (-1 0) ]
   1 holes:
   Hole #1 = [ 4 vertices: (1 0) (0 -1) (-1 0) (0 1) ]
 }

Same as above
 { Outer boundary = [ 8 vertices: (-1 -1) (0 -1) (1 -1) (1 0) (1 1) (0 
1) (-1 1) (-1 0) ]
   1 holes:
   Hole #1 = [ 4 vertices: (1 0) (0 -1) (-1 0) (0 1) ]
 }

Number of elements in pointList is 3

Square with diamond hole as a sequence of points
 [ 3 vertices: (-1 -1) (0 -1) (-1 0) ]
 squareWithNoHoles is simple
 squareWithNoHoles is convex
 squareWithNoHoles is counterclockwise
 squareWithNoHoles has area 0.5

***** connect_holes seems to have a bug *****

// cholebug.cpp  --  Demonstration of a bug in the CGAL connect_holes function

#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 displayPolyInfo(
    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 = ";
        print_polygon (pwh.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(*hit);
    }

    cout << "  }" << endl;

}   // end print_polygon_with_holes


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


void displayListOfPolyWithHolesInfo(
    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);
    }

    cout << endl;
}


int main()
{
    Point pointsP[] = {Point(-1, -1), Point(1, -1), Point(1, 1), Point(-1, 
1)};
    Polygon_2 P(pointsP, pointsP+4);
    displayPolyInfo(P, "P", "A square");

    Point pointsQ[] = {Point(-1, 0), Point(0, -1), Point(1, 0), Point(0, 1)};
    Polygon_2 Q(pointsQ, pointsQ+4);
    displayPolyInfo(Q, "Q", "A diamond inside the square P above");

    // Difference P - Q
    Pwh_list_2 differencePminusQ;
    CGAL::difference(P, Q, back_inserter(differencePminusQ));
    displayListOfPolyWithHolesInfo(differencePminusQ, "differencePminusQ", 
        "Difference P - Q above");

    // Now connect holes of the diamond hole to the square outer boundary

    Polygon_with_holes_2 squareWithDiamondHole = differencePminusQ.front();
    displayPolyWithHolesInfo(squareWithDiamondHole, "squareWithDiamondHole", 
        "Same as above");

    Point_list pointList;
    connect_holes(squareWithDiamondHole, back_inserter(pointList));
    cout << "Number of elements in pointList is " << pointList.size() << endl;
    cout << endl;
    Polygon_2 squareWithNoHoles(pointList.begin(), pointList.end());
    displayPolyInfo(squareWithNoHoles, "squareWithNoHoles", 
        "Square with diamond hole as a sequence of points");

    cout << "***** connect_holes seems to have a bug *****"  << endl;
    cout << endl;

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


    string c;
    cin >> c;
}

// end cholebug.cpp