Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!ucbvax!pasteur!miro.Berkeley.EDU!foote
From: foote@miro.Berkeley.EDU (Bill "Mr. Fun" Foote)
Newsgroups: comp.graphics
Subject: Re: Concave polygon problem
Message-ID: <14611@pasteur.Berkeley.EDU>
Date: 13 Jun 89 20:58:04 GMT
References: <3378@cps3xx.UUCP> <3964@eos.UUCP>
Sender: news@pasteur.Berkeley.EDU
Reply-To: foote@miro.Berkeley.EDU (Bill "Mr. Fun" Foote)
Organization: University of California at Berkeley
Lines: 79

In article <3964@eos.UUCP> jbm@eos.UUCP (Jeffrey Mulligan) writes:
>From article <3378@cps3xx.UUCP>, by dulimart@cpsvax.cps.msu.edu (Hansye S. Dulimarta):
 >
 >> procedure Decompose (N);
 >>   comment - "decompose a N-side polygon into triangles"
 >> begin
 >>   (1) Pick the first point to start the decomposition (p1)
 >>   (2) Contruct a triangle from point (p1, p2 and pN-1).
 >>       After "removing" this triangle from the polygon we are left with
 >>       a polygon with (N-2) sides
 >
 >If the interior angle at p1 is greater than 180 degrees, then the
 >triangle into which you have "decomposed" the polygon actually lies
 >outside of the original polygon.  Testing this angle is not sufficient,
 >either:
 >
 >               P2
 >               .
 >             ./
 >           . /
 >         .  /
 >       .   /
 >  P1 .    .  P3
 >       .   \
 >         .  \
 >           . \
 >	     .\
 >	       .
 >
 >               P4
 >
 >Here the angle at P1 is < 180, but triangle P1 P2 P4 contains area
 >outside the polygon.
 >
 ...
 >
 >A little doodling has convinced me that it is difficult to devise
 >an algorithm that will do this without testing that the cutting
 >segment lies entirely within the polygon.  An effective way to
 >reduce the search space, however, would seem to be to restrict
 >possible cutting segments to those having endpoint(s) which do
 >not lie on the convex hull.
 
 
I recently wrote a tessellation program for a class that used a
"slice triangles along the perimeter"-type of algorithm.  The way
I tested for situations like the above was to check that the edge
that I wanted to add didn't intersect any other edges.  As long as one
is careful to define what "intersect" means, especially at the endpoints
of an edge, this works.  Implemented in a straightforward manner, this test
is O(n) for each added segment.

In my program, I walkled all the way around the contour checking for
non-intersecting segments, then I added the shortest such segment.  This
made the resulting tessellation better (i.e. fewer long skinny
triangles).

Doing things like this results in a reasonable algorithm that produces
acceptable triangular tesselations (where "reasonable" and "acceptable"
mean this:  I got a good grade for the program).  It's probably not
the fastest algorithm, and it certainly doesn't produce an optimal
tessellation.  (In my class, two people came up with programs that
produced optimal tessellations.  I believe that they both ran in
O(n^5).)  The algorithm outlined above has an execution
time of O(n^3) (both worst case and typical).

An observation:  I think that the original poster was looking for a
program that would tessellate a concave polygon into a number of
convex polygons.  Tessellating into triangles is probably the simplest
way to go, but he could probably do better by tesselating into something
else (like general convex polygons).

By the way, I still have the source code (in C) for my tessellation
program.  If anyone wants it, drop me an e-mail line.  If you
find any bugs, I do NOT want to know :-)

Bill Foote
foote@miro.Berkeley.EDU
..!ucbvax.Berkeley.EDU!miro!foote