Algorithm to convert a collection of edges into collection of triangles

Question

I have implemented a polygon triangulation algorithm into my program. The algorithm first takes a simple polygon, described as 2D points/vertices, and splits it into y-monotone pieces. After this is done, the algorithm then takes each monotone polygon piece and splits it into triangular pieces.

The input to the algorithm I need help with is an array of vertices outlining a y-monotonic polygon in clockwise or counter-clockwise order. The output is a collection of all edges, both from the original polygon but also the new ones added by the triangulation algorithm in order to split this y-monotonic piece into triangular pieces. This works great if I only want to paint the result as it's possible to just draw each edge.

However, there is no particular order to this collection of edges, and I need the output to be an array of type triangle strip or an array where each triangle is simply described by it's 3 vertices (Example: [a1,a2,a3,b1,b2,b3] as we have triangle a and triangle b).

Is there any conventional algorithm or any other way which can help me solve this? Speed is not of extreme importance but I'd prefer a fast solution.

Here is a pseudocode example of the program used in order to give a better understanding of my question:

class Vertex {
 var point;
 var index;
 init(x,y,index){
   point = (x,y)
   self.index = index
 }
}

class Edge {
 var from; // of type Vertex
 var to; // of type Vertex
 init(from, to){
  self.from = from
  self.to = to
 }
}

A call to a function getMonotonePiecesOfPolygon(polygon) could generate one of many monotonic polygon pieces that would have these vertices and edges:

var vertex0 = Vertex(x0,y0,0)
var vertex1 = Vertex(x1,y1,1)
var vertex2 = Vertex(x2,y2,2)
var vertex3 = Vertex(x3,y3,3)

var edge0 = Edge(vertex0, vertex1)
var edge1 = Edge(vertex1, vertex2)
var edge2 = Edge(vertex2, vertex3)
var edge3 = Edge(vertex3, vertex4)

This could correspond to a rectangle like this:

         edge0
       0------1
       |      |
 edge3 |      | edge1
       |      |
       3------2 
         edge2

Then, we can supply these edges in an array and divide the polygon into triangles with the a triangulation method 'makeMonotonePolygonIntoTrianglePieces()'

var edgesArray = [edge0,edge1,edge2,edge3]  
var edgesArray = makePolygonIntoTrianglePieces(edgesArray)

Now the edgesArray could look like this:

edgesArray == [edge0,edge1,edge2,edge3,newEdge1]

where

newEdge1.from == vertex0
newEdge1.to == vertex2

which would correspond to a polygon like this if we were to draw each edge:

         edge0
       0------1
       |\     |
 edge3 |  \   | edge1
       |    \ |
       3------2 
         edge2

Now here is the part of what my question is seeking to solve. I need an array which would look like this:

var triangles = [
                 vertex0,vertex3,vertex2, 
                 vertex0,vertex2,vertex1
                ]

or using triangle strips (each triangle described by one new vertex and two vertices from the previous triangle):

var triangles = [
                 vertex3, vertex2, vertex0,
                 vertex1
                ]

I don't understand where you're stuck. You know which edges you've added. By construction, each of those edges is common to exactly two triangles. You look for the one or two vertices connected to both ends of that edge. Better yet, keep a list of your constructed triangles as you add the edges. Then you can sort them as you wish. If you want a triangle strip, then removed the superfluous elements from your sorted list. — Prune
Maybe I’m just to tired to think but I’m not following what you mean that I’m “looking for the one or two vertices connected to both ends of that edge”. The solution with adding each constructed triangle seems as it might work though, I’ll try it out tomorrow :) thanks — A. Claesson
Okay, try a specific example. In your posted square, you added edge [0, 2]. You know that this added edge forms two triangles. Thus, you look for the vertices connected to both 0 and 2. That gives you the two triangles you show in your array. If you then start with either isolated vertex -- in only one triangle (it will have exactly two edges -- 1 and 3 are those isolated vertices), you can "walk" your way down the triangle strip. — Prune
@Prune: I think the algorithm is not just restricted to polygons constructed with 4 edges. As soon as you have more I guess it is a bit more complicated, because you have to know which of all 'neighboring' edges you can connect with a new edge to get a triangle that is inside the polygon. Of course for all of them you will construct a triangle (maybe though degenerated), but some of them may lie outside (just think about a polygon that forms a star like shape). Btw. you can even produce such a situation with 4 edges. — jottbe
OP has already gone through the algorithm of generating the edges. The question is then how to produce the final output organization. You start with an isolated vertex and its two edges, forming the first triangle for the output. Now, to make this easier to visualize; remove that triangle from the figure. Recur on the remaining figure. In many cases (and all cases with a triangle strip), one or both of that triangle's vertices will be isolated. — Prune

Håkan Håkan · Accepted Answer · 2019-08-02T21:57:45

In Chapter 2 of the book you refer to in one of the comments, they present a data structure called Doubly-Connected Edge List (DCEL). DCEL:s are used to store planar subdivisions such as triangulations. From what you write, I think it could be what you are looking for.

https://en.wikipedia.org/wiki/Doubly_connected_edge_list

Algorithm to convert a collection of edges into collection of triangles

1 Answers