CGAL users discussion list

[Efraim Fogel <>]

Indeed a bug. It happens when the number of faces of the underlying
arrangement that belongs to the point set is greater than one. We will
post the fix once it's in place, and naturally include it in the next
release.

Roger House wrote:
> 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
>   

-- 
  ____  _        ____             _
 /_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                        _/