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

  • 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 '17 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 '17 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 '17 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 '17 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 '17 at 13:42
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.

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

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.