Polygon Decomposition into Triangles

Rationale: Triangles are simple, convex, and planar. Look at the simple case of a convex polygon, with n sides numbered P0 .. Pn-1. To decompose into triangles just draw lines between P0 - P1, P0 - P2, ... P0 - Pn-2.

But concave polygons are more difficult since this simple technique doesn't work.

So we will look at an algorithm that will work for both convex and concave polygons. The general idea is to form triangles from the polygon and then test to ensure that no other polygon points are inside the triangles (as might be case for concave polygons).

We will start from the left and form the leftmost triangle.

1. Find leftmost vertex (smallest x) - A
2. Compose possible triangle out of A and the two adjacent vertices B and C
3. Check to ensure that no other polygon point P is inside of triangle ABC
4. If all other polygon points are outside of ABC then cut it off from polygon and proceed with next leftmost triangle

For a point P to be inside of ABC, it must be inside of all three planes of the triangle. Example: For triangle ABC below, P1 is outside of plane AC and inside of planes AB and BC, P3 is outside of plane BC and inside of planes AB and AC. Therefore, P1 and P3 are outside of ABC. P2 is inside of all three planes and is therefore inside of ABC.

So if we can find a plane that the point is outside then we are through. We can first test the point against the extent (bounding rectangle) of the triangle. The extent is defined by:

min (x1, x2, x3), max (x1, x2, x3)

min (y1, y2, y3), max (y1,y2,y3)

so test is:

px < min (x1, x2, x3) ( this test is not needed if use leftmost triangle) and px > max (x1, x2, x3)

py < min (y1, y2, y3) and py > max (y1, y2, y3)

If any of these conditions is true, then P is outside of triangle. Note: This is true for P3, but not for P1. If all of above tests fail (are not true), then must do a generalized triangle_inside test. This is based on a property of the line equation analogous to plane equations. That is, if we put a points coordinates into the equation for a line, all points on the line will have a value of 0 for the line equation, all poinyts on one side of the line will have a value > 0 and all points on the other side of the line will have a value < 0.

For a parametric representation of a line:

x = x1 + t * dx

y = y1 + t * dy

Solving for t gives:

t = (x - x1) / dx = (y - y1) / dy

f(x, y) = (x - x1) (y2 - y1) - (x2 - x1) (y - y1) = 0 for x, y on the line

f(x, y) > 0 for a point on one side of the line

f(x, y) < 0 for a point on the other side of the line

So, a point P is inside a line iff it is on the same side as the vertex opposite the line. We can have the function inside as follows:

function same_side (p1, p2, l1, l2: point2d) : boolean;
 { returns true if p1 and p2 are on the same side of the line through l1, l2 }
  begin
    same_side := ((p1.x - l1.x) * (l2.y - l1.y) - (l2.x - l1.x) * (p1.y - l1.y))
	         * ((p2.x - l1.x) * (l2.y - l1.y) - (l2.x - l1.x) * (p2.y - l1.y)) > 0
end; { same_side }

function inside(p, a, b, c, point2d) : boolean;
{ returns true if p is inside of triangle abc, else returns false }
  begin
     inside := same_side(p, a, b, c) and same_side(p, b, a,c) and
                   same_side(p, c, a, b);
end;  { inside }

If there are no points inside of our test triangle, then we store the new triangle, remove the leftmost vertex and proceed with the next leftmost vertex.

If one of points is inside the test triangle, then we form a new test triangle by connecting the original leftmost point and the leftmost of the inside points.

Solid Polygon menu
HyperGraph Table of Contents.
HyperGraph Home page.