Test for strictly simple polygon (holes are allowed)?

Question

I'm looking for an algorithm to test whether or not a polygon is 'strictly' simple. Usually the test involves checking for intersection between any of the polygon segments. But here, since I want to check for cases that don't always fall under edge-edge intersection, I'm not too sure what to look for.

In the above image, B C and D aren't simple polygons, but only D would fail the intersection test. My terminology (in terms of strictly simple) may be a little off as well, but I think the picture illustrates what I mean.

Answer 1

Say two lines do intersect if they have at least a common point.

Take one edge and count the intersections with any other edges. If it has

• 2 intersections, then it has one edge left and one edge right and everything is good.
• more than 2 intersections, then it has either more than two edges starting at the end points (case B), an endpoint of an edge in the middle (case C) or an intersection with another line (case D).

So in my opinion, your worries are ill-founded:

But here, since I want to check for cases that don't always fall under edge-edge intersection [...]

This approach works here too.