Splitting A Polygon into Separate Triangles
Author
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.
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
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-------cQuote:Original post by agaudreau
A 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?
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
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
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
http://www.geometrictools.com/SampleFoundation/Triangulation/Triangulation.html
With best regards,
Kimmi
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.
Now, if you want to associate some cost to each triangle to minimize/maximize, then the problem is NP-complete.
Author
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.
Polygon triangulation sounds like it might be what I'm after.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
