两组重叠多边形的快速映射

Question

我有两个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的每个多边形可以包含0个、1个、2个或任意数量的foreground多边形

我想知道前景的每个多边形都包含在背景的哪个多边形中。一个简单的算法是在前景f的所有多边形上循环，并测试f是否在背景层的每个多边形b内，当找到一个多边形时停止

然而，这将是可怕的性能方面，与O(Nf*Nb)缩放。使用shapely提供的算法，有没有一种简单的方法可以更快地实现这一点