标识联合多边形的原始边缘

        这是一个解决方案。 取每个原始边缘。它们可以由3件事指定（超过）： 指示方向的向量 初始点 终点 第一步是对向量进行归一化（例如乘以标量，以使

x

和

y

的绝对值中的较大者为1）。然后将所有边缘存储到一个哈希中，该哈希的键是那些向量，其值是该向量的边缘数组。 （如果边缘很多，则可以考虑使用间隔树作为边缘。） 现在给定组合多边形上的一条边，您可以找出它的向量，在哈希表中查找，并且在原始多边形中通常只有少量具有该精确向量的边，所以也不太可能很难通过它们，找出哪些重叠。 请注意，虽然此解决方案可以让您相当有效地找到边缘沿边界延伸的情况，但会漏掉多边形仅在一个角触及组合多边形的边界的情况。希望对您来说无关紧要。     

由于幼稚的方法由于联合中出现了新的边缘和顶点而无法工作（请参见旧的答案和注释），因此我们将需要采用更复杂的数据结构。 这个想法是要识别输入集中包含输出集边缘的边缘。 “包含”是指输出集的边的两个顶点都必须在输入集的边上。因此，我们需要在输入边集中搜索一个包含一条线段的线段，该线段穿过我们正在考虑的边线的两个顶点。 筛选出大量用于搜索的边集的一种简单方法是使用边界框：如果我们要检查的顶点不位于由一条边的两个顶点形成的边界框内，则可以确定出来。那么主要算法是： 输入：以V1和V2为终点的输出多边形E1的边。 输出：输入多边形的边，其中V1和V2都在边上。 从输入集中获取其边界框同时包含V1和V2的边集（或换句话说，由V1，V2形成的边界框） 蛮力搜索V1和V2都位于的边缘。 第二步是显而易见的。有几个地方可以寻找第一个。 K-D树（体积对象）看起来可以解决该问题。或者也许是一棵R树。还要检查stackoverflow中是否存在类似问题。不幸的是，我对空间算法不是很精通，可以提出一个合适的算法。 旧答案： 我认为您不需要任何精美的数据结构来处理此案。我假设联合中顶点的坐标与原始集中的坐标相同。因此，您可以执行以下操作：为输入数据创建一个顶点列表，其中每个顶点记录其所属的多边形。使它们易于搜索：天真的方法是先按一个坐标对它们进行排序，然后再按另一个坐标对它们进行排序。这样就可以在O（log n）中找到任何顶点。 现在，对于联合多边形的任何给定边，搜索该边的第一个顶点，然后搜索另一个。取多边形所属的集合的交集，即可得到原始多边形。为了加快第二个顶点的搜索速度，您还可以将连接的顶点列表添加到原始列表中，这样就不必再次进行完全搜索。 最终的优化是预先计算：只需运行上述算法，并记录每个边的结果，然后除去所有顶点和边表。如果不需要预先计算的表，则可以过滤掉未出现在并集中的顶点的原始顶点集。     

        您可以使BSP或更具体的四叉树具有多边形边缘。对于每个边缘，请记住在哪个多边形中使用该多边形。 对于输出多边形中的每个边缘，请执行树搜索，并检查边缘是否仅与四叉树叶节点中的边缘重叠。 在原始多边形中有

n

个边，在输出多边形中有

m

个边。要创建树

O(n log n)

，需要搜索边缘overlapping5ѭ的重叠。总体为

O((m+n)*log n)

。 注意：如果在2个初始多边形中使用整个边缘，则在输出多边形边界中不使用整个边缘。这样，您可以从四叉树中删除重复的边。不必要。 可以采用其他方式。创建输出多边形边的四叉树，并搜索初始多边形的每个边。运行时间是

O((m+n)*log m)

，这是更快的。但是如果您将来需要，可以使用高级方法从输入面中提取更多信息。