python - 查找重叠的加权多边形 'highest' 区域

Question

我有许多以坐标列表形式存在的多边形。这些多边形中的每一个都代表全局 map 上的一个区域，并且每个多边形都有一个权重。

我需要在 map 上找到这个权重最高的区域。这意味着在多边形重叠的地方，权重将是相交区域的两个多边形的总和。我想让计算尽可能高效。任何帮助将不胜感激。

Answer 1

解决此问题的最简单方法是按最近的邻居对多边形进行聚类。此步骤是可选的，仅用于提高相交多边形的搜索效率。相反，也可以省略聚类，这将需要对相交多边形进行详尽搜索。

在下一步中，您可以替换两个相交的多边形 A和 B由三个多边形组成，如下所示:一个由面积 A 组成的多边形没有权重为 A 的交叉区域，B 的等效多边形，以及覆盖 A 的交叉区域的第三个多边形和 B添加权重 A和 B作为重量。替换 A和 B由三个生成的多边形和更新集群。重复此步骤，直到找不到相交的矩形，您就完成了。