Menu
Yesterday I was looking to check if a point was inside a polygon and found this great script: https://github.com/tparkin/Google-Maps-Point-in-Polygon
But today at work I was told that our client needs to check if one polygon is inside another polygon. I am wondering if is there a formula where I can take, let's say, two coordinates (instead of one to check a point), and from those two coordinates generate a rectangle and check if that rectangle is inside a polygon.
I don't know if I'm asking a stupid question (a teacher in highschool used to say "there are no stupid questions, there is only fools who don't ask"), but if you don't understand me totally but just a bit, I'd be grateful if you just tell me where to start.
681
using a function called . within() that checks if a point is within a polygon. using a function called . contains() that checks if a polygon contains a point.
Offset the polygon inwards by distance = circle's radius. If the resulting polygon is still a valid polygon (i.e., is not self-intersecting) and maintain the same vertices traversing orientation, check if the circle's center is inside the offset polygon. If yes, the circle is inside the original polygon.
A point is on the interior of this polygons if it is always on the same side of all the line segments making up the path. Given a line segment between P0 (x0,y0) and P1 (x1,y1), another point P (x,y) has the following relationship to the line segment.
The point will be inside a convex polygon if and only if it lies on the same side of the support line of each of the segments. That is, either it lies on the left of every line or it lines on the right of every line.
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.
The above works for any type of polygon. If the polygons are convex, you can skip the line intersection tests and just test that all line end-points of A are inside B.
If really necessary, you can speed up the line intersection tests using the sweep line algorithm.
154
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.
24
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
