按到前一点的距离对点云坐标进行排序

Question

我有一个大约有 300 个点的绳状物体的点云。我想对该点云的 3D 坐标进行排序，以便绳子的一端具有索引 0，另一端具有索引 300，如图所示。该对象的其他点云可能是 U 形的，因此我无法按 X、Y 或 Z 坐标排序。因此，我也无法按到单个点的距离进行排序。

我已经通过sklearn或scipy查看了 KDTree来计算每个点的最近邻，但我不知道如何从那里开始对数组中的点进行排序而不需要重复输入。

有没有一种方法可以对数组中的这些坐标进行排序，以便从起点开始在数组中附加下一个最近点的坐标？

Answer 1

首先，显然这个问题没有严格的解决方案（甚至对于你想要得到什么也没有严格的定义）。因此，您可能编写的任何内容都将是某种启发式方法，在某些情况下会失败，特别是当您的点云获得某种不平凡的形式时（例如，您是否允许绳子中出现循环？）

也就是说，一种简单的方法可能是构建一个图，以点为顶点，每两个点通过一条边连接，边的权重等于这两点之间的直线距离。

然后构建该图的最小生成树。这将为您的点云提供一种骨架，您可以在此骨架上设计任何简单的算法。

例如，按照沿着这棵树测量的到绳子起点的距离对所有点进行排序。树的任意两个顶点之间只有一条路径，因此对于树的每个顶点，计算到绳索起点的单个路径的长度，并按该距离对所有顶点进行排序。