Je cherche un moyen d'analyser deux splines cubiques et de trouver le point où elles se rapprochent le plus. J'ai vu beaucoup de solutions et d'articles, mais je n'ai pas pu mettre en œuvre les méthodes suggérées. Je sais que le point le plus proche sera l'un des points d'extrémité des deux courbes ou un point où la première dérivée des deux courbes est égale. La vérification des points finaux est facile. Trouver les points où les premiers dérivés correspondent est difficile. Données:
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)
Un candidat pour le point le plus proche est où:
a=P1-P0 b=P2-P1 c=P3-P2
3 Réponses :
L'utilisation de Numpy suppose que le problème doit être résolu numériquement. Sans perte de généralité, nous pouvons traiter que Point B: (0.7071067518175205, 0.7071068105555733) Voici un exemple pour deux cercles (un cercle et un arc). Cela fonctionnera probablement avec les splines. 0 et 0 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]))
Point C: (9.292893243165555, 9.29289319446135)
Ce serait une meilleure réponse si les fonctions paramétriques présentées impliquaient en fait deux splines au lieu de deux cercles. Passer d'un cercle à un ermite cubique: trivial. Passer d'un hermite cubique à une spline cubique: plutôt pas tellement.
Merci à tous pour votre réponse. Désolé pour mon défunt. Je suis resté coincé sur un autre projet et tous les toits du Minnesota, y compris le mien, fuyaient. Cela semble vraiment prometteur. J'avais vraiment du mal à structurer la solution. Je vais jeter un oeil à le convertir pour travailler avec une spline cubique. J'ai déjà les calculs pour cela dans d'autres parties du système. Je vais vous raconter comment ça se passe. Merci!
Cela semble fonctionner très bien. J'ai mis à jour B (t) et C (s) pour générer des points le long des deux courbes d'origine et la fonction de réduction fonctionne très bien même avec les valeurs par défaut. Il a de nombreuses autres méthodes plus complexes pour trouver la réponse. Je vais devoir les explorer aussi. Merci.
Vous pouvez également utiliser la fonction 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()
Mais cela minimise certainement quelque chose de différent.
@AakashM cela minimise la distance de Manhattan entre les deux courbes, pas la distance euclidienne.
Il serait utile d'utiliser deux courbes de démonstration similaires à la question d'origine, au lieu de courbes avec deux points d'intersection connus.
@ Mike'Pomax'Kamermans vous avez raison, paramètres modifiés d'une courbe.
Merci à tous pour votre réponse. Désolé pour mon défunt. Je suis resté coincé sur un autre projet et tous les toits du Minnesota, y compris le mien, fuyaient. Je n'avais jamais vu la fonction fmin auparavant. Cela semble être une bonne possibilité. Je vais essayer. Merci!
Votre hypothèse de B '(t) = C' (s) est trop forte.
Les dérivés ont une direction et une ampleur. Les directions doivent coïncider dans les points candidats, mais les magnitudes peuvent différer.
Pour trouver des points avec les mêmes pentes dérivées et la distance la plus proche, vous pouvez résoudre un système d'équation (bien sûr, haute puissance :()
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
Avec combien de points de données traitez-vous? Il peut être plus facile de calculer par force brute les distances pour chaque paire de points (par exemple,
pairwise_distancesdans scikit-learn) si cela ne demande pas trop de calcul pour votre applicationIl n'y a en fait aucune raison pour que la paire de points les plus proches ait la même dérivée. Soit les lignes tangentes à ces points sont colinéaires, soit la paire de points la plus proche comprend un ou deux points d'extrémité de courbe. Et puis pour rendre les choses encore plus amusantes, il est tout à fait possible d'avoir plus d'un "point le plus proche" (qui dans le cas de courbes superposées, constitue des intersections)
Merci à tous pour votre réponse. Désolé pour mon défunt. Je suis resté coincé sur un autre projet et tous les toits du Minnesota, y compris le mien, fuyaient. Je vois maintenant que mon hypothèse était trop simple. Cela semblait bon à l'époque. :) Quant au nombre de points de données que je regarde: Pour certaines de mes formes, lorsque j'interpole le chemin complet, j'obtiens plus de 60 millions de points. Ma solution actuelle fonctionne en les mâchant tous, mais je cherche à le faire plus efficacement. Merci