# Splitting A Polygon into Separate Triangles

This topic is 3582 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a concave polygon that I need to split up into a series of individual triangles,but I'm not quite sure of the correct method to do so.

##### Share on other sites
Maybe I'm misunderstanding, but a polygon can't be concave or convex can it? Given that it's 3 points..

How do you want to split your polygons? One way is to just pick an edge, pick a point on the edge (linear interpolate between start and end of the edge), and generate a point there. ie

Given triangle abca|.| .|  .|   .|    .|     .|      .b-------cGenerate point d along ac. Using the equation of a line, P(t) = (1-t) a + tc , where t is a scalar  0<= t <= 1a|.| .|  .|   d|    .|     .|      .b-------cThen create two triangles, abd and bcd,a|.| .|  .|   d|  / .| /   .|/     .b-------c

##### Share on other sites
A triagle only has 3 points, a polygon can have infinite points. ^^

##### Share on other sites
Quote:
 Original post by agaudreauA triagle only has 3 points, a polygon can have infinite points. ^^

That's a good point!

In which case, OP can you explain your setup a bit more?

##### Share on other sites
I am guessing you have a container of verticies that make up some sort of complex shape.

with no other information I dont think it is possible to designate triangles correctly in every case. Now if you had some more information, like what verts touch other verts via 'edges' or something like that, maybe we would be able to help a bit more.. maybe

##### Share on other sites
Sounds to me like polygon triangulation.

##### Share on other sites
Maybe the GeometrcTools-Website could be helpful. Take a look onto the following link:
http://www.geometrictools.com/SampleFoundation/Triangulation/Triangulation.html

With best regards,

Kimmi

##### Share on other sites
The problem as stated is sort of ambiguous. If you just want to triangulate some planar polygon, then you can use a simple greedy algorithm: While the polygon is not totally covered, remove a triple of vertices contained in the remaining polygon. Eventually you will cover the whole polygon with the triangles you remove.

Now, if you want to associate some cost to each triangle to minimize/maximize, then the problem is NP-complete.

##### Share on other sites
It's like, I have an array of points, now previously I was using the fillPolygon method of the Graphics object in .NET to draw the polygon which would join up the points and fill it in, but I've since changed to using XNA instead, which means that I'm pretty much stuck using triangles when drawing primitives, so the only way I can see would be to split up my polygon into individual triangles and draw it that way, I also can't have them overlap as I plan on making them see-through and of course in that situation if they did overlap, some parts would be more transparent than others.

Polygon triangulation sounds like it might be what I'm after.

##### Share on other sites
I suggest looking at the Ear Clipping method of triangulation. There is a PDF on it here.

1. 1
Rutin
41
2. 2
3. 3
4. 4
5. 5

• 18
• 20
• 14
• 14
• 9
• ### Forum Statistics

• Total Topics
633369
• Total Posts
3011535
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!