Jump to content
Sign in to follow this  
arno

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...

Arno

If the world should blow itself up, the last audible voice would be that of an expert saying it can't be done.

FSDeveloper.com | Former Microsoft FS MVP | Blog

Share this post


Link to post
Share on other sites
Guest GerrishGray

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 this post


Link to post
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...

Arno

If the world should blow itself up, the last audible voice would be that of an expert saying it can't be done.

FSDeveloper.com | Former Microsoft FS MVP | Blog

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Tom Allensworth,
    Founder of AVSIM Online


  • 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!

    Click here for more information and to see all donations year to date.
×
×
  • Create New...