Monotone polygon triangulation with collinear, vertical edge segments

3
votes

I'm trying to implement polygon triangulation using the widely known 2-pass sweep line algorithm that subdivides the polygon into monotone subcomponents in the first sweep line pass, then triangulates these monotone components in a second pass. My current implementation works for the general case, but I can't for the life of me figure out how to adapt it to deal with inputs containing multiple coincident edge segments (segments with equal x-coordinates when sweeping left-to-right, or equal y-coordinates when sweeping right-to-left).

Edit: I just realized that the way I framed this question makes it quite long and verbose, so here's a quick TL;DR; for anyone who knows about polygonal triangulation but doesn't feel like reading the whole thing: is the following shape a valid input for the 2nd pass of the triangulation algorithm? If yes: how to adapt the second pass to handle it, if no: how do I adapt the 1st pass such that it produces monotone subcomponents that can be fed into the 2nd pass:

http://www.wouterbijlsma.nl/~wouter/tmp/RTdr6rET9.png

Long version of the question below this point ;-)

A very quick rundown of the algorithm:

  1. The first pass subdivides the input polygon into 'monotone subcomponents'. A monotone subcomponent is a polygon can be split into 2 connected chains that have coordinates that are either sorted left-to-right (when the algorithm is implemented using a vertical sweep line), or top-to-bottom (when using a horizontal sweep line). Let's assume we use a vertical sweep line: each monotone subcomponent can then be split into an upper chain, and a lower chain, connected at the minimum and maximum x-coordinates, and when scanning the vertices of either chain, the x-coordinates are increasing. If the subcomponent is strictly monontone, the upper and lower chains can not have edge segments with identical x-coordinates (ie: vertical edge segments).

  2. The second pass sweeps the monotone subcomponents and subdivides them into triangles by adding internal edges. The idea is that each subcomponent is swept left-to-right, and at each vertex hit by the sweep line, one of 2 things can happen: a) the untriangulated area to the left of the sweep line can be triangulated by adding diagonals, or b) the current vertex cannot 'see' any of the previously swept, but unprocessed vertices in the untriangulated area to the left of the sweep line. In case b) the vertex is pushed to a stack (the 'reflex chain'), and by construction, at some point case a) will occur, and the vertices of the reflex chain will be popped one-by-one and connected with diagonals to the last sweep line vertex.

The above description lacks some details, but I would assume anyone who knows how to answer my question already understands the algorithm so I won't go into more detail here.

The problem I have is the following: suppose I have a polygon representing an arrow that points left, for example like this:

http://www.wouterbijlsma.nl/~wouter/tmp/RTdr6rET9.png

When I enter this shape into my algorithm, the monotone subdivision pass leaves the shape untouched: there are vertical edges in it, so it's not strictly monotone, but it is monotone, and as far as I understand the algorithm, it does not have to be subdivided before you can triangulate it (maybe this is where I go wrong because my assumption is bad).

Now suppose I feed the (unmodified) arrow polygon into the 2nd pass to triangulate it. How do I deal with the 2 vertical edge segments in the base of the arrow head? The sweep line algorithm requires the vertices of the polygon to be sorted left to right, so you would assume the answer would come down to how to sort vertices with the same x-coordinates (e.g. in chain order, or on y-coordinate, or on polygon boundary index), but whatever sorting I use, the triangulation will always fail.

Let's call the leftmost vertex vertex 0, and order the vertices in counter-clockwise order. This means the 4 vertices of the base of the arrow head are vertices 1, 2, 5 and 6. We have three sorting options:

  1. Some of the source material I used to implement the algorithm says 'sort vertices with equal x coordinates on increasing y coordinates', ie: 1, 2, 5, 6. If I do this and sweep them, the first triangle comes out ok (0, 1, 2), but after that the algorithm will add an edge (5, 2), which creates a 4-vertex component (0, 2, 5, 6). No edge (0, 5) is added, because the triangulation algorithm prescribes adding edges to all previous untriangulated vertices on the reflex chain except the first (changing this would break the general case). While the polygon region bounded by the 4 vertices is triangular in shape, it's obviously not a triangle because it has 4 points, and it's also not a valid polygon by most definitions because it has collinear edges.

  2. Another paper I read says 'break ties such that the chain order is preserved'. This would mean the 4 vertices in my example would be sorted 1, 2, 6, 5, since both the lower and upper chain run left-to-right. If I sweep them in this order I again get a triangle (0, 1, 2), but the next vertex scanned (6), will create a polygon (0, 1, 6), which is even worse then the first case because it creates an edge (1, 6) which runs over vertex 5 but doesn't contain it. Sweeping vertex 5 will completely mess up the state of the algorithm because it will create a degenerate triangle (1, 5, 6), a line, and sweeping the tail vertices will fail to triangulate the remainder of the polygon

  3. Sorting in original polygon vertex order (along boundary, counter-clockwise): in this case this would yield the same result as case 1), ie: 1, 2 5, 6, which has already been shown to fail.

I'm starting to think that maybe an arrow shape like this should either be considered non-monotone, or (even though I have never seen this mentioned in any description of the algorithm) the monotone triangulation algorithm requires inputs to be strictly monotone. Could this be the thing I'm missing? And if yes, how would I need to adapt the monotone subdivision pass to deal with (multiple, coincident) vertical edge segments? The source material I used classifies all vertices as 'start', 'end', 'merge', 'split' or 'regular' (lower/upper) during subdivision, but in case of a vertical segment, these classifications are ambiguous: according to the definition of these vertex classes, a vertex part of a vertical segment could considered to be a start/end vertex, but also a split or merge vertex. Or maybe I do have to sort the 4 vertices on their y-coordinates, then create an invalid 4-vertex triangle component with 2 collinear edges, and then 'fix it up' afterwards by removing the vertex on the collinear edges?

The main source I used to implement the algorithm is the original GJPT-78 paper that introduced the triangulation algorithm, it's not publicly available (paywall), so I can't link it here, but lots of CS course material is available online that describes the algorithm, I also used these for example:

http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf https://www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdf (see 'Lecture 6' chapter)

I've read quite a few more of these. Almost every set of slides, paper, blog, or whatever other description of the algorithm specifically mentions vertices with equal x-coordinates (or y-coordinates if using a horizontal sweep line), but they all just say 'we assume no equal x-coordinates' and that this restriction is 'easily fixed and only serves to simplify representation' or 'not fundamental to the algorithm' or whatever. Strangely none of them cares to elaborate on the required changes or workarounds to support this case, or they contain some fuzzy statement about sorting equal x-vertices in some way that in practice does not fix the problem.

Maybe I'm just a little stupid or missing something really obvious, but I've been messing around trying to fix this corner case for days now without result, and it's starting to get really frustrating. I had assumed implementing the algorithm for the basic case (which involves writing a DCEL data structure, a sweep line algorithm, a sorted edge map, the trigonometry required to determine interior angles and visibility, data structures to efficiently store and lookup vertex classifications, etc) would be almost all of the work, and fixing the vertical edge problem afterwards would be trivial. Right now I spent more time trying to fix the vertical edges, than on all of the other stuff I needed to get the algorithm working for the general case combined (it works perfectly for any polygon I throw at it, as long as it doesn't have vertical edges).

Thanks! Wouter

2
algorithmgraphicspolygoncomputational-geometrytriangulation
Does the right thing happen on the arrow with a slight shear transform (i.e., (x, y) |-> (x + epsilon y, y))? – David Eisenstat
I ask because one of the usual tricks for dealing with degeneracy w.r.t. sweep lines is to make an infinitesimal, symbolic rotation, which amounts to "sorting by y" in the sense that, if the y-almost-parallel sweep line intersects a point (x, y), then the points to the "left" are those lexicographically less than (x, y), and the points to the "right" are greater. If the sheared arrow leads to a degenerate triangulation, however, then there's a more fundamental problem with collinear segments. – David Eisenstat
@David Eisenstat: applying a slight shear transform each of the points that have the same x-coordinates would indeed result in a 'valid' triangulation and prevent the algorithm from getting into an invalid state. I've actually seen this mentioned as a solution at least once. The problem I see though, is that this would add additional triangles with an extremely small area. In the 'arrow' case this would be a triangle (2, 5, 6). Of course one could filter out such triangles from the result, but I'm not sure if there isn't some nicer solution that produces a proper triangulation directly. – w0utert
Constrained Delaunay triangulation is a possibility, though perhaps someone more knowledgeable than me about computational geometry could suggest an alternative that reuses more of your existing code base (planar graph algorithms are more my specialty). – David Eisenstat

2 Answers

4
votes

I finally figured this out myself, so I'll answer my own question, for posterity ;-)

As it turns out, the changes to make the triangulation algorithm work for polygons with vertical edges are minimal, and no special cases are required to handle them. I had to change the following things:

  1. Sort vertices with equal x-coordinates on increasing y-coordinate (note: I use a vertical sweep line, for a horizontal sweep line sort on y first, then x)
  2. Classify vertices with incident vertical edges as 'merge' or 'split', instead of 'regular up/down' (aka 'upper chain/lower chain')
  3. Never add diagonals when the last 2 points of the reflex chain and the current sweep line vertex are colinear

The first requirement is mentioned in most papers on the algorithm. Sorting bottom to top has the same effect of a symbolic clockwise rotation, like David Eisenstat mentioned.

The second change I had to make was because I misinterpreted the various vertex classifications. My assumption was that a merge vertex should always have both incident edges fully to its left, a split vertex fully to its right, which is not correct. If one of the 2 incident edges is vertical, and the other to the left of the vertex, it should be classified as 'merge', if the other edge is to the right, it should be classified as 'split'. In particular, I had to change the following lines from this:

// Classify vertex based on the interior angle and which side of the sweep line the two edges are
BOOL reflex_vertex = (interiorAngle < 0);

BOOL both_left = (e_in.origin.coordinates.x < vertex.coordinates.x) && (e_out.destination.coordinates.x < vertex.coordinates.x);
BOOL both_right = (e_in.origin.coordinates.x > vertex.coordinates.x) && (e_out.destination.coordinates.x > vertex.coordinates.x);

if (!reflex_vertex && both_right)
  type = K14SweepLineVertexTypeStart;

else if (!reflex_vertex && both_left)
  type = K14SweepLineVertexTypeEnd;

else if (reflex_vertex && both_right)
  type = K14SweepLineVertexTypeSplit;

else if (reflex_vertex && both_left)
  type = K14SweepLineVertexTypeMerge;

else if ([_lowerChainVertices containsObject:@(vertex.id)])
  type = K14SweepLineVertexTypeLowerChain;

else
  type = K14SweepLineVertexTypeUpperChain;

To this:

// Classify vertex based on the interior angle and which side of the sweep line the two edges are
BOOL reflex_vertex = (interiorAngle < 0);

BOOL both_left = (e_in.origin.coordinates.x <= vertex.coordinates.x) && (e_out.destination.coordinates.x <= vertex.coordinates.x);
BOOL both_right = (e_in.origin.coordinates.x >= vertex.coordinates.x) && (e_out.destination.coordinates.x >= vertex.coordinates.x);

...

The last change was necessary to prevent degenerate triangles with 3 colinear points in the output. When triangulating monotone subcomponents, whenever a vertex is found on the same polygonal chain as the vertices on the stack (the 'reflex chain'), diagonals are added from the current sweep line vertex, to all visible reflex chain vertices. In my implementation, visibility was determined by looking at the (signed) interior angle of the vertex at the top of the stack. This check only looked at the sign of the angle, where a positive angle means visible (interior less than or equal to pi radians, or 180 degrees). The problem was with the or equal part, if the 2 points at the top of the stack plus the current sweep line vertex are collinear, the interior angle is exactly pi radians, and no diagonal should be added. I had to change the check from this:

BOOL visible = (vi_x_interior_angle > 0.0f);

To this:

BOOL visible = (vi_x_interior_angle > 0.0f) && ((vi_x_interior_angle + COMPARE_EPSILON) < M_PI);

I use a small epsilon, which is not really necessary if your vertices are static/hard-coded and the x-coordinates of vertical edges are exactly equal, but in my case the vertices maybe calculated and could have small roundoff error. Not adding a diagonal in case the 3 points are almost exactly colinear should in general produce better results than adding a triangle with a virtually zero area.

Apart from these three things no special handling whatsoever is needed to make the algorithm work for any simple polygon (no self intersection, no holes) you throw at it. I'm a bit bummed to have wasted at least 20 hours to figure this out, but at least I finally got the stupid thing working. Just wish at least one of the many papers I read about this particular algorithm would have been a little more explicit about the 3 things I missed in my implementation :-/

1
votes

In our sweep line engine we use total lexicographical ordering among all points, where we consider y coordinate to be the major coordinate and x coordinate to me the minor coordinate (in our case we sweep in bottom-to-top direction). In our implementation, to generalize the processing of points having the same y coordinate, we assume that points that are located later in the input queue (have greater x coordinate) are at the same time located slightly "higher" on the plane by some infinitesimal amount. This is, obviously, a conceptual variant of a shear transformation by some infinitesimal amount of shear, which was already mentioned in the comments.

And, as you already mentioned above, a side-effect of this approach is that in general case it leads to the formation of "unnecessary" cuts at the monotonization stage, as shown below

enter image description here

Despite the fact that the shape is already monotone along vertical direction, the algorithm finds it necessary to add the cutting edge shown in red (again, in this case we sweep in bottom-to-top direction). But since our ultimate goal is a triangulation anyway, this is not a big problem. Of course, if you have some additional restrictions on the quality of the final triangulation, then these "early" triangles might become an issue.

In my case the triangulation is generated in order to serve as an input for an algorithm that performs kinetic transformation of the initial triangulation. In order to be robust, kinetic triangulation algorithms have to be able to deal with "bad" needle-like triangles anyway, for which reason I don't impose any restrictions on the quality of the triangulation.