# How to determine if a Polygon is inside another Polygon's hole

Given two valid polygons `P` and `Q`, what's the cheapest / fastest way to determine:

If polygon `Q` is inside one of polygon `P`'s holes (interior rings), or vice versa. (see illustration below)

To the best of my knowledge, the DE-9IM predicates don't directly help here, since the polygons are disjoint (`FF2FF1212`) according to the matrix, so checks for containment, intersection, crossing, and within aren't useful. The best I've come up with is:

• check whether the polygons intersect
• if they don't, construct polygons from their bounding boxes, then check whether `P_bbox` contains `Q_bbox`, or vice versa.
• One polygon's bounding box will always have to be strictly smaller than the other.

But I'm wondering whether this might catch some other arrangement that I haven't thought of.

• The small polygon can be outside of the big circle, on a "corner" of the bounding box (so outside but BB is contained)
– JGH
Commented Sep 5, 2017 at 13:19
• Is the "linearly separable" question always trivially "no" given the "Given two valid polygons arranged like this (polygon Q inside P's ring)" condition. A polygon inside another polygon can't be linearly separable. Commented Sep 5, 2017 at 13:20
• @spacedman Yes, I'm trying to ensure that two polygons aren't linearly separable, but that this condition derives from this particular arrangement. Commented Sep 5, 2017 at 13:26
• Then no, two polygons arranged like this (one inside another) can't possibly be linearly separable. Is your question really "How can I tell if one polygon is inside another?" Commented Sep 5, 2017 at 13:33
• @Spacedman No, because if that were the case then a simple containment check would be enough, but it correctly returns `false` in this case (which you can verify using GEOS and presumably JTS). My question is really "Given two polygons, how can I tell if one is contained inside the ring of the other. Commented Sep 5, 2017 at 13:42

Since you are dealing with holes, you could replace such polygons with a filled version. If the polygon has an inner ring, take the outter ring and create a new temporary polygon, then check if it contains others. If yes, using the original polygon, check that it doesn't intersect the smaller one

I don't know if it is the cheapest way, because you have to calculate M Winding numbers of (P) for N points in Q.

The windings number in conjunction with the orientation of the ring could give you a clue if something is inside or outside.

I use this technique, if I want to determin if a point is inside or outside of a polygon constellation. You calculate the angles between your object in/out of the polygon and build the sum of these angles for each ring.

Here I illustrated the matter with positive or negative angles...

To prevent the usage of things like ~ 360° or ~0° only the signs of the around running angles are registered.

Sketch of the algorithm:

If the point set of Q not laying in P (abort condition...) as calculated as the sum of winding numbers S for each polygon of P with:

WS = SUM (sgn[i] * S[i]);

while:

`````` sgn[i] = 1  if it is an outer and

sgn[i] = -1 if it is an inner ring of P;
``````

You will get a result with:

if the sum for each vertex is 0 your object is outside,

if the sum > 0 it is inside.

• Have you just described a point-in-polygon algorithm? I'm not sure how that helps. Commented Sep 5, 2017 at 22:06
• @Spacedman Sorry to be unclear but, ... you have to calculate M Winding numbers of P for N points in Q and the question if the thingy is complete in-/ outside. Commented Sep 5, 2017 at 22:10