CGAL users discussion list

[Iosif Pinelis <>]

Mariette Yvinec wrote:

> 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....

Thank you Mariette for your response. Such a naive test would be pretty 
bad, since it won't work unless the polygon is first tested for 
simplicity. But the simplicity test in CGAL is said to require Omega(n 
log n) operations (and apparently this lower bound cannot be improved), 
while the convexity can be tested (not naively) in O(n) operations (see 
LEDA or http://arxiv.org/abs/cs.CG/0609141 or 
http://arxiv.org/abs/cs.CG/0701045).

All the more, I would like to find out exactly what algorithms and what 
exact definitions (of polygon simplicity, convexity, etc.) are used in 
such tests in CGAL or, short of that, what the corresponding code is. 
Are those algorithms essentially the same as in LEDA? (LEDA has detailed 
enough descriptions of those algorithms.)

CGAL is open-source, no? I guess this should mean that all of its code 
is accessible. How then could I look at it? Many thanks for any further 
help.

Iosif Pinelis

> > 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