将重叠的凸多边形合并为单个凹多边形的最佳方法？
Best way to merge overlapping convex polygons into a single concave polygon?
我正在处理几个相互重叠的凸多边形，我需要将它们重新组合在一起以形成一个可能是凸面或凹面的多边形。
问题总是如下：
1) 我需要合并在一起的多边形总是凸的。
2) 每个多边形的顶点按顺时针顺序定义。
3) 多边形从不按任何特定顺序排列。
4) 最终的多边形只能是简单的凸多边形或凹多边形，即没有自交，没有重复的顶点或形状中的洞。
这是我正在使用的多边形类型的示例。
![重叠凸多边形]"image removed")
我目前的方法是从第一个多边形开始，逐个顶点循环遍历所有多边形的所有顶点以找到重叠部分。如果没有重叠，我存储最终轮廓的顶点并继续。
找到重叠顶点后，我通过测量可能路径的角度并选择通向形状外部的那个来确定要继续到哪个多边形。
这种方法一直有效，直到我遇到没有顶点相互重叠的多边形，而是一个多边形的顶点与另一个多边形的边重叠，就像图像中的矩形一样。
我目前正计划通过 运行 对我尚未处理的所有形状进行线相交检查来解决这些情况，但我相信就性能而言，这不是最简单或最好的方法.
有人知道我应该如何以更有效的方式解决这个问题 and/or 通用方式吗？
给定一个顶点，您可以按如下方式加快 "overlapping" 顶点或边的搜索速度：
寻找顶点
假设坐标是精确的，在某种意义上，如果两个顶点重叠，它们具有完全相同的x和y坐标，没有任何"error"的不精确，那么最好先通过 x 坐标创建一个散列，然后对于每个 x 条目，您将有一个 y 坐标的散列。该内部散列的值将是具有该顶点的多边形列表。
该结构可以在 O(n) 时间内构建，并且可以让您在常数时间内找到匹配的顶点。
只有在没有匹配的情况下，您才会转到下一个算法：
寻找优势
在预处理步骤中（仅一次），为这些多边形创建 segment tree，其中 "segment" 对应于特定多边形的 min/max x 坐标范围。
给定一个顶点，使用线段树找到在正确x坐标范围内的多边形，即顶点的x坐标在min/max的x坐标范围内多边形。
迭代这些多边形，并消除那些不具有顶点 y 坐标的 y 坐标范围的多边形。
如果没有多边形剩余，则该顶点不参与另一个多边形的任何边。
您不能在此处获得多个多边形，因为这意味着另一个多边形共享顶点，这是基于哈希的算法已经涵盖的情况。
如果您只得到一个多边形，则通过该多边形的边继续搜索以找到匹配项——这是您已经计划要做的（线相交检查），但现在您只需要为一个多边形做。
您可以先将边缘过滤为具有正确 x 范围的边缘，从而稍微加快该线相交检查的速度。对于凸多边形，您最多会得到两条边。至多这两个中的一个将具有正确的 y 范围。如果你得到这样一条边，检查顶点是否真的在那条边上。
我解决了这个问题并将答案发布在这里以防其他人也遇到这个问题。
我的第一步是根据 trincot 的建议实施预处理循环。
- 我计算了每个单独形状的最小和最大 x 和 y 边界。
- 我使用这些值来确定所有重叠的形状，并为每个形状存储了一个简单的数组，以后我可以用它来只查看可以相互重叠的形状。
然后，对于确定最终多边形轮廓的实际循环：
- 我从第一个形状开始，简单地将其顶点与附近形状的顶点进行比较。如果至少有一个顶点不与另一个顶点共享，则它必须位于外边缘并且循环从那里开始。如果只有重叠的顶点，那么我将第一个形状添加到所有选中形状的 table 中，然后用另一个形状重复此过程，直到找到位于外边缘的顶点。
- 一旦找到起始顶点，主循环将逐个检查起始形状的顶点，并测量给定顶点与附近每个形状的边的距离。如果距离为零，则顶点要么与另一个形状的顶点重叠，要么顶点位于另一个形状的一侧。
- 找到上述类型的顶点后，我将前一个形状的编号添加到已检查形状的 table 中，这样就不会再次检查它。然后，我检查是否有其他形状共享这个特定顶点。如果有，那么我确定最外面的形状并从那里继续，从第 2 步开始。
- 检查完所有形状后，我会检查起始形状中的所有非重叠顶点是否确实已添加到轮廓中。如果不是，我会在最后添加它们。
可能有计算速度更快的方法，但我发现这个方法编写起来很简单，它满足我的所有要求，而且速度足够快，足以满足我的需要。
我正在处理几个相互重叠的凸多边形，我需要将它们重新组合在一起以形成一个可能是凸面或凹面的多边形。
问题总是如下：
1) 我需要合并在一起的多边形总是凸的。
2) 每个多边形的顶点按顺时针顺序定义。
3) 多边形从不按任何特定顺序排列。
4) 最终的多边形只能是简单的凸多边形或凹多边形，即没有自交，没有重复的顶点或形状中的洞。
这是我正在使用的多边形类型的示例。
![重叠凸多边形]"image removed")
我目前的方法是从第一个多边形开始，逐个顶点循环遍历所有多边形的所有顶点以找到重叠部分。如果没有重叠，我存储最终轮廓的顶点并继续。
找到重叠顶点后，我通过测量可能路径的角度并选择通向形状外部的那个来确定要继续到哪个多边形。
这种方法一直有效，直到我遇到没有顶点相互重叠的多边形，而是一个多边形的顶点与另一个多边形的边重叠，就像图像中的矩形一样。
我目前正计划通过 运行 对我尚未处理的所有形状进行线相交检查来解决这些情况，但我相信就性能而言，这不是最简单或最好的方法.
有人知道我应该如何以更有效的方式解决这个问题 and/or 通用方式吗？
给定一个顶点，您可以按如下方式加快 "overlapping" 顶点或边的搜索速度：
寻找顶点
假设坐标是精确的，在某种意义上，如果两个顶点重叠，它们具有完全相同的x和y坐标，没有任何"error"的不精确，那么最好先通过 x 坐标创建一个散列，然后对于每个 x 条目，您将有一个 y 坐标的散列。该内部散列的值将是具有该顶点的多边形列表。
该结构可以在 O(n) 时间内构建，并且可以让您在常数时间内找到匹配的顶点。
只有在没有匹配的情况下，您才会转到下一个算法：
寻找优势
在预处理步骤中（仅一次），为这些多边形创建 segment tree，其中 "segment" 对应于特定多边形的 min/max x 坐标范围。
给定一个顶点，使用线段树找到在正确x坐标范围内的多边形，即顶点的x坐标在min/max的x坐标范围内多边形。
迭代这些多边形，并消除那些不具有顶点 y 坐标的 y 坐标范围的多边形。
如果没有多边形剩余，则该顶点不参与另一个多边形的任何边。
您不能在此处获得多个多边形，因为这意味着另一个多边形共享顶点，这是基于哈希的算法已经涵盖的情况。
如果您只得到一个多边形，则通过该多边形的边继续搜索以找到匹配项——这是您已经计划要做的（线相交检查），但现在您只需要为一个多边形做。
您可以先将边缘过滤为具有正确 x 范围的边缘，从而稍微加快该线相交检查的速度。对于凸多边形，您最多会得到两条边。至多这两个中的一个将具有正确的 y 范围。如果你得到这样一条边，检查顶点是否真的在那条边上。
我解决了这个问题并将答案发布在这里以防其他人也遇到这个问题。
我的第一步是根据 trincot 的建议实施预处理循环。
- 我计算了每个单独形状的最小和最大 x 和 y 边界。
- 我使用这些值来确定所有重叠的形状，并为每个形状存储了一个简单的数组，以后我可以用它来只查看可以相互重叠的形状。
然后，对于确定最终多边形轮廓的实际循环：
- 我从第一个形状开始，简单地将其顶点与附近形状的顶点进行比较。如果至少有一个顶点不与另一个顶点共享，则它必须位于外边缘并且循环从那里开始。如果只有重叠的顶点，那么我将第一个形状添加到所有选中形状的 table 中，然后用另一个形状重复此过程，直到找到位于外边缘的顶点。
- 一旦找到起始顶点，主循环将逐个检查起始形状的顶点，并测量给定顶点与附近每个形状的边的距离。如果距离为零，则顶点要么与另一个形状的顶点重叠，要么顶点位于另一个形状的一侧。
- 找到上述类型的顶点后，我将前一个形状的编号添加到已检查形状的 table 中，这样就不会再次检查它。然后，我检查是否有其他形状共享这个特定顶点。如果有，那么我确定最外面的形状并从那里继续，从第 2 步开始。
- 检查完所有形状后，我会检查起始形状中的所有非重叠顶点是否确实已添加到轮廓中。如果不是，我会在最后添加它们。
可能有计算速度更快的方法，但我发现这个方法编写起来很简单，它满足我的所有要求，而且速度足够快，足以满足我的需要。