求点到复杂曲线的最小距离 [英] Find minimum distance from point to complicated curve

问题描述

我有一个复杂的曲线，定义为表格中的一组点(完整表格是 对它进行插值但它返回的拟合非常差:

# 根据 x 对数据进行排序.temp_data = zip(x_data, y_data)temp_data.sort()# 解包排序后的数据.x_sorted, y_sorted = zip(*temp_data)# 生成单变量样条.s = UnivariateSpline(x_sorted, y_sorted, k=5)xspl = np.linspace(0.8, 1.1, 100)yspl = s(xspl)# 阴谋.plt.scatter(xspl, yspl, 标记='o', color='r', s=10, lw=0.2)

我也尝试增加插值点的数量，但结果一团糟:

# 根据 x 对数据进行排序.temp_data = zip(x_data, y_data)temp_data.sort()# 解包排序后的数据.x_sorted, y_sorted = zip(*temp_data)t = np.linspace(0, 1, len(x_sorted))t2 = np.linspace(0, 1, 100)# 一维线性插值.x2 = np.interp(t2, t, x_sorted)y2 = np.interp(t2, t, y_sorted)plt.scatter(x2, y2, 标记='o', color='r', s=10, lw=0.2)

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

解决方案

如果您愿意为此使用库，请查看 shapely:https://github.com/Toblerity/Shapely

举个简单的例子(points.txt 包含您在问题中链接的数据):

import shapely.geometry as geom将 numpy 导入为 npcoords = np.loadtxt('points.txt')line = geom.LineString(coords)点 = geom.Point(0.8, 10.5)# 注意 "line.distance(point)" 是相同的打印点距离(线)

作为一个交互式示例(这也绘制了您想要的线段):

将 numpy 导入为 np导入 shapely.geometry 作为 geom导入 matplotlib.pyplot 作为 plt类最近点(对象):def __init__(self, line, ax):self.line = 线self.ax = axax.figure.canvas.mpl_connect('button_press_event', self)def __call__(self, event):x, y = event.xdata, event.ydata点 = geom.Point(x, y)距离 = self.line.distance(point)self.draw_segment(点)打印到线的距离:"，距离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()如果 __name__ == '__main__':coords = np.loadtxt('points.txt')line = geom.LineString(coords)图, ax = plt.subplots()ax.plot(*coords.T)ax.axis('相等')NearestPoint(line, ax)plt.show()

请注意，我添加了 ax.axis('equal').shapely 在数据所在的坐标系中操作，如果没有等轴图，视图会扭曲，而 shapely 仍然会找到最近的点，它赢了在显示中看起来不太正确:

I have a complicated curve defined as a set of points in a table like so (the full table is here):

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

If I plot this table with the commands:

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)

I get the following:

where I've added the red points and segments manually. What I need is a way to calculate those segments for each of those points, that is: a way to find the minimum distance from a given point in this 2D space to the interpolated curve.

I can't use the distance to the data points themselves (the black dots that generate the blue curve) since they are not located at equal intervals, sometimes they are close and sometimes they are far apart and this deeply affects my results further down the line.

Since this is not a well behaved curve I'm not really sure what I could do. I've tried interpolating it with a UnivariateSpline but it returns a very poor fit:

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

I also tried increasing the number of interpolating points but got a mess:

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

Any ideas/pointers will be greatly appreciated.

解决方案

If you're open to using a library for this, have a look at shapely: https://github.com/Toblerity/Shapely

As a quick example (points.txt contains the data you linked to in your question):

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)

As an interactive example (this also draws the line segments you wanted):

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

Note that I've added ax.axis('equal'). shapely operates in the coordinate system that the data is in. Without the equal axis plot, the view will be distorted, and while shapely will still find the nearest point, it won't look quite right in the display:

这篇关于求点到复杂曲线的最小距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！