算法：从地图上的点创建线段
Algorithms: create segments from points on a map
我想知道是否有现成的算法或方法可以做到这一点：
我在 2D 中有很多点（比如 x，y）代表道路位置。每条路可以走不同的方向 "split"。我只需要生成拆分之前的段。用图片更好地解释：
这些是我的观点
这些是生成的 3 个片段
我想使用插值样条，但这对这个不起作用，而且 Ant Colony 在这里可能不会有太大帮助，因为他们可能会走捷径。
有没有办法做到这一点，如果是的话，你会怎么做？
我可以想到两种方法来解决这个问题，都涉及一对一地找到壁橱。
第一种方法涉及沿任一轴对点列表进行排序，然后从第一个点开始，通过点向前搜索，测量点之间的距离。以Pn为第n个点，我们可以说离P1最近的点至多是P1到P2的距离。所以我们最多搜索排序数组那么远，如果我们遇到另一个更近的点，比如 P4，我们将搜索的距离缩短得更远。找到最近的点后，在两者之间画一条线段，然后移动到点 P2。您可能会对此进行优化，存储一些有关 P1 和 P2 的相对位置的信息，然后自动跳过您将 P1 与之进行比较的一些元素，因为您已经知道它们不是 P2 的最佳解决方案。
我能想到的另一种方法是使用四叉树。将整个网格分成 4 个方块，如果其中任何一个方块包含的元素多于 1，则将它们也分成 4 个方块，如此重复直到每个方块包含 0 或 1 个元素。然后查看包含这些单个方块（仅包含 1 个元素）的方块，并比较最近的邻居。现在，这确实意味着您将不得不手动检查与正在搜索的方块直接相邻的方块，因为它可能位于边界上（想想一个刚好在网格上方 1/2 上方的方块，以及一个刚好在 1/2 下方的方块) 并且在 'expand' 回到作为初始网格的原始正方形之前，您不会找到另一个点。我认为这个解决方案的编程会有点困难，但在密集地图中肯定会更快。
我想知道是否有现成的算法或方法可以做到这一点： 我在 2D 中有很多点（比如 x，y）代表道路位置。每条路可以走不同的方向 "split"。我只需要生成拆分之前的段。用图片更好地解释：
这些是我的观点
这些是生成的 3 个片段
我想使用插值样条，但这对这个不起作用，而且 Ant Colony 在这里可能不会有太大帮助，因为他们可能会走捷径。 有没有办法做到这一点，如果是的话，你会怎么做？
我可以想到两种方法来解决这个问题，都涉及一对一地找到壁橱。
第一种方法涉及沿任一轴对点列表进行排序，然后从第一个点开始，通过点向前搜索，测量点之间的距离。以Pn为第n个点，我们可以说离P1最近的点至多是P1到P2的距离。所以我们最多搜索排序数组那么远，如果我们遇到另一个更近的点，比如 P4，我们将搜索的距离缩短得更远。找到最近的点后，在两者之间画一条线段，然后移动到点 P2。您可能会对此进行优化，存储一些有关 P1 和 P2 的相对位置的信息，然后自动跳过您将 P1 与之进行比较的一些元素，因为您已经知道它们不是 P2 的最佳解决方案。
我能想到的另一种方法是使用四叉树。将整个网格分成 4 个方块，如果其中任何一个方块包含的元素多于 1，则将它们也分成 4 个方块，如此重复直到每个方块包含 0 或 1 个元素。然后查看包含这些单个方块（仅包含 1 个元素）的方块，并比较最近的邻居。现在，这确实意味着您将不得不手动检查与正在搜索的方块直接相邻的方块，因为它可能位于边界上（想想一个刚好在网格上方 1/2 上方的方块，以及一个刚好在 1/2 下方的方块) 并且在 'expand' 回到作为初始网格的原始正方形之前，您不会找到另一个点。我认为这个解决方案的编程会有点困难，但在密集地图中肯定会更快。