Check if polygon is inside a polygon

CodeChuck picture CodeChuck · Jan 28, 2011 · Viewed 26.7k times · Source

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.

Answer

moinudin picture moinudin · Jan 28, 2011

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.