Monotone polygonal triangulation with collinear, vertical edge segments

I am trying to triangulate a polygon using the well-known two-pass sweep line algorithm, which subdivides a polygon into monotonic sub-components in the first sweep of the sweep line, and then triangulates those monotonic components in a second pass. My current implementation works in the general case, but I can't forever figure out how to adapt it to deal with inputs containing multiple matching edge segments (segments with the same x-coordinates when sweeping from left to right, or equal y-coordinates when sweeping from right to left).

Edit: I just realized that the way I phrased this question makes it pretty long and verbose, so here's a quick TL; DR; for those who know about polygonal triangulation but don't want to read it all: is the following form a valid input for the second pass of the triangulation algorithm? If yes: how to adapt the second pass to handle it, if not: how should I adapt the 1st pass in such a way that it generates monotonic sub-components 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 summary of the algorithm:

• The first pass subdivides the input polygon into "monotone subcomponents". A monotonic subcomponent is a polygon that can be split into two connected nets, which have coordinates that are either sorted from left to right (when the algorithm is implemented using a vertical line) or from top to bottom (when using a horizontal line). Suppose we are using a vertical scan line: each monotonic subcomponent can then be split into an upper chain, and the lower chain associated with the minimum and maximum x-coordinates, and when scanning the vertices of any chain, the x-coordinate grows. If the subcomponent is strictly monotonic, the top and bottom nets cannot have edge segments with the same x-coordinates (that is: vertical edge segments).

• The second pass sweeps the monotonous sub-components and subdivides them into triangles by adding interior edges. The idea is that each subcomponent moves from left to right, and one of two things can happen at each vertex that falls along the sweep line: a) the unreinforced area to the left of the sweep line can be triangulated by adding diagonals, or b) the current vertex is not can "see" any of the previously moved but unprocessed vertices in the uncrossed area to the left of the sweep line. In case b), the vertex is pushed onto the stack ("reflex chain"), and by construction, at some moment a) takes place, and the vertices of the reflex chain will be pushed one after another and connected with diagonals to the last vertex of the sweep line.

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

I have the following problem, suppose I have a polygon representing an arrow that points to the left, for example:

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

When I introduce this shape into my algorithm, monotone subdivision skips the shape intact: it has vertical edges, so it is not strictly monotone, but it is monotone, and as far as I understand the algorithm, it doesn’t need to subdivide before you can triangulate it (maybe this is where I'm wrong because my guess is bad).

Now let's say I feed the (unmodified) arrow polygon into a second pass to triangulate it. How can I deal with the two vertical edge segments at the base of the arrowhead? The sweep line algorithm requires the vertices of the polygon to be sorted from left to right, so you assumed the answer would boil down to how to sort the vertices with the same x-coordinates (for example, in chain order or by the y-coordinate or by the polygon border value), but any sort I use, triangulation will always fail.

Let's call the left vertex of vertex 0 and order the vertices in counterclockwise order. This means that the 4 vertices of the arrow base are vertices 1, 2, 5 and 6. We have three sorting options:

• Some of the raw material I used to implement the algorithm says "sort vertices with equal x coordinates in ascending y coordinates", that is: 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 the previous unreinforced vertices in the reflex chain, except for the first one (changing this will break the general case). While the area of ​​a polygon bounded by four vertices is triangular, it is obviously not a triangle since it has 4 points and is also not a valid polygon by most definitions.since it has collinear edges.

• Another article I am reading says: "Discontinuous links such that the order of the chains is maintained." This would mean that the 4 vertices in my example would be sorted 1, 2, 6, 5, since both the bottom and top chains work from left to right. If I sweep them in that order, I get a triangle (0, 1, 2) again, but the next checked (6) vertex will create a polygon (0, 1, 6), which is even worse than the first case because it creates an edge (1, 6), which runs through vertex 5, but does not contain it. The sweeping vertex 5 will completely ruin the state of the algorithm, because it will create a degenerate triangle (1, 5, 6), the line and sweeping of the tail vertices will not be able to triangulate the rest of the polygon

• ( , ): , 1), : 1, 2 5, 6, .

I'm beginning to think that perhaps this arrow shape should be considered non-monotonic, or (although I've never seen this in any algorithm description), a monotonic triangulation algorithm requires the input to be strictly monotonic. Could this be what I am missing? And if so, how would I need to adapt the monotone subdivision pass to handle (multiple, overlapping) vertical edge segments? The original material I used classifies all vertices as "start", "end", "merge", "split" or "regular" (bottom / top) during division, but in the case of a vertical segment, these classifications are ambiguous: according to definition of these vertex classes, the vertex portion of a vertical segment can be considered the start / end vertex,but also a split or converging top. Or maybe I need to sort the 4 vertices on my y-coordinates and then create an invalid 4-vertex triangle component with 2 collinear edges and then "fix it" after removing the vertex on the collinear edges?

The main source I used to implement the algorithm is the original paper GJPT-78 which introduced the triangulation algorithm, it is not publicly available (paywall) so I cannot link it here, but there is a lot of CS course material available online that describes the algorithm. I have also used them, for example:

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

I've read a few more of them. Almost every set of slides, paper, blog, or any 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 do not accept equal x-coordinates" and that this constraint is "easily fixed and serves only to simplify the presentation" or "is not fundamental to the algorithm" or something else. Strangely, none of them care about clarifying the required changes or workarounds to support this case, or they contain some kind of fuzzy statement about sorting equal x-vertices in some way that doesn't fix the problem in practice.

Maybe I'm just a little dumb or missing something really obvious, but I've already fumbled with trying to fix this corner case for days with no results and it starts to get frustrating. I intended to implement an algorithm for the main case (which includes writing a DCEL data structure, a sweep line algorithm, a sorted edge map, trigonometry needed to determine interior angles and visibility, data structures for efficiently storing and retrieving vertex classifications, etc.) would be almost all work, and fixing the vertical edge problem afterwards would be trivial. Right now, I've spent more time fixing vertical edges than all the other things I need,to make the algorithm work for the general case in combination (it works great for any polygon I throw at it, t have vertical edges).

Thank! Wouter