快速确定中心点和路径的方法

Random sample consensus algorithm . 我曾经用这个从点云重建三维实体。因为你的例子是二维的,它会重复地随机选取2个点,并检查有多少个点在可以从这2个点构造的直线的某个阈值内。该算法理想情况下会找到3条线,近似于你所说的“路径”。这些线的交点可以很好地指示您应该在哪里寻找中心点。

要获得这三条直线,可以从数据集中删除点。因此,首先它会找到最佳拟合,然后将拟合阈值内的点删除。在这之后,它会寻找下一个最佳匹配,以此类推。您可以使用while循环来实现这一点,条件是剩余的点数。为了让你的例子更清楚:

从第二条直线删除点,然后将最后一条直线拟合到左侧的点:

可以考虑将数据放在树结构中,例如 balltree 寻找这3个交叉点的共同最近邻居。

使用RANSAC,您可能会得到比您想要的更少或更多的线,或者这些线不合适。这完全取决于参数(您可以通过反复试验来优化这些参数)和数据。

注意:上面的例子只是我用matplotlib做的一个演示,我没有使用RANSAC算法,但结果会有点相同。