jm@wlbr.IMSD.CONTEL.COM (James Macropol) (06/08/89)
I have been looking for an algorithm to convert a (possibly) concave polygon into a set of convex polygons that cover the same area. The algorithm need not be optimal, but should do a reasonable job, and be fast. I have been unable to find such a beast, but I know that it must exist somewhere. Any ideas or references would be much appreciated. ------ Jim Macropol Contel Federal Systems (818)706-5202 jm@wlv.imsd.contel.com wlbr!jm
nelson@berlioz (Ted Nelson) (06/08/89)
In article <32132@wlbr.IMSD.CONTEL.COM> jm@wlbr.imsd.contel.com (James Macropol) writes: >I have been looking for an algorithm to convert a (possibly) concave >polygon into a set of convex polygons that cover the same area. The >algorithm need not be optimal, but should do a reasonable job, and be >fast. 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. -- Ted.
dulimart@cpsvax.cps.msu.edu (Hansye S. Dulimarta) (06/13/89)
In article <32132@wlbr.IMSD.CONTEL.COM> jm@wlbr.imsd.contel.com (James Macropol) writes: >I have been looking for an algorithm to convert a (possibly) concave >polygon into a set of convex polygons that cover the same area. The >algorithm need not be optimal, but should do a reasonable job, and be >fast. > >I have been unable to find such a beast, but I know that it must exist >somewhere. > >Any ideas or references would be much appreciated. >------ >Jim Macropol >Contel Federal Systems (818)706-5202 >jm@wlv.imsd.contel.com wlbr!jm 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; Do you get the idea ?
foo@titan.rice.edu (Mark Hall) (06/13/89)
In article <3378@cps3xx.UUCP> dulimart@cpsvax.UUCP (Hansye S. Dulimarta) writes: >In article <32132@wlbr.IMSD.CONTEL.COM> jm@wlbr.imsd.contel.com (James Macropol) writes: >>I have been looking for an algorithm to convert a (possibly) concave >>polygon into a set of convex polygons that cover the same area. >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; > >Do you get the idea ? P4 *-------------------------------* / \ / \ * P3 \ \ \ \ \ * P2 \ | *(inside) * | / * P1 / / / / / * Pn-1 / \ / \ Pn-2 / *------------------------------* One problem with your algorithm: It fails for concave polygons. (Which is what it is needed for.) The triangle defined by points P1, P2, Pn-1 does not have to be in the polygon at all. Did I miss something? - mark
jbm@eos.UUCP (Jeffrey Mulligan) (06/14/89)
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. > Do you get the idea ? More half-baked speculation follows; hit 'n' now if you're waiting for the literature citation. 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. -- Jeff Mulligan (jbm@aurora.arc.nasa.gov) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-6290
foote@miro.Berkeley.EDU (Bill "Mr. Fun" Foote) (06/14/89)
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
markov@ruuinf.cs.ruu.nl (dr.m.h. overmars) (07/22/89)
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. -- -------------------------------------------------------------------------------- Mark Overmars |\/| Dept. of Comp. Science, University of Utrecht, | |ark P.O. Box 80.089, 3508 TB Utrecht, the Netherlands E-mail: hp4nl!ruuinf!markov