CGAL users discussion list

[Roger House <>]

I'm looking for some CGAL functions to verify 2-polygons, and I've not been
able to find what I need.  Any help will be appreciated.

Figure 1:  (0,0) (2,0) (2,1) (0,1) is a rectangle which CGAD regards as a
simple polygon, fit for more or less any use.

Figure 2:  (0,0) (2,0) (2,1) (1,0) (0,1) defines an object which looks like
two triangles sharing a vertex (1,0); but they don't really because 
(0,0)-(2,0)
is an edge but (0,0)-(1,0) and (1,0)-(2,0) are not.  This is not a simple
polygon by CGAL's definition which is found on p889 of the reference manual:

   "A polygon is simple if edges don't intersect, except
   consecutive edges, which intersect in their common vertex."

However, the waters get muddied somewhat on p1076 where a figure is shown
like figure 2 and the figure is said to be simple, but not strictly 
simple.  This
seems to be an unfortunate distinction because the function is_simple says
this polygon is not simple.  It seems that is_simple checks for strict
simplicity, not plain old simplicity.  

Figure 3:  (0,0) (2,0) (2,1) (0,-1) clearly isn't any kind of simple since
the edges (0,0)-(2,0) and (2,1)-(0,-1) intersect in the middle.  I have 
seen
such figures called self-intersecting, but on p900 the function is_simple_2
is described like this:

   "The function is_simple_2 computes if a polygon is simple,
   that is, does not self-intersect."

So the non-strict simplicity of figure 2 is called self-intersection here,
which more or less makes that term unavailable for figure 3.  

Here's a function I hope that CGAL provides:  Check a polygon to make sure
that case 3 does not happen, but allow case 2.

Actually, what I really want is this:  Given a sequence of points which
purportedly is the outer boundary of a polygon, and given a collection of
sequences of points which are purportedly holes in the polygon, verify that
the outer boundary and the holes actually form a valid polygon-with-holes
which CGAL boolean operations will accept.

Thank you for considering this issue.

Roger House
Software Developer