java - 给定n个几何形状的最大参与者交集区域

Question

我在 GeoJson 中定义了 n 个几何形状，我想计算包含最大数量形状的交集。

我有以下限制；

• 所有形状都不能相交(任何形状之间没有相交，0 参与者相交)
• all shapes may intersets(有一个交集是所有的shapes，n-participant intersection)
• 可能有不止一个与k个参与者的交集(形状A B C相交，形状D E F相交，有2个3人交集，不需要都找到，找到第一个3人时返回)

因此，作为起点，我虽然可以通过使用蛮力(尝试与给定形状的 n、n-1、n-2 组合相交)来做到这一点，但时间复杂度为 O(n!)。我想知道是否可以优化算法？

编辑:

好吧，我忘记了有关数据类型的内容。我正在使用 Esri/geometry形状库。具体来说，Polygon类实例。

Answer 1

这个问题感觉就像你可以构建无法有效解决的困难案例，特别是如果形状不是凸的。以下是您可以尝试的两个想法:

<强>1。迭代交集

保留一个列表 L(不相交的)多边形，开始时计数为空。现在遍历给定的多边形 P。对于来自 P 的每个多边形 p，将其与来自 L 的所有多边形 l 相交。如果 p 和 l 之间存在交集，则从 L 和

中删除 l

• 将 set_intersection(l, p) 添加到 l +1 的先前计数
• 将 set_minus(l, p) 与“l 的先前计数”相加
• 记住 set_minus(p, l) 并继续 L 的下一个条目

当你遍历 L 的所有元素后，将 p 的剩余部分添加到 L，计数为 1。

最终您将得到一个不相交的多边形列表，其计数等于参与多边形的数量。

<强>2。空间分解

围绕所有多边形构建边界框。然后迭代地拆分该空间(类似于 KD 树)。对于每一半(矩形)，计算 P 与该矩形相交的多边形数。最佳优先(始终评估计数最高的矩形)。当您处于 KD 树的某个级别时，然后停止并通过蛮力或迭代交叉进行评估。

这两种方法都将受益于在多边形周围使用最小边界矩形的过滤器。