CGAL users discussion list

Le Mer 7 mars 2007 0:25, Iosif Pinelis a écrit :
> 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.

Strange...
You should try downloading the "All the code, but without the manuals"
tar.gz file, then. At least you will have everything.

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

Yes.

>    2. Do you allow any of these determinants to be zero?

Yes. The first time a none zero result is obtained, its sign is recorded.
All other non zero results have then to have the same sign.

>    3. The _biggest_ question remaining now: is there a rigorous proof
>       that the CGAL convexity test exactly corresponds to the definition
>       that you gave?

In my first definition, I forgot to mention the special case of flat
convex polygons, as I mentionned in the next message. Here is a proof:

- in the case of a flat polygons, all orientation tests will be zero. The
result then depends only on the number of changes in the lexicographic
order of vertices. This lexicographic order changes when the order on the
supporting line changes (whatever the direction of the line is). This
concludes the proof for the flat case.

- in the case of non flat polygons, we can assume that three successive
vertices are never aligned (by removing unnecessary vertices), and we have
a non-flat locally convex curve P. If it has no self intersection, it is
convex, and it has exactly 2 changes of lexicographic order. If it has
self intersections, we have to show that there are at least 3 changes of
lexicographic order. Let us call X some intersection point. We can split P
at X into two polygons, P1 and P2. As any polygon, P1 and P2 have at least
2 changes of order each. P is the union of P1 and P2. As such, it has at
least 2 + 2 changes, maybe minus one, in case X is a point with an order
change for both P1 and P2. Hence, we always have at least 3 changes in
case there is an auto intersection. This concludes the proof.

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

I send you that.
-- 
Camille Wormser