1
$\begingroup$

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:

enter image description here

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So that's why I couldn't find anything on the web .. forgot about the word 'polygon'. Thanks! Will approve as soon as I can (8 minutes). $\endgroup$ – user3162904 Apr 29 '14 at 15:59
0
$\begingroup$

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.

**enter image description here**

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.

$\endgroup$
  • 1
    $\begingroup$ How doe this relate to the original question? $\endgroup$ – Servaes Jul 13 '15 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.