Strictly simple polygon test (holes allowed)?
I'm looking for an algorithm to test if a polygon is "strictly" simple. Typically the test involves checking the intersection of any of the polygon segments. But here, since I want to check for cases that don't always fall under the cross-border, I'm not too sure what to look for.
In the above image, BC and D are not simple polygons, but only D will complete the intersection test. My terminology (in strictly simple terms) may also be a little inadequate, but I think the picture illustrates what I mean.
source to share
Let's say that two lines intersect if they have at least a common point.
Take one edge and count the intersections with any other edges. If he has
- 2 intersections, then it has one edge on the left and one edge on the right, and all is well.
- more than two intersections, then it has either more than two edges, starting at the endpoints (case B), the endpoint of the edge in the middle (case C), or an intersection with another line (case D).
So, in my opinion, your worries are unfounded:
But here, since I want to check for cases that do not always fall into the cross-intersection of the edge [...]
This approach works here as well.
source to share
These three classes of invalid polygons must be checked independently.
Case B:
Make sure there are no duplicate vertices in your polygon.
Case C:
Make sure the vertices don't hit any edges. Assuming you are using floating point numbers, this can be tricky because the floating point numbers would have to be the same. This can be circumvented by saying that they cannot be within EPS
each other, but that could invalidate some other polygons that are almost invalid. I personally would use it EPS
myself if I didn't need the utmost precision (at this point I don't know what I would do).
Case D:
As you said, this can be found by checking if any edges intersect.
Case E: Two edges overlap (intersect at infinitely many points), but their vertices do not have.
I'm not sure if this should be a separate case, but this situation cannot be solved by checking for case D (I think you end up dividing by zero). Therefore, you will also need to check that the two edges do not match exactly the same string.
I cannot think of any other cases at the moment
source to share