CGAL users discussion list

[Iosif Pinelis <>]

Andreas Fabri wrote:

> Hello,
>
> With a sweep you can detect intersections of line segments.
> When the line segments of a polygon intersect it is not simple.
>
> For convexity: find the leftmost point of the polygon and
> walk along the polygon. On the upper side you should always
> progress in x-direction, and three consecutive vertices should
> always make a right turn.
>
> hope this helps. You can't expect a PhD thesis to describe the above.

Thanks Andreas. My question was not how one could test the polygon 
simplicity or convexity. Rather, it was this: specifically in CGAL, 
exactly what definitions of the polygon simplicity, convexity, etc. are 
assumed and what corresponding algorithms are used?

There are many disparate definitions of these notions in the literature 
and on the web, most of them informal and some even contradictory in 
themselves; and oftentimes (perhaps more often than not) these terms are 
used without any definition. It should not then be very surprising that 
claims about these notions in a number of places are simply incorrect. I 
think rigorous definitions are important, because otherwise we end up 
with "definitions" like this: "a polygon is convex if and only if my own 
test says it is so". Such practice would result in as many definitions 
of a notion as there are tests for it! Unfortunately, this or something 
pretty close to this kind of practice seems to be the case today.

Concerning your particular suggestions, one may ask: how do you define 
the notion of polygon convexity (say) or even that of a polygon itself? 
And how do you define the "upper side" of a general (not necessarily 
simple) polygon? And what about a lower side, etc.?

But, again, my questions are about CGAL specifically. Thanks again for 
any further help concerning CGAL.

Iosif Pinelis

> Iosif Pinelis wrote:
>
> > 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