views:

642

answers:

7

Given a convex polygon represented by a set of vertices (we can assume they're in counter-clockwise order), how can this polygon be broken down into a set of right triangles whose legs are aligned with the X- and Y-axes?

Since I probably lack some math terminology, "legs" are what I'm calling those two lines that are not the hypotenuse (apologies in advance if I've stabbed math jargon in the face--brief corrections are extra credit).

A: 

Google for "polygon triangulation earclipping"

Neil N
Ear clipping is totally wrong for the question, thanks to "whose legs are aligned with the X- and Y-axes". Of course, I'm not convinced there actually is a general solution to the question as posed....
Sol
Ear clipping is not wrong, he would just have to do a more strict version of it. Adding the requirment of only right angle trianlges that are aligned with the axis' would likely produce MANY more trianlges than general ear clipping, but its still ear clipping.
Neil N
A: 

I'm not sure if this is possible. Think about a square that's already aligned with the sides on the X and Y axes. How do you draw triangles using the vertices that are also aligned to the X,Y axes?

Or are the actual sides of the polygon allowed to be along the x,y axis. Which means you could just draw a line down the diagonal of the square. If so, it might be difficult to do with a more complex polygon where some sides are aligned to the axes, while others are not.

Kibbee
In that case, you split the rectangle into two triangles.
Die in Sente
A: 

I'm not convinced there is a general solution to the question as posed. The problem is the aligned with the X- and Y-axes bit. That means that each vertex needs to be projected to the opposite side of the polygon in both the X and Y directions, and new vertices created at those intersection points. But that process must continue on for each new vertex added that way. You might get lucky and have this process terminate (because there's already a vertex appropriately placed on the opposite side), but in the general case it's just going to go on and on.

If you throw out that restriction, then Neil N's suggestion seems good to me.

Sol
+1  A: 

I'm not sure about writing an algorithm to do this but it seems entirely possible to do this for any convex polygon on a piece of paper. For each vertex project a line vertically or horizontally from that vertex until it meets another of these vertical or horizontal lines. For vertices with small changes in angle, where adjacent sides are both travelling in the same direction in terms of x and y, you will need to add two lines from the vertex, one horizontal and one vetical. Once you have done this, you should be left with a polygon in the centre of the origonal polygon but with sides that are either vertical or horizontal because the sides have been formed by the lines drawn from the vertices of the original polygon. Because these sides are either vertical or horizontal, this shape can easily be sub-divided into a number of triangles with one horizontal side, one vertical side and one hypotenuse.

Ian Turner
I think this only works if you don't care if some of the internal vertices come in the middle of edges. In my answer I assumed this wasn't allowed... guess the question doesn't forbid it.
Sol
+1  A: 

I'm assuming you've already ordered the vertices as you describe above, and that they indeed define a convex polygon.

Each vertex defines a horizontal line. For V vertices, then, you will have a set of V lines. Discard any line that meets one of the following criteria:

  • The vertex or vertices defining that line has/have the highest or lowest Y component (if one vertex, that line intersects the polygon only at that point; if two, that line coincides with a polygon edge)
  • If two vertices have equal Y coordinates otherwise, keep only one of those lines (it's duplicated).

The result will resemble a "banding" of the polygon.

Each horizontal line intersects the polygon at two points. One is its defining vertex. The other is either another vertex, or a point on a segment defined by two vertices. You can determine which is the case easily enough - just simple comparison of Y coords. The coordinates of the intersection with a segment is also easy math, which I leave to you.

Each intersection defines a vertical segment. The segment is contained within the polygon (if it coincides with an edge, you can discard it), and the other end meets either another horizontal line, or the edge of the polygon if that edge is itself horizontal. Determining the case is again a matter of mere comparison of coords. Finally, there may be 0-2 additional vertical segments, defined by the vertices with the highest and/or lowest Y coords, if there is only one of either.

The resulting diagram now shows each band with a right triangle trimmed off each end if possible. Each triangle should meet your criteria. The leftover regions are rectangles; draw an arbitrary diagonal to split each into two more right triangles meeting your criteria.

You're done.

Paul Brinkley
This falls into the same problem I have been talking about. If the horizontal line doesn't intersect another vertex, then you have to create a new vertex where it does intersect. And then you have to create a new vertical line from that new vertex, and so on.
Sol
There is no "so on", however. That vertical segment will always intersect a horizontal segment, and stop there. I'm very sure this is provable, although not in the space allowed for comments. :-)
Paul Brinkley
While I admit the problem doesn't explicitly specify this, the way this sort of thing is usually done, it can't stop there. If it did, there would be a t-junction where there is an internal vertex in the middle of the side of a triangle.
Sol
I honestly can't speak to the way this is usually done; I just wrote what I knew would work. As for a vertex in the middle of the side of a triangle, I don't know what you're referring to; my design would divide trapezoids, not triangles (except at the very top and bottom in certain cases).
Paul Brinkley
A: 

Neil N is right, I think. Unfortunate that he didn't provide any specific links.

If you have a trapezoid whose top and bottom are parallel to the X axis, you can easily render that with 4 right triangles. Call that shape a horizontal trapezoid.

If you have a triangle with one side parallel to the X axis, you can render that with 2 right triangles -- or you can consider a degenerate case of the trapezoid with the top of bottom having length zero.

Start at either the top or bottom of your convex hull (i.e. search for coordinate with min or max y) and split it into horizontal trapezoids.

It's not to hard to write the code so that it works just as well with non-convex polygons.

Die in Sente
A: 

I think this is not possible in the general case.

Consider the polygon {(0, 1), (1, 0), (2, 0)}

.
 ..

This triangle can not be split into a finite number of triangles as you describe.

Oliver Hallam