找到从点到复杂曲线的最小距离

Question

我有一个复杂的曲线定义为表中的一组点,如此(完整的表在这里):

#  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)

我也试过增加插值点的数量但是弄得一团糟:

# 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)

任何想法/指针将不胜感激.

Answer 1

如果您愿意使用库,请查看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仍会找到最近的点,但在显示中看起来不太正确:

Answer 2

该曲线本质上是参数化的,即对于每个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)