CGAL users discussion list

[Iosif Pinelis <>]

 wrote:

> The CGAL definition of simplicity is the usual one. You have it in the
> manual:
>
> "A polygon is a closed chain of edges. Several algorithms are available
> for polygons. For some of those algorithms, it is necessary that the
> polygon is simple. A polygon is simple if edges don't intersect, except
> consecutive edges, which intersect in their common vertex."
>  
Thanks a lot for this post. This helps.

> It could be more precise by telling you that any degenerate edge
> (zero-length edge) is discarded first.
>
> The definition of convexity seems to be missing from the manual. However,
> there again, it is the usual one:
>
> non-simple polygons are not convex, a simple polygon is convex if the
> union of its bounded side and its edges is convex.
>
>  
Sounds great.

> > > > I have been able to find online only extremely brief
> > > > descriptions of the corresponding pieces of code. As for the polygon
> > > > simplicity, it is said there that a sweep algorithm is used, but no
> > > > details are given.
> > > >        
>
> I don't see why you would need more in the manual. If you need more, a
> quite precise description is present at the beginning of the
> Polygon_2_simplicity.h file, and you have the code itself.
>  
This touches perhaps on the very cause of my problems. As I wrote 
before, I have tried to install CGAL on Windows XP (after installing 
Visual C++ 2005 Express edition (version 8.0) and also boost) using the 
CGAL Windows Installer (which says it assumes Visual C++ 2003 (version 
7.1)), and the installation fails to complete, perhaps not surprisingly. 
A CGAL installation manual says that only Visual C++ 2003 (version 7.1) 
is supported by CGAL, but 7.1 does not appear to be available any more, 
as it has been replaced by 8.0 by Microsoft.

Anyway, now I have many .h files in my CGAL download, but I can't find 
Polygon_2_simplicity.h anywhere, even with the Google desktop search.

>  
>
> > > > As for the polygon convexity, nothing at all is
> > > > said about the algorithm.
> > > >        
>
> Indeed. It may be interesting to present it. Basically, it checks the
> local convexity (by successive orientation tests) and checks that there is
> not more than two changes of lexicographic order along the polygon, which
> ensures simplicity (given the local convexity, of course).
>
>  
This gives me a pretty clear idea about the algorithm. Questions I still 
have here:

  1. Just to be sure, do you mean by the local convexity that all the
     2-by-2 determinants (y_{i+1}-y_i) (x_i-x_{i-1}) - (x_{i+1}-x_i)
     (y_i-y_{i-1}) formed by the coordinates of the adjacent
     edge-vectors have the same sign? Here (x_i,y_i) is the ith vertex.
  2. Do you allow any of these determinants to be zero?
  3. The _biggest_ question remaining now: is there a rigorous proof
     that the CGAL convexity test exactly corresponds to the definition
     that you gave?

> > How then could I look at it?
> >    
>
> I guess downloading it would be a step in the right direction. It is
> available at
> http://cgal.org/download/
>  
Alas, as I said, it hasn't worked for me. If it's too difficult to fix 
my installation problem, is it possible to e-mail me copies of 
Polygon_2_simplicity.h and, I'd guess, Polygon_2_convexity.h or whatever 
-- containing a description of the convexity test and/or the 
corresponding code?

Many thanks for your patience with me.

Iosif Pinelis