Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Functions to verify 2-polygons

Subject: CGAL users discussion list

List archive

[cgal-discuss] Functions to verify 2-polygons


Chronological Thread 
  • 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.

Top of Page