从点到复杂曲线的最小距离是多少？

Question

从点到复杂曲线的最小距离是多少？

19

我有一个由一组点在表格中定义的复杂曲线，如下所示（完整的表格在这里）：

#  x   y
1.0577  12.0914
1.0501  11.9946
1.0465  11.9338
...

如果我使用以下命令绘制此表格：

plt.plot(x_data, y_data, c='b',lw=1.)
plt.scatter(x_data, y_data, marker='o', color='k', s=10, lw=0.2)

我获得了以下内容：

其中，我手动添加了红点和线段。我需要的是一种计算每个点这些线段的方法，即：找到在此2D空间中给定点到插值曲线的最小距离的方法。

我不能使用数据点本身的距离（生成蓝色曲线的黑色点），因为它们不位于等间隔位置，有时它们接近，有时它们相距很远，这会深刻影响我的后续结果。

由于这不是一条行为良好的曲线，我真的不知道该怎么做。我尝试用 UnivariateSpline 进行插值，但返回很差的拟合结果：

# Sort data according to x.
temp_data = zip(x_data, y_data)
temp_data.sort()
# Unpack sorted data.
x_sorted, y_sorted = zip(*temp_data)

# Generate univariate spline.
s = UnivariateSpline(x_sorted, y_sorted, k=5)
xspl = np.linspace(0.8, 1.1, 100)
yspl = s(xspl)

# Plot.
plt.scatter(xspl, yspl, marker='o', color='r', s=10, lw=0.2)

enter image description here

我也尝试了增加插值点的数量，但结果混乱不堪：

# Sort data according to x.
temp_data = zip(x_data, y_data)
temp_data.sort()
# Unpack sorted data.
x_sorted, y_sorted = zip(*temp_data)

t = np.linspace(0, 1, len(x_sorted))
t2 = np.linspace(0, 1, 100)    
# One-dimensional linear interpolation.
x2 = np.interp(t2, t, x_sorted)
y2 = np.interp(t2, t, y_sorted)
plt.scatter(x2, y2, marker='o', color='r', s=10, lw=0.2)

在此输入图片描述

如果您有任何想法/指针，将不胜感激。

- Gabriel

这个问题不是凸优化问题（https://en.wikipedia.org/wiki/Convex_optimization）... 这意味着优化技术通常不能保证给出全局最小值。话虽如此，模拟退火是在一个不完美的世界中尝试寻找全局最优解的一种选择。 - Him

4个回答

7

曲线本质上是参数化的，即对于每个x并不一定有一个唯一的y，反之亦然。因此，你不应该插值形式为y(x)或x(y)的函数。相反，你应该进行两次插值，x(t)和y(t)，其中t是相应点的索引，例如第一个图中的红点。然后，使用scipy.optimize.fminbound来查找最佳的t，使得(x(t) - x0)^2 + (y(t) - y0)^2最小化，其中(x0, y0)是第一个图中的红点。对于fminsearch，你可以指定t的最小/最大边界为1和len(x_data)。

- prgao

您介意澄清一下 fminsearch 是什么吗？另外，您提到的对 x 和 y 分别进行两次插值，不是我在问题中尝试过的最后一种方法吗？结果却很混乱。 - Gabriel

2

不要排序，x和y的初始顺序已经正确。 - prgao

还有一个函数名为'fminbound'，'fminsearch'是Matlab的等价函数。它可以在两个指定的边界之间找到标量函数的最小值。请参阅http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fminbound.html。 - prgao

这条曲线明显存在不连续性，我不会进行插值，除非你只在非不连续部分内进行插值，而这是很难自动化的。 - gg349

2

您可以尝试在曲线的增量点对上实现从点到线的距离计算，并找到最小值。这将从绘制的曲线引入一小部分误差，但应该非常小，因为这些点相对较接近。

http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

- Chris Bonnell

2

此外，曲线仅由点定义，而不是由特定的点插值函数定义。因此，除非我们假设一个特定的插值函数是正确的，否则我们甚至无法讨论所造成的误差。 - gg349

哦，好发现！是的，这个方法没有特定的错误。 - Chris Bonnell

我有同样的想法，但实际上它行不通：你必须检查你的点的投影是否属于该直线。但在某些情况下可能不会发生这种情况。例如：你的点刚好在一个倾斜的“帽子”曲线上方。那么最小距离将在你的点和帽子上部的点之间，但你无法通过垂直距离到一条直线来找到它。 - user1220978

如果线上的点比两个问题中的任何一个点更接近，则应拒绝该距离。 - Chris Bonnell

0

您可以轻松地在PyPI中使用trjtrypy包：https://pypi.org/project/trjtrypy/

所有所需的计算和可视化都包含在此软件包中。您只需一行代码即可获得答案，例如：

要获取最小距离，请使用：trjtrypy.basedists.distance(points, curve)

要可视化曲线和点，请使用：trjtrypy.visualizations.draw_landmarks_trajectory(points, curve)

- John

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joe Kington · Accepted Answer

如果你愿意使用一个库来完成这个任务，可以看一下 shapely: https://github.com/Toblerity/Shapely

这里有一个快速的例子（points.txt 包含了你在问题中提到的数据）：

import shapely.geometry as geom
import numpy as np

coords = np.loadtxt('points.txt')

line = geom.LineString(coords)
point = geom.Point(0.8, 10.5)

# Note that "line.distance(point)" would be identical
print(point.distance(line))

作为一个交互式的示例（这也绘制了你想要的线段）：

import numpy as np
import shapely.geometry as geom
import matplotlib.pyplot as plt

class NearestPoint(object):
    def __init__(self, line, ax):
        self.line = line
        self.ax = ax
        ax.figure.canvas.mpl_connect('button_press_event', self)

    def __call__(self, event):
        x, y = event.xdata, event.ydata
        point = geom.Point(x, y)
        distance = self.line.distance(point)
        self.draw_segment(point)
        print 'Distance to line:', distance

    def draw_segment(self, point):
        point_on_line = line.interpolate(line.project(point))
        self.ax.plot([point.x, point_on_line.x], [point.y, point_on_line.y], 
                     color='red', marker='o', scalex=False, scaley=False)
        fig.canvas.draw()

if __name__ == '__main__':
    coords = np.loadtxt('points.txt')

    line = geom.LineString(coords)

    fig, ax = plt.subplots()
    ax.plot(*coords.T)
    ax.axis('equal')
    NearestPoint(line, ax)
    plt.show()

在此输入图片描述

请注意，我已添加ax.axis('equal')。 shapely在数据所在的坐标系中运作。没有等轴线绘图，视图将会被扭曲，虽然shapely仍将找到最近的点，但在显示上看起来不太正确：

在此输入图片描述