识别并确定合并多边形的原始边界

Question

我有很多多边形，当我对它们进行联合后，我得到了一个新的大多边形。联合算法是一个黑盒子，使用第三方库进行处理，我无法控制，也无法希望提取任何进度信息。

有没有有效的方法可以让我知道这个巨大的联合多边形的每条边属于哪个小多边形的边？

解决这个问题的暴力方法是将联合多边形的每条边与每个小多边形的每条边进行比较，但这将非常低效。是否有其他更有效的技术？

我的直觉告诉我扫描线算法可能会在这里有所帮助，尽管我完全不知道该如何做。

编辑：小多边形可能重叠，因此联合多边形可能包含位于小多边形边缘的点，但这些点可能不是原始多边形的顶点。

下面显示了此内容的屏幕截图：

- Graviton

---

你如何“合并”你的多边形？我的猜测是，在进行合并时，你可以在某个地方存储小多边形边缘与大多边形对应边缘之间的关联。 - B. Decoster

@Fezvez，这个联合是我无法控制的。请查看更新后的问题。 - Graviton

Answer 1

这里是一种解决方案。

获取每条原始边。它们可以由3个东西（过）指定：

1. 指示方向的向量
2. 起点
3. 终点

第一步是对向量进行归一化（例如，乘以标量使得x和y中绝对值较大的那个为1）。然后将所有的边存储到一个哈希表中，其中键是那些向量，值是具有该向量的边的数组。（如果你有很多边，你可能考虑使用interval tree来处理边。）

现在，给定组合多边形上的一条边，您可以确定它的向量，查看您的哈希表，通常只会有少量原始多边形中具有该确切向量的边，因此不难通过它们并确定哪些重叠。

请注意，虽然这种解决方案将让您相当高效地找到边沿界运行的情况，但它将错过一个多边形仅在组合多边形的一个角落处接触边界的情况。希望这对您没有影响。

- btilly

---

“错过多边形仅在组合多边形的一个角落处接触边界”的意思是什么？从我所看到的来看，它不会，因为组合多边形上的所有边缘都以某种方式位于原始多边形的边缘上，对吧？ - Graviton

@Graviton，拿一个五边形，将其切成4个三角形，它们在一个角落相遇。所有4个三角形都接触该角落，但是这个算法只会注意到其中2个三角形接触了该点。 - btilly

我能想象出你提到的五边形，但是我在这种情况下运行了你的算法，但仍然得不到我想要的答案；这里有什么问题？ - Graviton

@Graviton：这取决于你的需求。你将会错过一些单点交集。但我猜想你对此并不在乎。如果你不在乎，那么这个解决方案就满足了你的要求。 - btilly

Answer 2

由于朴素的方法在并集中出现新的边和顶点（请参见旧答案和评论）而无法工作，因此我们需要使用更复杂的数据结构。

思路是在输入集中识别包含输出集边缘的边缘。通过“包含”，我的意思是输出集中的边缘的两个顶点都需要在输入集的边缘上。因此，我们需要搜索输入边缘集以找到一个包含通过我们考虑的边缘的两个顶点的线段的边缘。

过滤掉大量搜索边缘集的简单方法是使用边缘框：如果我们正在检查的顶点不位于由边缘的两个顶点形成的边界框内，则可以将其排除。然后，主要算法如下：

输入：来自输出多边形的边缘E1，V1和V2为端点。

输出：来自输入多边形的边缘，其中V1和V2都在边缘上。

- 获取输入集中的边缘集，其边界框包含V1和V2（或换句话说，由V1，V2形成的边界框） - 暴力搜索同时包含V1和V2的边缘。

第二步很明显。第一步有几个地方需要查看。K-D tree（体积对象）似乎可以解决问题。或者也可以考虑R-tree。此外，可以在stackoverflow上查找类似的问题。不幸的是，我对空间算法不是很熟悉，无法建议一个合适的算法。

---

旧答案：

我认为你不需要任何复杂的数据结构来处理这种情况。我假设联合顶点的坐标与原始集合中的顶点坐标相同。因此，你可以做如下操作：为输入数据创建一个顶点列表，每个顶点记录它所属的多边形。使这些顶点易于搜索：一种朴素的方法是先按一个坐标排序，然后再按另一个坐标排序。你可以用 O(log n) 的时间找到任何一个顶点。

现在，对于联合多边形的任何给定边，搜索该边的第一个顶点，然后搜索另一个顶点。取它们所属的多边形的交集，就得到了原始多边形。为加速搜索第二个顶点，你还可以向原始列表中添加连接的顶点列表，这样就不必再进行完整的搜索。

最后一个优化是预计算：只需运行上述算法，并记录每条边的结果，然后摆脱所有顶点和边表。如果你不需要预计算表，你可以过滤出在联合中没有出现的顶点。

- vhallac

---

不太确定这是否有效，因为当我联合所有多边形时，新的顶点（不属于原始多边形的顶点）可能会出现在联合多边形中。 - Graviton

你可能需要澄清问题。对于新顶点出现的情况，上面的简单解决方案将不足以解决问题。您还需要描述这些新顶点的特征：如何确定它们是否属于原始多边形？ - vhallac

我的意思是，想象一下如果两个多边形重叠，那么这两个多边形的并集将会产生一些不在原始两个多边形顶点上的点，而是位于多边形的边缘。这就是我所说的新顶点出现的意思。 - Graviton

@Graviton 已经知道了，为了这种情况，您需要一个更好的数据结构来快速确定可能包含这个新顶点的边。K-D 树似乎可以解决这个问题。如果我能找到什么东西，我会更新答案。 - vhallac

Answer 3

您可以使用多边形边缘创建BSP或更具体的四叉树。对于每个边缘，请记住它在哪些多边形中使用。

对于输出多边形中的每个边缘，执行树搜索并仅检查与四叉树叶节点中的边缘重叠。

假设原始多边形中有n条边缘，输出多边形中有m条边缘。创建树需要O(n log n)，搜索边缘重叠需要O(m log n)。总体时间复杂度为O((m+n)*log n)。

注意：如果整个边缘在两个初始多边形中都被使用，则不在输出多边形边界上。通过这种方式，您可以从四叉树中删除重复的边缘。不是必需的。

也可以采用其他方法。创建输出多边形边缘的四叉树，并搜索每个初始多边形的边缘。运行时间为O((m+n)*log m)，速度更快。但是，使用上述方法，如果将来需要从输入多边形中提取更多信息，则可以实现此目的。

- Ante