从无序2D测量点集构建路径折线：求已知算法及相似问题方案

• 基于图的路径构建：把每个测量点当成图里的节点，只要两个点间距在你设定的“足够近”阈值内，且连线的方位角和当前路径段的角度变化符合“无快速变向”要求，就给这两个点连一条边。之后先找出图里的所有连通分量（每个分量就是一个路径聚类），再在每个分量里用贪婪遍历或者欧拉路径的思路，把点排成连续的路径。这种方法是把你自己的启发式思路系统化，还能处理简单的分支场景。
• 聚类+排序两步走：
  • 聚类阶段：用DBSCAN聚类算法最合适。它是按密度来分组的，正好匹配你“同路径点间距不大”的假设——把邻域半径设为你的“足够近”阈值，最小样本数设为2（毕竟一条路径至少得有两个点），这样自动就能把同一路径的点聚成一类，像90度转弯的两段路，因为点的密度断开，会被分成两个簇，完全符合你的预期。
  • 排序阶段：对每个簇里的点，有几种思路：一是用带方向约束的贪心TSP算法，每次选下一个点时，优先挑距离近且方位角变化小的；二是用链状排序法，先找到路径的两个端点（比如簇里距离最远的两个点，或者度数为1的图节点），然后从端点开始，一步步找最符合距离和方向要求的下一个点，和你自己的方法类似，但逻辑更严谨。
• 轨迹重建类算法：不少针对零散轨迹点的重建算法也适用，比如连续点匹配算法，它假设每个点只和前后两个点相连，通过计算点之间的邻接概率（结合距离和方向一致性），来生成最贴合真实路径的有序序列。

• 这个问题本质是无标签轨迹点的聚类与排序，在GIS领域特别常见，比如处理车载GPS采集的零散轨迹、步行导航的路径重建，很多GIS工具里都有现成的实现逻辑。
• 另外计算机视觉里的边缘点排序成线条问题也和这个类似，核心都是靠距离和方向的一致性来聚类并生成连续序列。

内容的提问来源于stack exchange，提问作者Guy Yafe