# Triangulate algorithm

## Recommended Posts

I already promissed before to put some info here about the triangulate algorithm I use. I was a bit too busy until now to think about it, but here it is.When I needed a triangulate algorithm to create the new DrawTriList commands I first tried one I found on the internet. But this one failed on complex polygons and because I had't written it myself I couldn't find and fix the problems. So I started with a blank sheet of paper and made my own algorith. As I am not studying maths, so probably there is already a fancy name for something like this :). Also, there might be a faster way of doing it, but this way I could program it rather easy. Here are the steps I came up with:You have a polygon with n points[ol][li]Create a line between point i and i+2[li]Check if this line crosses any of the other lines of the polygon, if yes goto 7[li]Does a point on the line lay inside the polygon i,i+1,i+2, if no goto 7[li]Create a new triangle with the points i,i+1,i+2[li]Remove point i+1 from the polygon[li]Go back to 1 and start again[li]Try again for a new triangle i+1,i+2 and i+3[/ol]Do this until you only have a triangle left.Until now this has worked fine for all my polygons (including complex ones). I'll also put the VB module on my website, but first I need to add some comments to it, so it also makes sense for other people (and translate some of the comments that are already there from Dutch to English).Arno

Member Netherlands 2000 Scenery Team[link:home.wanadoo.nl/arno.gerretsen]Arno's FlightSim World for scenery design hints, tips and other tricks...

##### Share on other sites
 Help AVSIM continue to serve you!Please donate today!

I'll put it use. Thank you very much.Lee.

##### Share on other sites

Hi ArnoIt seems to me that your algorithm will always produce a 'solution' for triangulation, and in step 7 you have successfully avoided the trap of splitting the polygon into two distinct areas because you stick to three consecutive points for your candidate triangle (any candidate triangle MUST include two external boundaries of the remaining polygon if you are going to avoid this trap).But as it stands the algorithm favours the fan type of triangulation and will not produce the best solution for long thin shapes where the ribbon approach is more appropriate. One solution that comes to mind is to take account of the relative distances from point i to points i+2 and i-1, and draw the triangle (i,i+1,i-1) when i-1 is nearer, thus removing point i from the remaining polygon. Some quick tests on paper seem to predict that this will still produce a fan for 'rounded' shapes, whilst producing the preferable ribbon style of triangulation for longer, thinner shapes. CheersGerrish

##### Share on other sites

Thanks Gerrish, I'll have a look at the suggestions. At the moment this works fine (so I guess I can better not touch it :) till my scenery is ready), but I'll have a look at the improvements some time.Arno

Member Netherlands 2000 Scenery Team[link:home.wanadoo.nl/arno.gerretsen]Arno's FlightSim World for scenery design hints, tips and other tricks...

## Create an account

Register a new account

• Tom Allensworth,
Founder of AVSIM Online

• ### Hot Spots

• Flight Simulation's Premier Resource!

AVSIM is a free service to the flight simulation community. AVSIM is staffed completely by volunteers and all funds donated to AVSIM go directly back to supporting the community. Your donation here helps to pay our bandwidth costs, emergency funding, and other general costs that crop up from time to time. Thank you for your support!