将重叠的凸多边形合并成一个凹多边形的最佳方法是什么？

给定一个顶点，您可以通过以下方法加速搜索“重叠”的顶点或边：

查找顶点

假设坐标是精确的，也就是说如果两个顶点重叠，它们的x、y坐标完全相同，没有任何不精确的误差，那么最好先按x坐标创建哈希表，然后对于每个x条目，您会有一个按y坐标创建的哈希表。该内部哈希表的值将是具有该顶点的多边形的列表。

该结构可以在O(n) 的时间内构建，并将允许您在恒定的时间内找到匹配的顶点。

只有当找不到匹配时，才会进入下一个算法：

###查找边缘

在预处理步骤中（仅一次），为这些多边形创建一个segment tree，其中“segment”对应于特定多边形的最小/最大x坐标范围。

给定一个顶点，使用分段树查找正确x坐标范围内的多边形，即顶点的x坐标在多边形的x坐标的最小/最大范围内。

遍历这些多边形，并消除那些没有包含顶点y坐标范围的多边形。

如果没有多边形保留，则该顶点不参与任何其他多边形的边缘。

您无法在此处获得多个多边形，因为这意味着另一个多边形共享顶点，这是哈希基于算法处理的情况。

如果您只得到一个多边形，则继续通过遍历该多边形的边缘来查找匹配项（这就是您已经计划执行的线相交检查），但现在您只需要为一个多边形执行它。

您可以通过先将边缘过滤到具有正确x范围的边缘，来加快该行相交检查的速度。对于凸多边形，最多会得到两条边缘。这两条中最多只有一条具有正确的y范围。如果您得到这样的一条边，检查顶点是否确实在那条边上。

我解决了这个问题，并在这里发布答案，以防其他人也遇到了这个问题。

我的第一步是根据trincot的建议实现了一个预处理循环。

1.我计算了每个形状的最小和最大的x和y边界。 2.我使用这些值来确定所有重叠的形状，并存储一个简单的数组，我稍后可以用它来只查看可以重叠的形状。

然后，对于实际的确定最终多边形轮廓的循环：

1.我从第一个形状开始，只需将其顶点与附近形状的顶点进行比较。如果存在至少一个顶点与另一个顶点不共享，则它必须位于外边缘，循环从这里开始。如果只有重叠的顶点，则将第一个形状添加到已检查形状的表格中，并重复此过程，直到找到在外边缘上的顶点。 2.一旦找到起始顶点，主循环将逐个检查起始形状的顶点，并测量从给定顶点到每个相邻形状边缘的距离。如果距离为零，则该顶点可以是另一个形状的顶点重叠或该顶点位于另一个形状的侧面。 3.在找到上述类型的顶点时，我将上一个形状的编号添加到已检查形状的表格中，以便不再检查该形状。然后，我检查是否存在其他共享此特定顶点的形状。如果有，则确定最外层形状，并从那里继续，从第2步重新开始。 4.一旦检查完所有形状，我检查起始形状的所有非重叠顶点是否确实添加到了轮廓中。如果没有，则在最后添加它们。

可能有计算上更快的方法，但我发现这个方法简单易写，满足我所有要求，并且对我的需求来说足够快。