Not logged in, Join Here! or Log In Below:  
News Articles Search    

 Home / General Programming / Triangulate y-monotone polygon in O(n) Account Manager
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.

May 17, 2005, 01:01 PM

I have following: one y-monotone polygon which I need to triangulate. I sort all points by y (merge the 2 monotone sides/chains of the polygon) and save the indices. After that I save the first 2 points in a stack S. Now I start a loop from i=3 to n-1 and look if the next point is on the other chain of the polygon (then the top point on S). If this is true I draw all diagonals from the actual point to all points in S and insert point i-1 and point i into the stack. If that wasnt true I take a point out of S and draw a diagonal from all points in S to point i - but only when the diagonal is inside the polygon. (remove all points in S without the last one in S). When I finished the loop I draw diagonals from all points in S (without the last and the first one) to the last point.

Ok, and there is the problem. How do I check if the diagonal is in the polygon without go from O(n) to something more O(nē)?


May 18, 2005, 11:30 AM

Is your polygon convex or can it be concave?

In either case, it sounds like you could modify the sweeping planes algorithm to suit your needs... if you can construct a list of edges then triangulating the polygon is easy...


May 18, 2005, 12:36 PM

Ehrm, maybe you didnt noticed it: it is monotone and in is a simple polygon which must not be convex. I thoughed about it and found some text about it (that nearly exactly what i wanted to do): (page 14 or so)

(I am speaking about the loop inside the else - so both points are in the same chain) When I understand it correctly i need to test the diagonale between the top vertex an the current vertex against the edge between the top and the second-top vertex? Sounds logic.....maybe you can check if is correct

(I am sry, when this sounds like i am angry, but my english isnt the best)


May 18, 2005, 07:02 PM

You toughed about it? Need more bran... :)


May 18, 2005, 07:04 PM

Well, if you have the left and right chains constructed, you can build triangles starting from the topmost point to each point on the right chain, going down the chain, and then go back up the left chain... that will create a triangle fan though. it is the simplest approach

This thread contains 5 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.