Menu
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)?
328
If no intersections are discovered, the polygon is simple. If it is not, the polygon can be viewed as a chain of two or more simple polygons, with neighboring polygons in the chain having only a finite number of corner points in common (Figure 7.20b). Each simple polygon in the chain can then be treated separately.
Count the number of times the line intersects with polygon edges. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.
In computer graphics, a complex polygon is a polygon which has a boundary comprising discrete circuits, such as a polygon with a hole in it. Self-intersecting polygons are also sometimes included among the complex polygons.
Perform line intersection tests for each pair of lines, one from each polygon. If no pairs of lines intersect and one of the line end-points of polygon A is inside polygon B, then A is entirely inside B.
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.
117
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.
25
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
