Triangularizing an arbitrary 4-Vertex Polygon

Here's a riddle for you. You have a polygon composed of exactly 4 vertices, call them v1, v2, v3, v4. They are given in any random order. How would you split these vertices into two sets, each defining a triangle, suc开发者_JAVA技巧h that both triangles make up the polygon without overlap.

The result should look like this:

Triangle 1: v1, v2, v3 Triangle 2: v2, v3, v4

... the trick is, the triangles can't overlap, and those points are given in any order, without any indication of their x,y coordinates. Is this even possible? If not, please suggest the best way to triangularize a 4-point polygon whose coordinates ARE known. I'm looking for an efficient loop.

You need to break this down into two steps:

1) Sort the vertices into clockwise order. See this question and its answers.

2) Find a diagonal which is inside the quadrilateral (if the quadrilateral is concave, only one of these will be inside. If convex, both are). See this question and its answers.

Once you've got that, it should be obvious how to find the two triangles.

It's not possible if you don't know the coordinates.

For the first triangle, pick any three points. It doesn't matter which; you will get a workable triangle.

For the second triangle, find the "far" point and remove it, substituting the remaining point.

The trick is finding the far point. Since you only have three options, you only need to perform two checks to figure out which it is (if it's not the first two, it's the third). That's about as efficient as you're gonna get.

Given the first triangle (A, B, C) and the fourth point D, the far point is the point in the triangle (pretend it's A) where the line segments (A, D) and (B, C) intersect. Simple as that.

Note that this will work with a degenerate quadrilateral triangle, but not with a line segment. Or maybe it will, depending on how you define working...

Oh well, here goes another homework...

If you have no idea about the coordinates, you might be screwed. Split it like v1,v2,v3 and v2,v3,v4. You can't do worse than this. If you know the areas or calculate them somehow, read on.

4 points are 4 triangles which makes a tetrahedron. You have a projection of it on a plane. You need to split the triangle set where the total area of each subset is equal. Probably you are using floating points so let's relax the split condition. You are looking for the minimum absolute difference.

Let's call the areas of the triangles A, B, C, D:

There are total of 2^4/2 ways you can split the triangle set.

If A+B+C+D is minimum, you either have a bug in your area calculation or you have a line segment.

If a case like A-(B+C+D) is minimum, your polygon is actually A with an extra vertex. Alternatively, you can make 3 quadrilaterals out of B,C,D if you like.

If a case like (A+B)-(C+D) is minimum, you can pick A,B or C,D

If you are actually trying to render these, you should create a vertex in the middle and make 4 triangles with the middle point as one of the verts. Otherwise I don't see whats wrong with going (v1, v2, v3), (v2, v3, v4)

[EDIT:]

Sorry, I'm thinking in 3D. This doesn't apply.