Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume38/tessel/part02/tessel.txt

Text File | 1993-06-21 | 9KB | 230 lines

From [e-mail] (Eric Manghise) to "comp.graphics"

|>
|>     - Is there a simple way of subdividing a 2D polygon with
|>         holes into convex pieces?  (Where the holes are
|>         2D polygons that are wholly contained in the
|>         polygon that delineates the exterior boundary.)

        No there is no simple way to decompose a polygon
        into convex pieces. I assume you want to decompose
        it into triangles. There are alot of different ways
        to do this. I might refer you to

            Triangulating a Simple Polygon in Linear Time
            Bernard Chazelle
            Department of Computer Science
            Princeton University.

        When you add holes you create a whole world of problems.
        Also when you compound this with the case of concave polygons
        life become very complicated.


        Here is another article I sucked off the net along time ago.


Concave or Convex?

The cruz of your problem is determining whether an angle is convex (< 180
degrees) or not.  Given three distinct points P0, P1, and P2 in the plane,
how do we tell it the angle formed by line segments P0P1 and P1P2 is con-
vex or not?  Before we answer this, we must be clear about our point of
view:  We assume that we are ABOVE the xy-plane (i.e., at some point with
a positive z-coordinate), looking down.  In addition, we define the angle
between P0P1 and P1P2 by measuring the arc swept out by rotating P1P2
about P1 in a COUNTERCLOCKWISE direction until we meet segment P0P1.

We don't actually need to determine the exact angle.  We simply want to
know if it is < 180 degrees or not.  Thus, we can conceptualize the pro-
blem in a bit different way:  Consider the infinite line oriented FROM P0
TO P1.  Where is P2 in relation to this line?

    P2 is on the left:   The angle is < 180 degrees
    P2 is on the line:   The angle is = 180 degrees
    P2 is on the right:  The angle is > 180 degrees

So now the problem boils down to figuring out which side of a line that
a point is on.  This is easily determined.  If L(x, y) = 0 is the ORIEN-
TED equation of a line, where L(x, y) = ax + by + c, then for any point P,

    L(P) > 0:  Point P is on the left of the line
    L(P) = 0:  Point P is on the line
    L(P) < 0:  Point P is on the right of the line

Thus, to tell whether angle P0P1P2 is convex, do this:  Determine the
oriented equation of the line FROM P0 TO P1, and plug P2 into the equa-
tion.  If the result is > 0, then the angle is convex.

WARNING:  As always when working with floating point arithmetic, all
comparisons should involve an epsilon.  Furthermore, to be safe, the
equation of the line should be normalized by dividing all coefficients
by sqrt(a*a + b*b).  Then when the equation is evalutated at a point,
the result is actually the signed distance of the point from the line,
which can be compared against an epsilon to see where the point is in
relation to the line.

A shortcut to the above method of determining a line equation is to use
this determinant, where Ph = (xh, yh), Pi = (xi, yi), and Pj = (xj, yj):

            | xh yh 1 |
        D = | xi yi 1 |
            | xj yj 1 |

If D > 0 then Pj lies on the left of the line FROM Ph TO Pi.  If D = 0,
the three points are collinear.  If D < 0 then Pj lies on the right of the
line FROM Ph TO Pi.  (Lying on the left means angle PhPiPj is convex, and
lying on the right means the angle is nonconvex.)

DISCLAIMER:  The above determinant should be checked.  I am recalling it
from memory, and it may not be quite right.

Using this determinant is not really different from the method already de-
scribed.  Calculating the determinant is exactly the same as determining
the equation of the line from point Ph to point Pi and then plugging Pj
into the equation.  Also, a warning is in order, because no normalization
is done.

So now we have a way to tell if an angle is convex or not.  This operation
is the basic primitive for all the following algorithms.



Clockwise or Counterclockwise?

Say we are given an array of n >= 3 distinct points labeled P0, P1, ...,
Pn-1, which are the vertices of a well-formed simple polygon P.  Say that
the n vertices are in order, but we don't know if the order is clockwise
or counterclockwise.  How do we tell?  Here is a simple algorithm:

Scan the set of vertices and find the one with least x-coordinate.  If
there is more than one vertex with least x-coordinate, then pick the one
of them which has least y-coordinate.  The resulting vertex is unique.
(If not, the polygon is ill-formed because its vertices are not distinct
points.) Call this vertex Pi.

Let Ph be the vertex preceding Pi, and let Pj be the vertex following Pi.
Then test if angle PhPiPj is convex.  If it is, then the vertices of poly-
gon P are oriented counterclockwise in our input array.  Otherwise, the
vertices are ordered clockwise.  In the latter case, reverse the elements
of P to put the vertices in counterclockwise order.



Decomposing a 2-d polygon in the xy-plane into triangles

Given a well-formed simple polygon P with n >= 3 vertices labeled P0,
P1, ..., Pn-1, we want to decompose P into triangles.  We assume that
the vertices are oriented in a counterclockwise direction as seen from
above.

Before presenting a general algorithm which handles all cases, it is
worthwhile to consider the case when it is known that the polygon is
convex (i.e., all angles < 180 degrees).  Then the polygon is easily
decomposed into n-2 triangles by drawing diagonals from vertex 0 to
the n-3 vertices P2, P3, ..., Pn-2, resulting in these triangles:

    P0,P1,P2
    P0,P2,P3
    P0,P3,P4
    . . .
    P0,Pn-2,Pn-1

If it is known that many of the polygons to be processed are likely to
be convex, then it is a good idea to test each polygon to see if it is
convex, and if so, apply the above simple algorithm.  Only when a non-
convex polygon is encountered is it necessary to apply the general al-
gorithm.

Here is the general algorithm:

Let Pi be any vertex of the polygon.  Let Ph be the vertex preceding Pi,
and let Pj be the vertex following Pi.  Test if angle PhPiPj is convex.
If not, increment i, determine h and j from i, and test again.  If a
convex angle is not found by this process, there is an error in the
polygon.  It is either not well-formed, or it is oriented clockwise.

Once a convex angle PhPiPj is found, the triangle formed by the three
points is a candidate.  However, it is ONLY a candidate.  It must be
tested like this:  For every vertex V of the polygon other than the three
forming the triangle, test if V is OUTSIDE the triangle (note that V
must not be ON the boundary of the triangle).  If some vertex is found
which is either on the boundary of or inside of the triangle, then the
triangle must be rejected.  In this case, increment i and continue
searching for a convex angle.

If all V are outside of the triangle, then slice the triangle off the
polygon by removing vertex Pi.  If the number of points in the resulting
polygon is 3, then the decomposition is finished.  Otherwise, search
again from a convex angle.

Here is a more detailed version of the algorithm:

  i = n-1;

  while (n > 3)
    {
    h = i;
    i = (i == n-1 ? 0 : i+1);
    j = (i == n-1 ? 0 : i+1);

    if (angle PhPiPj nonconvex)
      continue;

    k = (j == n-1 ? 0 : j+1);         /* k is vertex after j  */
    m = n-3;

    while (m--)
      if (Pk outside triangle PhPiPj)
        k = (k == n-1 ? 0 : k+1);
      else
        break;

      if (k != h)                      /* Vertex k not outside */
        continue;                      /*   triangle PhPiPj    */

    Store triangle PhPiPj;

    Remove vertex Pi from polygon P;
    n--;
    i = (i == 0 ? n-1 : i-1);
    }

  Store triangle P0P1P2 as the final triangle of the decomposition;


The above algorithm always produces exactly n-2 triangles.  Also, every
vertex of every triangle produced by the algorithm is a vertex of the
original polygon.  In other words, no new points are created by this al-
gorithm.



Now Back to 3-Space

Since your original problem has to do with a polygon in 3-space, we need
to consider how to get from there to the xy-plane.  Say that the input
is an array Q of n >= 3 3-points, Q0, Q1, ..., Qn-1 which are the vertices
of a well-formed simple planar polygon.

If the plane of the polygon is not vertical (consider the xy-plane to be
horizontal), then simply set up a 2-d polygon P with the points Q, ignor-
ing the z-coordinate.  In effect, this projects polygon Q onto the xy-
plane.  Now check if P is counterclockwise, and, if not, reverse its ele-
ments so it is counterclockwise.  Then decompose P into triangles.  Note
that if the z-coordinates are carried in polygon P (they will never be
used because all algorithms above use only x- and y-coordinates), then
the triangles produced by the decomposition will in fact be polygons in
3-space with correct z-coordinates.  Thus, the input polygon is decom-
posed as desired.

If the input polygon is in a vertical plane (which can be determined by
checking to see if the projection onto the xy-plane is a straight line),
then simply swap the x- and z-coordinates of the input vertices, apply
the algorithm in the preceding paragraph, and then swap the x- and z-
coordinates of the resulting triangles.

Note that this method of going from 3-space to 2-space works because a
parallel projection of a polygon does not change any convex angles to
nonconvex ones, or vice versa.