c++ - 如何从一组线段创建封闭区域(凸多边形)？

Question

下面的问题是二维的，所以建议答案时可以做一些简化。

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

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

我看了一些图表和最短路径理论，但我想不通。

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

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

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

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

在此处查看图片 -(需要 10 个声望才能将其发布到此处 :P)

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

感谢您的帮助!

Answer 1

根据您的说明:

也许你可以试试这个:

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

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

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

---

<罢工>抱歉，您的问题不是很清楚，但我想 Convex Hull会派上用场的。您可以在计算船体时使用线段的端点。

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