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 <beeftink@dutentb.et.tudelft.nl> 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
==============================================================================