算法：从地图上的点创建线段

Question

我想知道现在有一个算法或一种方法来做到这一点： 我有许多代表道路位置的2D点（比方说x，y）。每条道路可以采取不同的方向和“分裂”。我只需要生成分段之前的段。与图片更好地解释：

这是我的观点

而这些都是3个区段产生

我想用样条插值但不会对工作这和Ant Colony在这里可能不会有多大帮助，因为他们可能会采取捷径。 有没有办法做到这一点，如果是的话，你会怎么做？

Answer 1

我可以想到两种方法来解决这个问题，包括一个一个寻找衣柜。

第一种方法将涉及沿任一轴对点列表进行排序，然后从第一个点开始，通过点向前搜索，测量之间的距离。以Pn为第n个点，我们可以说最接近P1的点最多是从P1到P2的距离。那么我们就可以在最远的地方搜索排序后的数组，如果我们遇到另一个更接近的点，比如说P4，我们会将搜索距离缩短得更远。一旦找到最近的点，在两者之间画一段，然后继续点P2。你可能会优化一些存储有关P1和P2的相对位置的信息，然后自动跳过你比较P1的一些元素，因为你已经知道它们不是P2的最佳解决方案。

我能想到的另一种方法是使用四叉树。将整个网格划分为4个正方形，如果这些正方形中的任何一个包含超过1个元素，则将它们也划分为4个正方形，然后重复，直到每个正方形包含0或1个元素。然后看看包含这些单个正方形（仅包含1个元素）的正方形，然后比较最近的邻居。现在，这意味着你将不得不手动检查与正在搜索的方块直接相邻的方块，因为它可能位于一个边界上（想象一个刚刚在网格上方的1/2上方，一个刚好在1/2以下），并且在“展开”回到最初的网格原始方块之前，您不会找到其他点。这个解决方案对我来说编程会有点困难，但在密集的地图中可以肯定会更快。