Jump to content
• Advertisement

Splitting A Polygon into Separate Triangles

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

If you intended to correct an error in the post then please contact us.

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

Share on other sites
Advertisement
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 this post

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

Share this post

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

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

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

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

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

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

Share this post

Share on other sites

• Advertisement
• Advertisement

• Popular Now

• 10
• 16
• 14
• 18
• 15
• Advertisement
• Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!