CGAL users discussion list

Le Mar 6 mars 2007 15:36, Iosif Pinelis a écrit :
>>> 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.

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

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.

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

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

>>> In no case I have been able to find
>>> rigorous definitions.

The simplicity definition is at the beginning of the polygon section of
the manual, and the convexity definition is the usual one.

> But the simplicity test in CGAL is said to require Omega(n
> log n) operations (and apparently this lower bound cannot be improved),

Indeed, it 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).

It is so in CGAL too, as you can see from  the above description.

> Are those algorithms essentially the same as in LEDA? (LEDA has detailed
> enough descriptions of those algorithms.)

You should at least give a link to these descriptions, if you want an answer.

> CGAL is open-source, no?

Yes, it is indeed.

> I guess this should mean that all of its code
> is accessible.

Indeed.

> 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/
-- 
Camille Wormser