'Testing whether a polygon is simple or complex
For a polygon defined as a sequence of (x,y) points, how can I detect whether it is complex or not? A complex polygon has intersections with itself, as shown:
Is there a better solution than checking every pair which would have a time complexity of O(N2)?
Solution 1:[1]
There are sweep methods which can determine this much faster than a brute force approach. In addition, they can be used to break a non-simple polygon into multiple simple polygons.
For details, see this article, in particular, this code to test for a simple polygon.
Solution 2:[2]
See Bentley Ottmann Algorithm for a sweep based O((N + I)log N) method for this. Where N is the number of line segments and I is number of intersection points.
Solution 3:[3]
In fact, this can be done in linear time use Chazelle's triangulation algorithm. It either triangulates the polygon or find out the polygon is not simple.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Andy Baker |
| Solution 2 | |
| Solution 3 | Chao Xu |