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

Question

以下问题涉及到2D，因此在提供答案时可以进行一些简化。

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

基本上，我使用Voronoi生成“道路”。然后我更改了一些数据。现在我需要一种方法循环遍历该数据（仍为线段，但不再符合Voronoi），并生成被“道路”包围的“邻域”。

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

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

我试图实现它，但我无法想出一种编写C ++代码的方法，可以执行此操作。问题在于从特定点的可用线路中选择最逆时针线路的问题。我所做的所有基于角度的数学都给出了错误的答案，因为c ++中实现sin / cos的方式不同。

因此，总结一下-如果您可以帮助我解决问题的全新方法，那就好；如果不能，您能帮我找到一种编写代码的方法来使用线段集合作为路径返回到起始点的最短顺时针路径吗？

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

请在此处查看图像-（需要10个声望才能在此处发布它：P）

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

感谢您的帮助！

- Marten

---

可以贴一张图片吗？有时候，这比一堵文字墙更好，并且大多数情况下能够引起读者的兴趣去阅读那堵文字墙 :) - Jacob

@Jacob - 已经完成了，现在你可以看到我想做的事情的图片 :) - Marten

你找到答案了吗？能否再次添加您图片的链接？ - cosmarc

Answer 1

根据您的澄清：

也许您可以尝试这个方法：

由于 Voronoi，您可能已经有了任何给定紫色蓝色点的“相邻”点列表。现在，给定一个紫色点 P 和一个相邻点 Q，您可以考虑与线段 PQ 相交的道路。所有这样的道路（即将 Q 变为 P 的相邻点）很可能形成 P 周围的封闭区域。

即使您没有“相邻”信息，您也可以尝试所有可能的紫色蓝色点对，并查看哪些线段被恰好一条道路所穿过。对于给定的点，这样的道路集将形成其周围的封闭区域。

这可能不是最优解，但可能有效，尽管我还没有尝试证明它。

---

对不起，你的问题不是很清楚，但我猜 凸包算法 可以派上用场。计算凸包时，你可以使用线段的端点。

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

- Aryabhatta

---

这并没有太大帮助，因为我面临的问题是选择哪些点（或线）组成了一个“区域”。我需要收集定义城市道路地图中一个“区域”的点的集合。之后，我可以重复这个过程，对每个区域都这样做，这样我就会得到一系列点（线）集合，定义了每个城市单元格以填充建筑物。希望这讲得通，因为很难解释 ;) - Marten

是的，那似乎更合理 ;) 但问题在于我使用了 Voronoi 线，并将其分段成较小的部分以使道路不那么笔直，这意味着我可以找到其中一些类似的部分，但并非全部。 - Marten

那么我最终会遇到一个问题，如何绘制更改后的大型道路上更小的道路。想法是创建一个边界区域，可以用来绘制较小的道路。是的，如果需要，我认为我有大部分的 Voronoi 数据可用。 - Marten

@Marten：不理解问题所在。您有一组道路形成 Voronoi 后的区域。现在您将每条道路分成弯曲的线段。您有了一个新的道路集，形成了您想要的区域，是吗？我们所做的只是交换了区域创建和数据修改步骤。也许您应该明确说明在 Voronoi 步骤之后进行了哪些更改... - Aryabhatta

在 Voronoi 之后，我将道路分成了几个段，并允许在从起点到终点移动时有一定的变化度，因此最终得到了弯曲的道路。问题是，这条道路沿着 Voronoi 的总体方向走，但并不完全相同（有时距离 Voronoi 点更近/更远）。这意味着，如果我在弯曲的道路之前进行区域步骤，那么道路将切入或远离该区域，如果我使用该区域来限制我的较小道路，则会出现重叠或空白区域。我的问题是，尽管似乎我有区域，但我不知道区域的点集。 - Marten

Answer 2

你的想法是沿着最短路径跟随线段（例如，如果有多个选择，则按照最顺时针的一个来进行）是不错的。

而且你可以不用调用任何sin/cos函数就能找到这条线。

这个想法是这样的：

假设你有两条线供选择。将这两条线相交的点称为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.
  }

注意：我还没有绑定代码，符号的决定可能完全相反。这是数学中我永远无法理解的细节。我总是必须用已知数据尝试它。

- Nils Pipenbrinck

---

我会在第一时间尝试您的解决方案，并告诉您它的表现如何。谢谢！ - Marten

叉积可以告诉你是左转还是右转，但不能直接告诉你“更急的左转”或“更浅的右转”。您需要对输入向量进行归一化，然后计算点积，如 straightness = (u.x * v.x) + (u.y * v.y);，因为叉积将为45度弯曲和135度弯曲返回相同的值（它围绕垂直线反射，而点积则围绕平行线反射）。因此，使用叉积来确定“左或右”，使用点积来确定转弯角度。 - dash-tom-bang

Answer 3

听起来你想把某个区域分割成不重叠的凸多边形。如果我理解正确，你不能在用线段构成多边形后就丢弃它们，因为每个内部线段都会与两个多边形相邻。

相反，你应该为每个线段设置两个标志，表示是否已经构建了线段“左侧”和“右侧”的多边形。如果你有一个有边界的区域，边界线段需要先设置其“外侧”标志，因为你不想在多边形中使用该侧。然后找到任何一个标志未设置的线段，并使用Nils的答案来绕过多边形。一些线段将被“翻转”；如果你按顺时针方向前进，你要在“正向”线段上设置“左侧”标志，在“反向”线段上设置“右侧”标志，反之亦然。（你可以按任意顺序构建所有多边形，这并不重要。）注意，第一个线段可以根据需要设置其标志而被解释为任何一个方向。当所有线段都以两个方向标记时，你就完成了。

如果你正在分割平面而不是有界区域，则某些线段将是射线；你还需要一些特殊代码来将按斜率排序的相邻射线连接成虚假的“多边形”。 有界情况的伪代码：

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)
}

- Walter Mundt

---

据我所知，我想使用有界区域来实现这个目标。但是如果我不知道边界的位置，如何设置边界标志呢？我只有一组点和信息，说明哪些点连接起来形成了一条线。 - Marten

你的区域是凸多边形吗？如果是，您可以从最小X值的任意点开始，沿着“最顺时针”的边缘绕着区域标记外侧边缘。这就像标记一个内部多边形一样，但接触相反的旗帜。 - Walter Mundt

抱歉有点儿笨，不确定它是否是凸的。我想在x/y值为最小/最大值的地方添加线段，将所有边缘线连接成封闭区域（我只是不画它们，而是用来计算面积）。 - Marten

抱歉耽搁了，我没有看到您的评论通知。在这种情况下，您可以对点运行凸包，并根据需要添加虚假的“道路”。运行上述算法，然后丢弃任何边界内含有任何虚假道路的区域。 - Walter Mundt