>

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

..!ucbvax.Berkeley.EDU!miro!foote