Subject: CGAL users discussion list
List archive
- From: Roger House <>
- To: CGAL <>
- Subject: [cgal-discuss] Functions to verify 2-polygons
- Date: Thu, 28 Aug 2008 16:04:51 -0700
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
- [cgal-discuss] Functions to verify 2-polygons, Roger House, 08/29/2008
Archive powered by MHonArc 2.6.16.