3

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.

enter image description here

9
  • 1
    The small polygon can be outside of the big circle, on a "corner" of the bounding box (so outside but BB is contained)
    – JGH
    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.
    – Spacedman
    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.
    – urschrei
    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?"
    – Spacedman
    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.
    – urschrei
    Sep 5, 2017 at 13:42

2 Answers 2

4

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

2

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...

enter image description here

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.

2
  • Have you just described a point-in-polygon algorithm? I'm not sure how that helps.
    – Spacedman
    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.
    – huckfinn
    Sep 5, 2017 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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