Menu
I have number of simple polygons which do not intersect each other but some polygons may be embedded into others.
For example:
+--------------------------------------------+
| |
| +----------------+ +--------+ |
| | | / | |
| | +--------+ | / | |
| | | | | / +----(2)-+ |
| | | | | / | |
| | +----(3)-+ | / | +---+ |
| | | +-----+ | | |
| +------------(2)-+ +(2)+ |
| |
+----------------------------------------(1)-+
How to find out the "depth" of all the polygons? In other words, how to find out by how many polygons a polygon is encompassed by? The "depth" are the numbers in parentheses.
I could count how many times a point of a polygon is inside of all the other polygons but this has quadratic complexity. How to compute those depths faster?
296
First check that one of the corner points in the polygon is inside the other polygon using the script. Then check if any of the lines in the polygon crosses any of the lines in the other polygon. If they don't, the polygon is inside the other polygon.
An interior angle of a polygon is an angle formed inside the two adjacent sides of a polygon. Or, we can say that the angle measures at the interior part of a polygon are called the interior angle of a polygon.
One simple way of finding whether the point is inside or outside a simple polygon is to test how many times a ray, starting from the point and going in any fixed direction, intersects the edges of the polygon. If the point is on the outside of the polygon the ray will intersect its edge an even number of times.
Draw a horizontal line to the right of each point and extend it to infinity. 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.
Put your polygons into some kind of spatial lookup structure, for example an R-tree based on the minimum bounding rectangles for the polygons. Then you should be able to compute the containment relation that you're after in O(n log n). (Unless you're in a pathological case where many of the minimum bounding rectangles for your polygons overlap, which seems unlikely based on your description.)
Edited to add: of course, you don't rely on the R-tree to tell you if one polygon is inside another (it's based on minimum bounding rectangles so it can only give you an approximation). You use the R-tree to cheaply identify candidate inclusions which you then verify in the expensive way (checking that a point in one polygon is inside the other).
174
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
