CGAL users discussion list

[Efraim Fogel <>]

Polygon_set_2 has a member function is_valid(). We are working on
providing well defined and documented means to test the validity of
polygons and polygons with holes.

There are some undocumented functions that do that (take a look at
/Boolean_set_operations_2/Gps_polygon_validation.h), but their API is
likely to change.

Roger House wrote:
> Thank you very much for this information.  I added vertex (2,4) to the
> top edge of the square,
> and, indeed, everything worked fine.
>
> Is there a Polygon_with_holes_2  function that I can call to check if
> a polygon is well-formed?
> I have not seen one in the User and Reference Manual, and when I look
> at the source code I
> quickly become confused.  Despite the detail and length of the manual,
> it seems that there are
> very useful functions which it doesn't mention and which I am unable
> to determine how to use.
> Any help will be appreciated.
>
> Roger House
>
> Efraim Fogel wrote:
>> This is not a bug. The polygon with holes you generate is invalid.
>>
>> If you want to generate a valid polygon with holes with identical
>> geometry, in this case you must compute the difference between the
>> polygon outer boundary and the hole.
>>
>> It is not completely your fault though. The function add_hole() has a
>> precondition below, which is currently missing from the documentation,
>> or at least vague. The code you attach violates the precondition.
>>
>> The boundary of a hole and the outer boundary of the polygon with holes
>> must not cross. Moreover, they must not intersect, except for at
>> vertices.
>>
>> If you add the vertex (2,4) to the outer boundary, everything works
>> fine.
>>
>> Roger House wrote:
>>  
>>> 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
>>>       


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