Slicing up geometry to create triangles

Question

When rendering object onto a screen, one must often cut up their objects into quads and triangles to allow the computer to process them and finally draw them onto a screen.

I am trying to slice up a given piece of geometry and end up with solely triangles. Since I am trying to incorporate something like this into a program, I am trying to find a general algorithm. I couldn't find any existing algorithms for this, so I had a go at it myself:

The problem I'm having with this is that I sometimes end up with a gap in my shape, and at the third step I don't know how to find the correct vertex to start at.

Some "rules":

• The object can have any number of vertices (although realistically speaking a limit of ~20 would suffice)

• The order of the vertices is known. This means the perimeter of the object is also known.

• The collection of triangles after applying the algorithm should have the same area and perimeter as the piece of geometry at the beginning. (So the collection of triangles should be the same shape)

The question is: is there a known algorithm for cutting up a single, closed shape into triangles (or quads)?

I don't know if this question is truly appropriate for the math exchange, but I hope someone here has done this before, or knows how to as I'm stuck.

Answer 1

This is called polygon triangulation. There are simple algorithms to solve it. I have some C code, in fact.

Answer 2

I am not sure I can answer your question completely (for the reason marked in bold).

According to Wiki’s explanation on polygon triangulation, one can decompose a polygon into a set of triangles such that the sum of all their area is the same as the original.

But that cannot fulfill your requirement - “The collection of triangles … should have the same area and perimeter as the piece of geometry at the beginning”.

In geometry, we can reduce any convex polygon to a triangle with the area preserved. See below.

In the figure, $ABCD$ is a quadrilateral. $BC$ is produced to $E$ such that $DE\parallel AC$. $AE$ intersects $DC$ at K.

It is not difficult to see that $\text{area of}\space \triangle ADK = \text{area of} \space \triangle CEK$.

Thus, quadrilateral $ABCD$ is ‘reduced’ to a triangle (namely$\triangle ABE$) having the same area.

Through this technique, one can ‘reduce’ an $n$-sided polygon to $(n-1)$-sided polygon having the same area …. and finally to a triangle having the same areas as the original.