Быстрое отображение двух наборов перекрывающихся многоугольников с фигурными - PullRequest
Новая
       8

Быстрое отображение двух наборов перекрывающихся многоугольников с фигурными

0 голосов
/ 05 октября 2019

У меня есть два файла geojson, каждый со списком полигонов, которые я могу легко импортировать с помощью 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])

Два набора полигонов представляют два «слоя». Все многоугольники foreground находятся внутри большего многоугольника background. Каждый многоугольник background может содержать ноль, один, два или любое количество многоугольника foreground.

Я хочу знать, в каком многоугольнике фона содержится каждый многоугольник переднего плана. Тривиальный алгоритм для этого состоит в том, чтобы зациклить все полигоны переднего плана f и проверить, находится ли f внутри каждого многоугольника b фонового слоя, и останавливаться, когда он найден.

Однако это было бы ужасно с точки зрения производительности при масштабировании O(Nf*Nb). Был бы легкий способ сделать это быстрее с алгоритмами, предоставленными shapely?

...