mjh@zurich.ai.mit.edu (Mark Hood) (09/29/90)
I am trying to implement the polygon triangulation algorithm described in
the paper "Triangulating Simple Polygons and Equivalent Problems" by
Fournier and Montuno, published in ACM TOG Vol 3 #2 April 1984 p153-174.
It's going well except for Algorithm 3, triangulate_monotone(), which
appears to have some misprints in it.
First of all, the FOR loop in the convex angle case doesn't have an END.
Instead, the following appears:
FOR each of PREV(current), current, NEXT(current) DO
BEGIN
insert other two vertices to form triangle;
and
save = PREV(current);
I am assuming that the ``and'' is supposed to be an END, but perhaps some
other action needs to be done before the end of the loop?
Secondly, after the FOR loop the following appears:
save = PREV(current);
remove current from uni-monotone polygon;
IF current = first THEN current = NEXT(first)
ELSE current = save;
It seems to me that the IF should be:
IF save = start THEN current = NEXT(start)
ELSE current = save;
where ``start'' is the topmost vertex if the monotone chain in on the right,
or bottommost if it is on the left.
I believe this because when triangulate_monotone(first, last) is called,
first and last are not necessarily the topmost or bottommost vertices of the
uni-monotone polygon, and the purpose of this IF appears to be to ensure
that the algorithm doesn't backtrack over this long edge. Also, it seems
that the IF should compare PREV(current) against start, not current itself;
otherwise, the start vertex may become current and thus a candidate for
deletion (the analysis which follows the algorithm states that the topmost
or bottommost vertex is never removed).
I would appreciate any correction or confirmation from anybody who has some
experience with this algorithm.
Thanks!
Mark Hood
mjh@zurich.ai.mit.edu
FYI, here is Algorithm 3, as published, for triangulating uni-monotone
polygons:
(c) 1984 ACM, by permission
TRIANGULATE_MONOTONE(first, last)
BEGIN
determine start vertex (topmost if the monotone chain is on the right,
bottommost if it is on the left).
determine number_of_vertices;
current = NEXT(start);
WHILE number_of_vertices >= 3 DO
BEGIN
IF ANGLE(PREV(current), current, NEXT(current)) is CONVEX THEN
BEGIN
FOR each of PREV(current), current, NEXT(current) DO
BEGIN
insert other two vertices to form triangle;
and
save = PREV(current);
remove current from uni-monotone polygon;
IF current = first THEN current = NEXT(first)
ELSE current = save;
decrement number_of_vertices
END
ELSE current = NEXT(current)
END
END
--
Mark Hood
mjh@zurich.ai.mit.edu