以下问题涉及到2D,因此在提供答案时可以进行一些简化。
我需要从一组点/线段中创建封闭区域(由线段或仅由点集 - 凸多边形定义)。
基本上,我使用Voronoi生成“道路”。然后我更改了一些数据。现在我需要一种方法循环遍历该数据(仍为线段,但不再符合Voronoi),并生成被“道路”包围的“邻域”。
我查看了一些图形图表和最短路径理论,但是我无法弄清楚它。
从逻辑上讲,可以通过从一个点的左侧边缘开始,使用可用线段的最短路径找回该点的方式来完成。 (仅使用顺时针方向)。然后标记这条线路并从数据中删除。然后,您可以重复相同的过程并以相同的方式获取所有区域。
我试图实现它,但我无法想出一种编写C ++代码的方法,可以执行此操作。问题在于从特定点的可用线路中选择最逆时针线路的问题。我所做的所有基于角度的数学都给出了错误的答案,因为c ++中实现sin / cos的方式不同。
因此,总结一下-如果您可以帮助我解决问题的全新方法,那就好;如果不能,您能帮我找到一种编写代码的方法来使用线段集合作为路径返回到起始点的最短顺时针路径吗?
编辑:添加了一个图片来说明我想要做什么。
请在此处查看图像-(需要10个声望才能在此处发布它:P)
我有一组点(紫色小点)。另一个数组定义了哪些点构成一条线(道路)。我想要一种方法来定义被道路包围的区域,以便我可以在其中放置建筑物或较小的道路,并针对边缘进行测试,以使每个区域都分开。希望这给您提供了如何解决此问题的更多信息。
感谢您的帮助!
我需要从一组点/线段中创建封闭区域(由线段或仅由点集 - 凸多边形定义)。
基本上,我使用Voronoi生成“道路”。然后我更改了一些数据。现在我需要一种方法循环遍历该数据(仍为线段,但不再符合Voronoi),并生成被“道路”包围的“邻域”。
我查看了一些图形图表和最短路径理论,但是我无法弄清楚它。
从逻辑上讲,可以通过从一个点的左侧边缘开始,使用可用线段的最短路径找回该点的方式来完成。 (仅使用顺时针方向)。然后标记这条线路并从数据中删除。然后,您可以重复相同的过程并以相同的方式获取所有区域。
我试图实现它,但我无法想出一种编写C ++代码的方法,可以执行此操作。问题在于从特定点的可用线路中选择最逆时针线路的问题。我所做的所有基于角度的数学都给出了错误的答案,因为c ++中实现sin / cos的方式不同。
因此,总结一下-如果您可以帮助我解决问题的全新方法,那就好;如果不能,您能帮我找到一种编写代码的方法来使用线段集合作为路径返回到起始点的最短顺时针路径吗?
编辑:添加了一个图片来说明我想要做什么。
请在此处查看图像-(需要10个声望才能在此处发布它:P)
我有一组点(紫色小点)。另一个数组定义了哪些点构成一条线(道路)。我想要一种方法来定义被道路包围的区域,以便我可以在其中放置建筑物或较小的道路,并针对边缘进行测试,以使每个区域都分开。希望这给您提供了如何解决此问题的更多信息。
感谢您的帮助!