Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!csd4.milw.wisc.edu!bionet!apple!usc!elroy!mahendo!wlbr!jm From: jm@wlbr.IMSD.CONTEL.COM (James Macropol) Newsgroups: comp.graphics Subject: Concave polygon problem summary (long) Keywords: polygon fill concave convex Message-ID: <32864@wlbr.IMSD.CONTEL.COM> Date: 21 Jun 89 20:08:51 GMT Reply-To: jm@wlbr.imsd.contel.com (James Macropol) Organization: Contel FSD, Westlake Village, CA Lines: 148 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" 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 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.