标识联合多边形的原始边

Question

我有很多多边形,在我做了所有这些多边形的联合之后,我得到了一个新的大多边形.联合算法是一个黑盒子,使用我无法控制的第三方库过程,我也不希望从任何进展中提取任何信息.

对于那个巨大的巨大联合多边形的每个边缘,它是否有效的方法让我知道哪个属于较小多边形的哪个边缘？

解决这个问题的一种强力方法是将工会化多边形的每个边缘与每个较小的多边形进行比较,但这将是非常低效的.还有其他更有效的技术吗？

我的预感告诉我,扫描线算法可能会有所帮助,虽然我完全不知道如何做到这一点.

编辑:小的npolygons可以重叠,因此union多边形可以包含位于小多边形边缘的点,但这些点可能不是原始多边形的顶点.

截图如下所示:

Answer 1

由于联合中出现了新的边和顶点，这种朴素的方法不起作用（请参阅旧的答案和注释），因此我们需要采用更复杂的数据结构。

这个想法是识别输入集中包含输出集边缘的边缘。我所说的“包含”是指输出集的边的两个顶点都需要位于输入集的边上。因此，我们需要在输入边集中搜索包含一条穿过我们正在考虑的边的两个顶点的线段的边。

过滤掉大量搜索边集的一个简单方法是使用边界框：如果我们正在检查的顶点不在由边的两个顶点形成的边界框内，那么我们可以规则它出去。主要算法是：

输入：输出多边形 E1 的一条边，以 V1 和 V2 作为端点。

输出：输入多边形的一条边，其中 V1 和 V2 都在边上。

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

第二步是显而易见的。对于第一个，有几个地方需要注意。KD 树（体积对象）看起来可以解决这个问题。或者可能是 R 树。另请检查 stackoverflow 是否有类似问题。不幸的是，我不太熟悉空间算法，无法提出合适的算法。

旧答案：

我认为您不需要任何花哨的数据结构来处理这种情况。我假设联合中顶点的坐标与原始集中顶点的坐标相同。因此，您可以执行以下操作：为输入数据创建一个顶点列表，其中每个顶点记录它所属的多边形。让这些易于搜索：一种简单的方法是首先按一个坐标对它们进行排序，然后再按另一个坐标排序。你可以用这种方式在 O(log n) 中找到任何顶点。

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

最后的优化是预计算：只需运行上述算法，并记录每条边的结果，然后删除所有顶点和边表。如果不需要预先计算的表，则可以过滤掉未出现在并集中的顶点的原始顶点集。