0

I have two geojson files, each with a list of polygons, that I can import easily with shapely:

import json
from shapely.geometry import shape, GeometryCollection, Point

with open("background.json") as f:
  features = json.load(f)["features"]

background = GeometryCollection([shape(feature["geometry"]).buffer(0) for feature in features])

with open("foreground.json") as f:
  features = json.load(f)["features"]

foreground = GeometryCollection([shape(feature["geometry"]).buffer(0) for feature in features])

The two sets of polygons represent two "layers". All polygons of the foreground are inside a bigger polygon of the background. Each polygon of the background may contain zero, one, two, or any number of polygon of the foreground.

I want to know in which polygon of the background every polygon of the foreground is contained. A trivial algorithm to do that would consist to loop on all polygons of the foreground f, and test if f is within every polygon b of the background layer, and stops when one is found.

However this would be terrible in terms of performance, with a O(Nf*Nb) scaling. Would there be an easy way to do this faster with the algorithms provided by shapely?

Vincent
  • 57,703
  • 61
  • 205
  • 388
  • 1
    Nothing comes to mind other than using https://shapely.readthedocs.io/en/stable/manual.html#object.contains. Depending on how expensive this operation is you could try to do some pre processing on the sets. Get rid of polygons that are completely inside other polygons, sort them on their area with the idea being large polygons have a higher chance of containing all other polygons etc – Mitch Oct 05 '19 at 00:29
  • Could the following be of any help? [Faster way of polygon intersection with shapely](https://stackoverflow.com/q/14697442/7851470) – Georgy Oct 05 '19 at 08:27

0 Answers0