2

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.
    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 form [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:

alt text

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.

IVlad
  • 43,099
  • 13
  • 111
  • 179
  • Please check. Seems very similar to this one http://stackoverflow.com/questions/693837/how-to-determine-a-diagonal-is-in-or-out-of-a-concave-polygon – Dr. belisarius Dec 07 '10 at 19:14
  • I suspect that there are additional conditions to the algorithm you described (even for points of the form [p, p+2]) because it is easy to construct counter examples where the algorithm says it is interior but the polygon intersects the line segment - e.g. a hexagon with a single concave vertex, testing [p-1, p+1] where p is 3 vertices away from the concave vertex. – lijie Dec 07 '10 at 19:18
  • @lijie - not really, that will be covered by step 1 of the algorithm. @belisarius - I'll check it. – IVlad Dec 07 '10 at 19:22
  • 2.1. looks like it is testing that pj is in the "interior" of the convex angle defined by pi-1, pi, pi+1. In that case, can't 2.2. be modified so that it tests that pj is in the "exterior" of the convex angle defined by pi+1, pi, pi-1? – lijie Dec 08 '10 at 14:56
  • @belisarius - I've checked that questions but couldn't get the posted solution to work in all cases, so I'd like to leave this open for a little while. @@lijie - I tried to, but was able to find counterexamples for all my attempts. Any suggestion on how to do it? – IVlad Dec 08 '10 at 16:30
  • @IVlad Ok. I was not sure, it was just a suggestion. – Dr. belisarius Dec 08 '10 at 20:14
  • 1
    oh.. if i change 2.2 as suggested (if pi is a concave point, then [pi, pj] is an inner diagonal iff pi, pj, pi-1 _or_ pi, pi+1, pj make a right turn) what's the counterexample? (note _or_ instead of _and_) – lijie Dec 10 '10 at 14:59
  • @lijie - I can't find one. I'll keep looking, but until then you might want to post it as an answer... – IVlad Dec 11 '10 at 16:32

3 Answers3

1

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.

lijie
  • 4,811
  • 22
  • 26
0

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.

ruslik
  • 14,714
  • 1
  • 39
  • 40
0

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.

dmuir
  • 449
  • 2
  • 3