python - 将线段拟合到一组点

Question

我试图将一条线段与一组点相匹配，但我找不到适合它的算法。我有一个二维线段 L 和一组二维点 C。 L 可以用任何合适的方式表示(我不在乎)，比如支持向量和定义向量、两点、具有左右边界的线性方程……唯一重要的是这条线有起点和终点，所以它不是是无限的。

我想将 L 放入 C 中，以便 c 到 L 的所有距离之和(其中 c 是 C 中的一个点)被最小化。这是一个最小二乘问题，但我(认为)不能使用多项式拟合，因为 L 只是一个片段。我在该领域的数学知识有点缺乏，所以任何关于进一步阅读的提示也将不胜感激。

这是我的问题的一个例子:

橙色线应与蓝色点相匹配，以使每个点到线的距离的平方和最小。我不介意解决方案是用不同的语言还是根本不是代码，只要我能从中提取算法。

因为这更像是一个数学问题，所以我不确定它是否适合 SO 还是应该转移到交叉验证或数学交换。

Answer 1

此解决方案与此处已发布的解决方案比较相似，但我认为效率更高、更优雅且更易于理解，这就是为什么尽管有相似之处我还是将其发布。

正如已经写过的那样，min(max(...)) 公式很难通过分析来解决这个问题，这就是为什么 scipy.optimize 很适合。

解决方案基于点与有限线段之间距离的数学公式，详见 https://math.stackexchange.com/questions/330269/the-distance-from-a-point-to-a-line-segment

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize, NonlinearConstraint


def calc_distance_from_point_set(v_):
    #v_ is accepted as 1d array to make easier with scipy.optimize
    #Reshape into two points
    v = (v_[:2].reshape(2, 1), v_[2:].reshape(2, 1))

    #Calculate t* for s(t*) = v_0 + t*(v_1-v_0), for the line segment w.r.t each point
    t_star_matrix = np.minimum(np.maximum(np.matmul(P-v[0].T, v[1]-v[0]) / np.linalg.norm(v[1]-v[0])**2, 0), 1)
    #Calculate s(t*)
    s_t_star_matrix = v[0]+((t_star_matrix.ravel())*(v[1]-v[0]))

    #Take distance between all points and respective point on segment
    distance_from_every_point = np.linalg.norm(P.T -s_t_star_matrix, axis=0)
    return np.sum(distance_from_every_point)

if __name__ == '__main__':

    #Random points from bounding box

    box_1 = np.random.uniform(-5, 5, 20)
    box_2 = np.random.uniform(-5, 5, 20)
    P = np.stack([box_1, box_2], axis=1)
    segment_length = 3
    segment_length_constraint = NonlinearConstraint(fun=lambda x: np.linalg.norm(np.array([x[0], x[1]]) - np.array([x[2] ,x[3]])), lb=[segment_length], ub=[segment_length])
    point = minimize(calc_distance_from_point_set, (0.0,-.0,1.0,1.0), options={'maxiter': 100, 'disp': True},constraints=segment_length_constraint).x
    plt.scatter(box_1, box_2)
    plt.plot([point[0], point[2]], [point[1], point[3]])

示例结果: