19
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Do you need to do this in code, by any chance? What language if so? Because this is almost certainly implemented by some library. $\endgroup$ – jpmc26 May 9 '17 at 20:43
  • $\begingroup$ @jpmc26 im doing it in python, but i'd like to write the code from scratch $\endgroup$ – dimebucker May 9 '17 at 22:48
  • $\begingroup$ This checks if the minimal AABB of one polygon fully contains the minimal AABB of the other. $\endgroup$ – user253751 May 9 '17 at 23:40
  • $\begingroup$ The 'simple' answer to this is to a) check if the polygons intersect (in which case this is false) and then if not b) check if any vertex in one polygon is inside the other polygon. Of course, checking if polygons intersect is difficult enough... $\endgroup$ – TLW May 11 '17 at 1:30
20
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Even "none of the sides of the two polygons intersect and that one vertex is inside" if a vertex of one lies on a side (or vertex) of the other - you'd need to check that the two edges leaving the vertex were both either inside or outside. $\endgroup$ – Julia Hayward May 9 '17 at 14:41
  • 5
    $\begingroup$ @JuliaHayward Wouldn't those count as intersections? Vertexes are endpoints of sides. $\endgroup$ – jaxad0127 May 9 '17 at 17:50
  • $\begingroup$ @jaxad0127 I think you'd have to define what behaviour you wanted. Does the polygon have to be strictly inside, or are common boundary points OK? If the latter then there are probably lots of special cases to check. $\endgroup$ – nickgard May 10 '17 at 7:29
8
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ ah..wow can't believe i missed that...do you know of a way that works? $\endgroup$ – dimebucker May 9 '17 at 14:10
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ could you expand on the segment-segment test? do you have an example or a reference? $\endgroup$ – dimebucker May 10 '17 at 0:17
  • $\begingroup$ Write $\begin{cases}x_0+p(x_1-x_0)=x_2+q(x_3-x_2),\\y_0+p(y_1-y_0)=y_2+q(y_3-y_2)\end{cases}$, solve for $p,q$ and check that they are in $[0,1]$. But you can do your own Web search. $\endgroup$ – Yves Daoust May 10 '17 at 6:10
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ unfortunately it is not always the case, the polygons are a mix of convex and concave $\endgroup$ – dimebucker May 9 '17 at 14:11
  • 1
    $\begingroup$ @dimebucker91 - but you can test if any of the line segments of the candidate inner polygon intersect the other polygon. If so, then it is not contained. If not, and one of the vertices tests as inside, then the entire polygon is inside. $\endgroup$ – Paul Sinclair May 9 '17 at 16:43
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

I don't want to spoil your party, but in my belief you need a more complex algorithm for guaranteeing that P1 is fully inside P2:

  • All vertices of P1 must be inside P2
  • All segments of which P1 consists must not cross any segment of P2

As for the first condition, you might do the following: p1 is a point of P1, and it has cartesian coordinates (x1, y1). Draw a ray from (-infinity,y1) to (x1, y1), and count the number of crosspoints between that segment and all segments of P2. If the amount is odd, then p1 is inside P2, if the amount is even, then p1 is outside P2.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.