[GIS] How to computational efficiently check if there are any overlapping polygons in a group of polygons

analysisogrpolygonpythonshapely

I need to do some processing with groups of polygons. If any of the polygons in the group overlaps other polygon the result is unpredictable and don't throw any error. So, I need to detect if there is any overlapping polygon inside the group and which polygons are overlapping.

The groups are made of about 15 polygons, so checking each polygon against the others would be costly. I wonder if there is an efficient way to do that.

The code is in Python and can use either the OGR bindings or Shapely.

A theoretical answer is also appreciated.

Best Answer

There are 105 combinations for testing the intersections of pairs of fifteen polygons, or mathematically (using combinations) expressed as 15 choose 2, or symbolically (15 over 2).

To borrow some similar logic with Shapely, you can do this:

from itertools import combinations

# gather the 15 Shapely polygons in something iterable, like a list
shapes = [poly1, poly2, ..., poly15]

# test the intersection on the combinations of pairs
intersections = [pair[0].intersects(pair[1]) for pair in combinations(shapes, 2)]
# intersections is a list with 105 elements of True or False

if any(intersections):
    print("yes, %d of %d combinations intersect" % (sum(intersections), len(intersections)))
else:
    print("no intersections")
Related Question