如何从一组线段创建封闭区域（凸多边形）？

Question

以下问题是二维的，因此在建议答案时可以进行一些简化。

我需要从一组点/线段创建封闭区域（由线段或仅由一组点定义 - 凸多边形）。

基本上我使用 Voronoi 来生成“道路”。然后我改变了一些数据。现在我需要一种方法来循环该数据（仍然是线段，但不再符合 Voronoi）并生成与“道路”接壤的“社区”。

我查看了一些图表和最短路径理论，但我无法弄清楚。

从逻辑上讲，可以通过从一个点的左边缘开始，使用可用线路的最短路径（仅使用顺时针方向）找到返回该点的路来完成。然后标记这条线并从数据中删除。然后你可以重复相同的过程并获得类似的所有区域。

我试图实现它，但它并没有让我有任何进展，因为我无法找到一种方法来编写可以做到这一点的 C++ 代码。问题是从特定点的可用线路中选择最逆时针的线路。我所做的所有基于角度的数学都给出了错误的答案，因为 sin/cos 在 C++ 中实现的方式。

总结一下 - 如果你能帮助我用一种全新的方法来解决这个问题，那就太好了，如果不能，你能帮我找到一种方法来编写代码部分，使用该行找到回到起点的最短顺时针路径段设置为返回路径。

编辑：添加了一张图片来说明我想要做什么。

检查此处的图像 - （需要 10 个信誉才能将其发布到此处：P）

我有一组点（紫色小点）。另一个数组定义哪些点组成一条线（道路）。我想要一种方法来定义被道路包围的区域，这样我就可以将建筑物或较小的道路放入其中，并针对边缘进行测试，以便将每个区域分开。希望这能为您提供有关如何解决此问题的更多信息。

感谢您的帮助！

Answer 1

根据您的澄清：

也许您可以尝试以下操作：

由于 Voronoi，您可能已经拥有任何给定 purple 蓝点的“邻近”点列表。现在给定一个紫色点 P，有一个邻居 Q，您可以考虑与线段 PQ 相交的道路。所有这些道路（即 P 的邻居之间的 Q 不同）可能会形成 P 周围的封闭区域。

即使您没有“邻居”信息，您也可以尝试所有可能的紫色 蓝色点并查看哪些线段恰好与一条道路相交。对于给定点，一组此类道路将在其周围形成一个封闭区域。

这可能不是最佳的，但可能有效，尽管我还没有尝试证明这一点。

---

<罢工>
抱歉，您的问题不太清楚，但我认为 凸包 会派上用场。您可以在计算外壳时使用线段的端点。

如果您想要多个不相交的“区域”，您可以尝试找到一条分隔线并分别运行凸包。

Answer 2

您沿着最短路径跟踪线段的想法（例如，如果您有多个选择，则沿着最顺时针的路径）是好的。

您可以在没有任何 sin/cos 调用的情况下找到这条线。

这个想法是这样的：

假设你有两条线可供选择。将线与 A 相交的点称为 A（例如您当前的位置）。两条线的端点称为 B 和 C。

这三个点构成一个三角形。现在看看这三个点是如何定位的。如果沿着从 A 到 B 到 C 的点，方向将是顺时针或逆时针。显然，如果顺序是顺时针，则从 A 到 C 的线将是最顺时针的线。否则就是从 A 到 B 的线。

如果您有两条以上的线可供选择，只需选择前两条，丢弃方向错误的线并进行相同的测试，直到最终得到一条线。这是最顺时针的。

现在关于数学：如何在不调用 sin/cos 甚至更糟的情况下找出三个点的缠绕顺序： atan：

您可以使用叉积来做到这一点。首先构建两个向量，分别给出从 A 到 B 和从 A 到 C 的方向：

   u.x = B.x - A.x
   u.y = B.y - A.y

   v.x = C.x - A.x
   v.y = C.y - A.y

现在我们可以计算这两个向量生成的平行四边形的带符号面积：

   signed_area = (u.x * v.y) - (u.y * v.x);

绕线是面积的符号。例如

  if (signed_area > 0)
  { 
     // order is clockwise. Pick Line B
  }
  else if (signed_area < 0)
  { 
     // order is counter-clockwise. Pick Line A
  }
  else 
  {
    // the lines are colinear.
  }

注意：我没有绑定代码，并且对标志的决定可能完全相反。这是我永远不会想到的数学细节。我总是必须用已知的数据进行尝试。

Answer 3

听起来您想将某个区域划分为不重叠的凸多边形。如果我理解正确的话，你不能在使用线段形成多边形后就扔掉它们，因为每个内部线段将与两个多边形接壤。

相反，每个线段应该有两个标志，用于确定是否已为线段的“左”和“右”构建了多边形。如果您有边界区域，则边界段需要将其“外部”边标志设置为开始，因为您不想在多边形中使用该边。然后找到未设置任一标志的线段，并使用尼尔斯的答案来围绕多边形工作。有些片段会被“反转”；如果您要顺时针方向行驶，则需要在“向前”段上设置“左”标志，在“向后”段上设置“右”标志，反之亦然。 （您可以按一个顺序构建所有多边形，选择哪一个并不重要。）请注意，第一段可以解释为其中之一，具体取决于您需要设置哪个标志。当所有段在两个方向上都被标记时，您就完成了。

如果您要划分平面而不是有界区域，则某些线段将是射线；您还需要一些特殊的代码来连接按斜率排序时相邻的光线到假“多边形”中。

有界情况的伪代码：

foreach seg in boundary segments {
    if left of seg is outside region {
         seg.leftDone = true
    } else {
         seg.rightDone = true
    }
}
while any seg.leftDone or seg.rightDone is false {
    seg = pick a segment with either flag unset
    start = seg
    polygon = new Polygon()
    reversed = not start.rightDone
    do {
        if reversed {
            seg.rightDone = true
            endpoint = seg.start
            polygon.addSegment(seg.reverse())
        } else {
            seg.leftDone = true
            endpoint = seg.end
            polygon.addSegment(seg)
        }

        next = findNextClockwiseSeg(seg, endpoint); // Nils's answer works

        seg = next
        reversed = (seg.end == endpoint)
    } while start != seg;
    result.addPolygon(polygon)
}