jm@wlbr.IMSD.CONTEL.COM (James Macropol) (06/22/89)
On June 7, I asked the net for algorithms to convert a (possibly) concave
polygon into a set of convex polygons that cover the same area.
Here is a summary of the responses that I received. I thank all of the
people who reponded for their time and effort.
------
Jim Macropol
Contel Federal Systems (818)706-5202
jm@wlv.imsd.contel.com wlbr!jm
---------------------------------
From: uselton@tusun2.knet.utulsa.edu (Sam Uselton)
The best collection of algorithms for such things, that I have seen,
is _Computational_Geometry_ by Prepartata and Shamos, Pub: Springer-Verlag.
The writing is sometimes heavy going, but the right stuff is all there,
and with references to the original papers. Yes it is concerned with
optimal algorithms, which means added complexity sometimes, but it is
the only way to know that it ALWAYS works fast, even when the data set gets
large, etc.
---------------------------------
From: nelson@berlioz (Ted Nelson)
I found a nice, simple one to degenerate into horizontal trapezoids. You
can find it in ACM Trans Graphics Vol 3, No 2, April 1984, pp 153-174
called "Triangulating Simple Polygons and Equivalent Problems." by Fournier
and Montuno. Don't be thrown by the title, the algorithm you want is
presented completely in the first 5 pages.
---------------------------------
From: "Kenny Goers" <goers@umn-cs.cs.umn.edu>
I think what you would like to know is in the following book:
"Procedural Elements in Computer Graphics", David F. Rogers,
McGraw-Hill Book Company
Chapter 3 Section 13 is
"Determining the Inward Normal and the Three Dimesional Sets"
Chapter 3 Section 14 is
"Splitting Concave Volumes"
---------------------------------
From: Herve Tardif <tardif@cs.unc.edu>
This problem is frequently encountered in the field of computational
geometry. You basically have two possiblities:
1) Decompose your concave polygon as a union of convex regions.
Chazelle, B. M. Computational geometry and complexity
Tech. CMU-CS-80-150, Carnegie Mellon Univ., Pittsburgh, PA., 1980
2) Decompose your concave polygon as a difference of convex regions
Convex decomposition of simple polygons, S.B. Tor and A.E. Middleditch
ACM, TOG, October 1984, vol.3, n.4.
The first method is probably what you want since the area covered by the
convex regions will be the same as the area covered by your concave polygon.
However this method is also harder to implement than the second one.
I hope this will help.
---------------------------------
From: daniel@unmvax.cs.unm.edu (Tommie Daniel)
There is a book that describes how to do this. It is:
Programming Principles in Computer Graphics
Leendert Ammeraal
John Wiley & sons - publisher
This reference even gives an implementation of the algorithm in C.
---------------------------------
From: dulimart@cpsvax.cps.msu.edu (Hansye S. Dulimarta)
Since triangle is a CONVEX polygon, we can decompose the general polygon
to a number of triangles. I don't have such algorithms / program to do that
but I just want to give you an idea of decomposing the polygon:
Let say that we have N-side polygon (which also implies N points in the
polygon). To simplify the notation let us label all points with
p1,p2,...,pN (start from a point in the polygon and go to the next adjacent
point in ONE direction : clockwise / counterclockwise)
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
(3) if the remaining polygon is still concave we still have to apply
further decomposition. [We can do this by calling recursively to
Decompose (N-2);]
end;
[ This unfortunately does not correctly decompose concave polygons,
as pointed out by foo@titan.rice.edu (Mark Hall) and jbm@eos.UUCP
(Jeffrey Mulligan).]
---------------------------------
From: foote@miro.Berkeley.EDU (Bill "Mr. Fun" Foote)
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 :-)
---------------------------------
From: markov@ruuinf.cs.ruu.nl (dr.m.h. overmars)
Summary: This is all wellknown in computational geometry
Some references to literature.
The problem of triangulating a polygon is well-known in computational
geometry. See e.g. Preparata and Shamos: Computational Geometry, an
introduction, published by Springer-Verlag for some algorithms. Given a
n-vertex polygon the theoretically most efficient algorithm runs in time
O(n loglog n) but I would not encourage you to implement it. A simple method
partitions the polygon into monotone polygons (each horizontal line intersects
it only once) and next triangulate these. It does not require you to add
vertices in the interior and runs in time O(n log n). See the above
book for a clear description.