Finding the diagonals of a polygon

Given a concave polygon (with no self-intersections), with its nodes in clockwise order, how can we determine all of its inner diagonals (those that are inside the polygon)?

I am interested in a solution that doesn't use any trig functions.

Background and what I tried:

In my computational geometry class we were given the following algorithm to test whether [pi, pj] is an inner diagonal in a polygon p0, p1, ... pn-1:

1. Test if [pi, pj] intersects an edge of the polygon that is not adjacent to it. If yes, it's not an inner diagonal. If not, go to step 2.
2. 1. if pi is a convex point (pi-1, pi, pi+1 make a right turn), then [pi, pj] is an inner diagonal iff pi, pj, pi+1 and pi, pi-1, pj make a left turn.
   2. if pi is not a convex point (pi-1, pi, pi+1 make a left turn), then [pi, pj] is an inner diagonal iff pj, pj-1, pi make a left turn.

This algorithm was given to us for a triangulation algorithm involving ear-clipping. I implemented that algorithm and it seems to work fine there, but the catch is that the ear-clipping algorithm only uses diagonals of the fo开发者_开发技巧rm [pi, pi+2].

However, consider the brute force triangulation algorithm that selects all non-intersecting diagonals. Using what I described as a subroutine for checking inner diagonals (together with a segment intersection method), I get the following result:

It's easy to check that the algorithm I posted rejects the inner diagonal [3, 6], when in fact it shouldn't:

3 is not a convex point, and 6, 5, 3 make a right turn instead of a left turn, so it gets rejected.

Note that, when using the ear-clipping algorithm, this polygon is triangulated correctly.

I am interested in how this algorithm can be adapted to detect all diagonals in a polygon. I've had no luck getting it to work.

I have also found other problems with this method, such as polygons for which exterior diagonals are drawn. Again, those work with the ear-clipping algorithm. We were never told that this method only applies for a special form of diagonals however, so I'm looking for clarifications.

Note: I couldn't decide whether to post this on math.stackexchange.com or here, since computational geometry deals in somewhat equal measure with both programming and mathematics, however I felt that programmers might be more familiar with this kind of algorithms than mathematicians, since someone has probably actually implemented this at some point.

Section 2.1 of the algorithm looks like it is testing that pj is in the "interior" of the convex angle defined by pi-1, pi, pi+1.

Section 2.2 can be derived from Section 2.1 so that it tests that pj is not in the "interior" of the convex angle defined by pi+1, pi, pi-1. This is basically NOT (pi, pj, pi-1 and pi, pi+1, pj make a left turn) == pi, pj, pi-1 or pi, pi+1, pj make a right turn.

So the entire clause would be "if pi is a concave point, then [pi, pj] is an inner diagonal iff either pi, pj, pi-1 or pi, pi+1, pj (or both) make a right turn.

Several notes:

1) It's easy to check if the diagonal is inner, by comparing the angles (for example, for diagonal 4-6 the angle 3-4-5 is larger than angle 3-4-6, so it's inner diagonal). I'm sure it can be simplified by a vector product, but my math isn't so good.

2) To check if a particular inner diagonal don't intersect other edges, you can check if the points of the polygon are on the expected side. Ex: if we try diagonal 1-4, the points 2 and 3 should be on one side, and points 5, 6 and 7 on other. If it does not hold, then the diagonal intersects an edge.

Note sure how efficient this would be, but you could compute the convex hull, and then get a list of polygons (the "excluded" polygons) that are in the convex hull but not in the original polygon. (In your example the convex hull would have vertices 1,2,4,5,7, so that the excluded polygons would be (2,3,4), (5,6,7).) Then the diagonals you want are the diagonals of the original polygon that don't intersect any of the excluded polygons. But note that the excluded polygons might not be triangles, indeed might not be convex, so the line intersection test might be awkward.