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?
Best Answer
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