二维点云中最优连续拟合线算法求解及点序问题解决

之前想在二维点云里生成中位/最优连续曲线，就试了《Total least squares fitting of Bézier and B-spline curves to ordered data》里的算法，结果完全不对——居然把两条独立的轮廓给连起来了。当时还在找除了滤点之外的办法，后来才发现问题根源是输入点的排序。

我的测试用例里，两组点都是大圆圈经缩放因子r<1的膨胀变换（dilatation）加旋转变换生成的。把所有输入点按顺时针重新排序后，再跑那个算法，就得到了预期的拟合曲线。

小提醒 #

这类针对有序数据的曲线拟合算法（比如贝塞尔、B样条的总体最小二乘拟合）对输入点的顺序敏感度极高，点列乱序或者交叉的话，很容易出现拟合曲线错连、变形的情况，遇到这类问题优先检查点的排序准没错。

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