Polygon-in-polygon testing

I have a list of vertices of simple polygons, and I would like to test whether or not a polygon is fully contained in another polygon in the list.

Is it sufficient to do something like:

Let $p_0$ be the candidate polygon.

Let $r_i, ~le_i, ~u_i, ~l_i$ denote the right most, left most, upper most and lower most vertex of the ith polygon in the list.

For all polygons in the list, if any polygon has:

$r_i(x) \ge r_0(x)$ AND
$le_i(x) \le le_0(x)$ AND
$u_i(y) \ge u_0(y)$ AND
$l_i(y) \le l_0(y)$

where for example $r_i(x)$ denotes the $x$-coordinate of the rightmost vertex of the $i$-th polygon, then we may conclude that $p_0$ is fully contained within $p_i$.

Does this make sense, and is there a counter example for which this algorithm doesn't work?

Solution 1:

The picture shows some counterexamples, including one that shows the problem is not even as easy as checking that all vertices of one polygon are inside the other polygon.

One possible approach would be to check that none of the sides of the two polygons intersect and that one vertex is inside.

See for example: https://stackoverflow.com/a/4833823

enter image description here

Solution 2:

Let $p_1$ be the quadrilateral with vertices $(1,0), (0,1), (-1,0), (0,-1)$. Then your conditions are for the bounding box $b$ of $p_1$, not for $p_1$ itself. In particular, a small $p_0$ fits in one corner of $b$ but is completely outside $p_1$.

It is not even sufficient to use a point-in-polygon algorithm to test whether the vertices of $p_0$ are all inside $p_1$ because $p_1$ might not be convex.

The only general way is to check that their union is $p_1$. For that you may need a polygon clipping tool like gpc. See also the Weiler–Atherton clipping algorithm and boolean operations on polygons.

Solution 3:

No, this doesn't work at all.

enter image description here

This bounding box test guarantees that the polygons are disjoint, when the boxes are disjoint. Otherwise it says nothing.

A relatively simple and correct test is to check that there are no pairwise side intersections, which is done by exhaustive segment-segment intersection tests. Then either the polygons are disjoint or one wholly included in the other. You make the final decision by taking some vertex and applying a point-in-polygon test wrt the other polygon.

If you are after an efficient solution, you can resort to a sweepline algorithm, during which you sweep an horizontal line across all vertices and maintain a list of the horizontal segments the polygons are cutting. Then you reduce to a 1D segment containment problem.

Solution 4:

If the containing polygon is convex you can check whether the vertices of the inner polygon are inside using known algorithms for computing the convex hull of a set of vertices.

See https://en.wikipedia.org/wiki/Convex_hull_algorithms

Edit: Since your polygons need not be convex I suspect there's no very easy answer. Perhaps you can look at the convex hull algorithms and find a way to modify one to check whether every vertex of the inner polygon is on the correct side of every edge of the outer one. @lhf points to gpc, which looks promising.

Solution 5:

Your test is a necessary, but not sufficient condition for insideness.

While this might sound useless, you can use your test as a quick first test to exclude most of the possibilities, and then go to a more complicated test to decide the remaining cases.

You don't want to use the complicated test on every possible combination since this could be very slow, depending on $n$.

I think the fastest complete test would be:

Every vertex of $p_0$ must be inside $p_i$, and every vertex of $p_i$ must be outside $p_0$.

So, how do you test whether a point is inside a polygon?

This is a very well studied problem with many web resources available. Starting with the Wikipedia page I found this page which describes two algorithms. If that link breaks, a web search will give you many others.