From: beeftink@dutentb.et.tudelft.nl (Frederik Beeftink) Newsgroups: sci.math,sci.math.num-analysis Subject: [Q] subdividing concave polygons into convex Date: 31 Jul 1995 10:08:04 GMT Does anyone know an efficient algorithm to detect concave corners in a polygon that is lying in a 3D-plane, and then (knowing the concave corners) to divide this polygon into several convex polygons (preferably all approximately of the same area). Please reply to: beeftink@cas.et.tudelft.nl -- Frederik Beeftink ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math,sci.math.num-analysis Subject: Re: [Q] subdividing concave polygons into convex Date: 3 Aug 1995 17:33:22 GMT It's funny how threads overlap. The following dovetails with the discussion of determining interior points of polygons. In article <3via24\$lp2@mo6.rc.tudelft.nl>, Frederik Beeftink wrote: >Does anyone know an efficient algorithm to detect concave corners in a polygon >that is lying in a 3D-plane, and then (knowing the concave corners) to divide >this polygon into several convex polygons (preferably all approximately of the >same area). (It's not a 3D plane, it's a 2D-plane lying in 3-space). Sure. First rotate the plane so that it's flat (projection will work too, as long as you don't project into a perpendicular direction). Then you can assume the polygon lies in R^2. Let P1, P2, ..., Pn be the vertices taken in order. To decide if the angle at Pi is concave, consider the triangle formed by Pi and the two adjoining vertices P(i-1) and P(i+1). When you traverse the edges P(i-1) Pi and Pi P(i+1), you will either have the interiors of the polygon and the triangle on the _same_ side (if the angle at Pi is convex) or on _opposite_ sides (if concave). Now, when you integrate x dy around a polygon, keeping the interior on your left, you get the area of the polygon, a positive number. Keeping the interior on your right gives the negative of this. In particular, you will get integrals of the same sign iff you traverse two polygons in the same direction (i.e., both interior-is-on-the-left or both interior-is-on-the-right). So, integrate xdy around the polygon and around the triangle, traversing both so that the points P(i-1), P(i), and P(i+1) are taken in the same order. If you get integrals of the same sign, the angle at P(i) is convex. If you get opposite signs, the angle is concave. The integral turns out just to be the cyclic sum of the terms ( y[i]*x[i-1] - x[i]*y[i-1] )/2, so the computations are quite fast. You could also do the projection to the y-z plane, computing the areas of the projections there as (1/2) Sum ( z[i]*y[i-1] - y[i]*z[i-1] ); and similarly the projections to the x-z plane. At least one of these projections would have to be non-zero; on one which is non-zero you just need to compare signs for the big polygon and the triangle. If the triple computation is too slow, it is possible to determine from three noncollinear (e.g. consecutive?) points a single non-zero projection; write me if you need details on this. There are a number of ways to increase computational speed and improve numerical stability, but you can't get better than O(n) in speed (which this is) and you will always have trouble with nearly straight angles. I don't know offhand how to get roughly equal areas, but here's how to create a convex partition. This procedure introduces no new vertices, which you didn't state as a criterion but I assume you had in mind. List all the vertices with either a "+" or "-" according to whether the angle is convex or concave there. (Since the sum of the supplements of the angles taken according to this sign is 2pi, there must be some "+"'s.) Begin with any "-" vertex adjacent to a "+" vertex, say P(i)="-", P(i+1)="+". Then the triangle P(i), P(i+1), P(i+2), P(i), which is like all triangles convex, has by construction the interior of the original polygon on the convex side of the angle P(i+1). Therefore, all of this triangle is contained in the original polygon. [You should consider the case of two consecutive "-" vertices to see why I insist P(i+1) be a "+".] Removing this convex subset leaves another polygon with one fewer vertex; by induction then we obtain a decomposition of the whole polygon into convex sets. Of course in this construction most of the pieces will be triangles. You can reduce the number of parts which result by modifying the construction as follows. Consider all the polygons of the form P(i), P(i+1), P(i+2), ..., P(i+k), P(i), in which P(i+j) is a "+" vertex for all j=1, 2, ..., k-1 (if P(i+k) is also "+", that's OK.) At least for k=2 we know this is convex. For any k it's convex at most of the vertices. One can simply try increasing k as long as the resulting angles at both P(i) and P(i+k) remain concave. (Or, you can try increasing k until you have enclosed an area equal to (1/N)-th of the total, where N is the total number of components you expect. I am not completely clear on whether N can be estimated in advance, or whether it is independent of the chosen decomposition.) dave ==============================================================================