Polygonal Triangulation - algorithm with O(n log n) complexity

Posted by Arthur Wulf White on Game Development See other posts from Game Development or by Arthur Wulf White
Published on 2012-10-14T19:08:11Z Indexed on 2012/10/14 21:52 UTC
Read the original article Hit count: 878

Filed under:

algorithm

|

polygon

|

triangles

I wish to triangulate a polygon I only have the outline of (p0, p1, p2 ... pn) like described in this question: polygon triangulation algorithm and this webpage: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html

I do not wish to learn the subject and have a deep understanding of it at the moment. I only want to see an effective algorithm that can be used out of the box. The one described in the site seems to be of somewhat high complexity O(n) for finding one ear. I heard this could be done in O(n log n) time. Is there any well known easy to use algorithm that I can translate port to use in my engine that runs with somewhat reasonable complexity?

The reason I need to triangulate is that I wish to feel out a 2d-outline and render it 3d. Much like we fill out a 2d-outline in paint. I could use sprites. This would not serve cause I am planning to play with the resulting model on the z-axis, giving it different heights in the different areas.

I would love to try the books that were mentioned, although I suspect that is not the answer most readers are hoping for when they read this Q & A format. Mostly I like to see a code snippet I can cut and paste with some modifications and start running.

© Game Development or respective owner

Related posts about algorithm

Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More
word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More
Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More
Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More
collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More

Related posts about polygon

Point in polygon OR point on polygon using LINQ

as seen on Stack Overflow - Search for 'Stack Overflow'
As noted in an earlier question, How to Zip enumerable with itself, I am working on some math algorithms based on lists of points. I am currently working on point in polygon. I have the code for how to do that and have found several good references here on SO, such as this link Hit test. So, I… >>> More
Breaking a concave polygon into convex ones.

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm using a game physics library (Box2D) which only supports convex polygon shapes. However, I'd like the level builder to be able to just specify concave polygons without having to worry about that. So, how can I automatically break apart a concave polygon into convex ones (or even all triangles)… >>> More
AndEngine Physics Editor loading level

as seen on Stack Overflow - Search for 'Stack Overflow'
I have created a .pes file using PhysicsEditor and imported as xml and have added to my project. When I parsed it and created bodies, it is showing strange behavior. The mapping of bodies that I created in PhysicsEditor is totally different what I see in my application means the shapes I draw in PhysicsEditor… >>> More
A Simple Geo fencing using polygon method

as seen on Code Project - Search for 'Code Project'
A Simple Geo fencing using polygon method >>> More
Polygonal Triangulation - algorithm with O(n log n) complexity

as seen on Game Development - Search for 'Game Development'
I wish to triangulate a polygon I only have the outline of (p0, p1, p2 ... pn) like described in this question: polygon triangulation algorithm and this webpage: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html I do not wish to learn the subject and have a deep understanding… >>> More