Нахождение ближайших точек между двумя кубическими сплайнами с помощью Python и Numpy

Question

Я ищу способ проанализировать два кубических сплайна и найти точку, где они находятся ближе всего друг к другу. Я видел много решений и сообщений, но я не смог реализовать предложенные методы. Я знаю, что ближайшей точкой будет одна из конечных точек двух кривых или точка, где первая производная обеих кривых равна. Проверить конечные точки легко. Трудно найти точки, где совпадают первые производные. Дано:

Curve 0 is B(t)   (red)
Curve 1 is C(s)   (blue)

Кандидат на ближайшую точку находится где:

B'(t) = C'(s)

Первая производная каждой кривой принимает следующий вид:

Где коэффициенты a, b, c формируются из контрольных точек кривых:

a=P1-P0
b=P2-P1
c=P3-P2

Взяв 4 контрольных точки для каждого кубического сплайна, я могу получить параметрические сечения каждой кривой в матричной форме, которую можно выразить с помощью Numpy с помощью следующего кода Python:

def test_closest_points():
    # Control Points for the two qubic splines.
    spline_0 = [(1,28), (58,93), (113,95), (239,32)]
    spline_1 = [(58, 241), (26,76), (225,83), (211,205)]

    first_derivative_matrix = np.array([[3, -6, 3], [-6, 6, 0], [3, 0, 0]])

    spline_0_x_A = spline_0[1][0] - spline_0[0][0]
    spline_0_x_B = spline_0[2][0] - spline_0[1][0]
    spline_0_x_C = spline_0[3][0] - spline_0[2][0]

    spline_0_y_A = spline_0[1][1] - spline_0[0][1]
    spline_0_y_B = spline_0[2][1] - spline_0[1][1]
    spline_0_y_C = spline_0[3][1] - spline_0[2][1]

    spline_1_x_A = spline_1[1][0] - spline_1[0][0]
    spline_1_x_B = spline_1[2][0] - spline_1[1][0]
    spline_1_x_C = spline_1[3][0] - spline_1[2][0]

    spline_1_y_A = spline_1[1][1] - spline_1[0][1]
    spline_1_y_B = spline_1[2][1] - spline_1[1][1]
    spline_1_y_C = spline_1[3][1] - spline_1[2][1]

    spline_0_first_derivative_x_coefficients = np.array([[spline_0_x_A], [spline_0_x_B], [spline_0_x_C]])
    spline_0_first_derivative_y_coefficients = np.array([[spline_0_y_A], [spline_0_y_B], [spline_0_y_C]])

    spline_1_first_derivative_x_coefficients = np.array([[spline_1_x_A], [spline_1_x_B], [spline_1_x_C]])
    spline_1_first_derivative_y_coefficients = np.array([[spline_1_y_A], [spline_1_y_B], [spline_1_y_C]])

    # Show All te matrix values
    print 'first_derivative_matrix:'
    print first_derivative_matrix
    print
    print 'spline_0_first_derivative_x_coefficients:'
    print spline_0_first_derivative_x_coefficients
    print
    print 'spline_0_first_derivative_y_coefficients:'
    print spline_0_first_derivative_y_coefficients
    print
    print 'spline_1_first_derivative_x_coefficients:'
    print spline_1_first_derivative_x_coefficients
    print
    print 'spline_1_first_derivative_y_coefficients:'
    print spline_1_first_derivative_y_coefficients
    print

# Now taking B(t) as spline_0 and C(s) as spline_1, I need to find the values of t and s where B'(t) = C'(s)

В этом post есть несколько хороших советов высокого уровня, но я не уверен, как реализовать решение на python, которое может найти правильные значения для t и s, которые имеют соответствующие первые производные (наклоны). Проблема B '(t) - C' (s) = 0 кажется вопросом поиска корней. Любой совет о том, как сделать это с Python и Numpy, будет принята с благодарностью.

Answer 1

Использование Numpy предполагает, что проблема должна решаться численно.Без потери общности мы можем относиться к этим 0<s<=1 и 0<t<=1.Вы можете использовать пакет SciPy для численного решения проблемы, например,

from scipy.optimize import minimize
import numpy as np

def B(t):
    """Assumed for simplicity: 0 < t <= 1
    """
    return np.sin(6.28 * t), np.cos(6.28 * t)

def C(s):
    """0 < s <= 1
    """
    return 10 + np.sin(3.14 * s), 10 + np.cos(3.14 * s)



def Q(x):
    """Distance function to be minimized
    """
    b = B(x[0])
    c = C(x[1])
    return (b[0] - c[0]) ** 2 + (b[1] - c[1]) ** 2

res = minimize(Q, (0.5, 0.5))


print("B-Point: ", B(res.x[0]))
print("C-Point: ", C(res.x[1]))

B-точка: (0,7071067518175205, 0,7071068105555733)
C-точка: (9.292893243165555, 9,29289319446135)

Это пример для двух кругов (один круг и дуга).Это, вероятно, будет работать со сплайнами.

Answer 2

Ваше предположение о B'(t) = C'(s) слишком сильно.

Производные имеют направление и величину.Направления должны совпадать в точках-кандидатах, но величины могут отличаться.

Чтобы найти точки с одинаковыми производными наклонами и наименьшим расстоянием, вы можете решить систему уравнений (конечно, большая мощность :()

 yb'(t) * xc'(u) - yc'(t) * xb'(u) = 0  //vector product of (anti)collinear vectors is zero
 ((xb(t) - xc(u))^2 + (xb(t) - xc(u))^2)' = 0   //distance derivative

Answer 3

Вы также можете использовать функцию fmin:

import numpy as np
import matplotlib.pylab as plt
from scipy.optimize import fmin

def BCubic(t, P0, P1, P2, P3):

    a=P1-P0
    b=P2-P1
    c=P3-P2

    return a*3*(1-t)**2 + b*6*(1-t)*t + c*3*t**2

def B(t):
    return BCubic(t,4,2,3,1)

def C(t):
    return BCubic(t,1,4,3,4)

def f(t): 
    # L1 or manhattan distance
    return abs(B(t) - C(t))

init = 0 # 2
tmin = fmin(f,np.array([init]))
#Optimization terminated successfully.
#Current function value: 2.750000
#     Iterations: 23
#     Function evaluations: 46
print(tmin)
# [0.5833125]
tmin = tmin[0]

t = np.linspace(0, 2, 100)
plt.plot(t, B(t), label='B')
plt.plot(t, C(t), label='C')
plt.plot(t, abs(B(t)-C(t)), label='|B-C|')
plt.plot(tmin, B(tmin), 'r.', markersize=12, label='min')
plt.axvline(x=tmin, linestyle='--', color='k')
plt.legend()
plt.show()