CGAL users discussion list

[Mariette Yvinec <>]

Iosif Pinelis wrote:

> Hi,
>
> I am a mathematician and a complete novice, and don't know C or C++. 
> My _main interest_ at this point is to find out what algorithms are 
> used in CGAL to check such polygon properties as the simplicity and 
> convexity, as well as the rigorous definitions of these notions as 
> assumed in CGAL. 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. As for the polygon convexity, nothing at all is 
> said about the algorithm. In no case I have been able to find rigorous 
> definitions.

For  the simplicity, the sweep algorithm is probably some variant of the 
famous Bentley-Ottmann algorithm
described in all text book on computational geometry.
For convexity, I don't know but it might as well be a naive test on all 
successive polygon angles....

> I guess I could try to read the CGAL C++ code for these algorithms, 
> but I can't find such code either in the CGAL download. I have tried 
> to install CGAL on Windows XP (after installing Visual C++ 2005 
> Express edition and also boost), but the installation fails to 
> complete. 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.
>
> Your help concerning the algorithms (and also the installation) would 
> be very valuable to me. Thank you.
>
> Iosif Pinelis