Линия и пересечение кривой в питоне с использованием кривой Безье и вертикальной линии

Question

У меня есть кривая Безье и я пытаюсь пересечь ее вертикальной линией. У меня нет фона в математике, поэтому я надеялся найти точку пересечения с помощью функции пересечения без необходимости решать линейные уравнения. Любая помощь будет принята с благодарностью!

Вот то, что я до сих пор

#!/bin/python 

import matplotlib.pyplot as plt 
from matplotlib.path import Path 
from matplotlib.lines import Line2D 
import matplotlib.patches as patches 
import matplotlib.ticker as plticker 
import numpy as np 

from matplotlib import cbook 

from shapely.geometry import LineString, Point 

verts = [ 
    (0., 0.), # P0 
    (0, 100), # P1 
    (100, 0), # P2 
    (100, 100), # P3 
    ] 

codes = [Path.MOVETO, 
     Path.CURVE4, 
     Path.CURVE4, 
     Path.CURVE4, 
     ] 

path = Path(verts, codes) 

fig = plt.figure() 
ax = fig.add_subplot(111) 
patch = patches.PathPatch(path, facecolor='none', lw=2, picker=0) 

#add the line 
ax.add_patch(patch) 

xs, ys = zip(*verts) 
#add the handles lines 
#ax.plot(xs, ys, 'x--', lw=2, color='black', ms=10) 

#ax.text(1, 1, 'P0') 
#ax.text(20, 4, 'P1') 
#ax.text(96, 80, 'P2') 
#ax.text(96, 96, 'P3') 

ax.set_xlim(-0.1, 100.1) 
ax.set_ylim(-0.1, 100.1) 

intervals = float(5) 
loc = plticker.MultipleLocator(base=intervals) 
ax.xaxis.set_major_locator(loc) 
ax.yaxis.set_major_locator(loc) 
ax.grid(True,'both') 

################# 

print "" 
#print zip(*path.iter_segments(stroke_width=10.0,curves=False)) 

def on_move(event): 
    #thisline = event.artist 
    xmouse, ymouse = event.xdata, event.ydata 
    #print "x: ", str(xmouse), ", y: ", str(ymouse) 

def on_click(event): 
    xmouse, ymouse = event.xdata, event.ydata 
    print xmouse 
    newline = Line2D([xmouse,xmouse], [0,100]) 
    ax.add_line(newline) 
    fig.canvas.draw() 

fig.canvas.mpl_connect('motion_notify_event', on_move) 
fig.canvas.mpl_connect('button_press_event', on_click) 

############### 

plt.show() 

Answer 1

Просто используйте кубический корень найти в любом случае. Вам не нужен фон в математике, все, что вам нужно, это иметь того, кто уже сделал это для вас, что есть. Вам нужна реализация кубического корня python, но то, что вы действительно хотите, - это any Имплантация кубического корня для кривых Безье, которые могут быть адаптированы к Python, поэтому я собираюсь дать вам реализацию JavaScript, и это должно быть почти тривиально, чтобы адаптировать это к python.

Сначала мы поворачиваем кривую Безье и линии, чтобы линия стала осью х. Мы делаем это, потому что мы можем лечить «найти пересечение» просто как «корень нахождения» (давайте сделаем это в псевдокоде):

pts = line.points + curve.points 
offset = pts[0]; 
for all p in pts: 
    p -= offset 
angle = atan2(pts[1].y, pts[0].x) 
for all p in pts: 
    p = rotate(p, -angle) 

сделано.

При выражении в терминах параметра интерполяции (переменная управления кривой Безье t в этом случае) пересечения инвариантны к линейным преобразованиям, поэтому это удобно.

Затем мы используем алгоритм Кардано сделать кубический корень вывод, который я объясняю более на http://pomax.github.io/bezierinfo/#extremities, и код, который основан на http://www.trans4mind.com/personal_development/mathematics/polynomials/cubicAlgebra.htm:

function getCubicRoots(pa, pb, pc, pd) { 
    // pa...pd are our cubic bezier coordinates in one dimension 
    var d = (-pa + 3*pb - 3*pc + pd), 
     a = (3*pa - 6*pb + 3*pc)/d, 
     b = (-3*pa + 3*pb)/d, 
     c = pa/d; 

    var p = (3*b - a*a)/3, 
     p3 = p/3, 
     q = (2*a*a*a - 9*a*b + 27*c)/27, 
     q2 = q/2, 
     discriminant = q2*q2 + p3*p3*p3; 

    // and some variables we're going to use later on: 
    var u1,v1,root1,root2,root3; 

    // three possible real roots: 
    if (discriminant < 0) { 
    var mp3 = -p/3, 
     mp33 = mp3*mp3*mp3, 
     r = sqrt(mp33), 
     t = -q/(2*r), 
     cosphi = t<-1 ? -1 : t>1 ? 1 : t, 
     phi = acos(cosphi), 
     crtr = cuberoot(r), 
     t1 = 2*crtr; 
    root1 = t1 * cos(phi/3) - a/3; 
    root2 = t1 * cos((phi+2*pi)/3) - a/3; 
    root3 = t1 * cos((phi+4*pi)/3) - a/3; 
    return [root1, root2, root3].filter(accept); 
    } 

    // three real roots, but two of them are equal: 
    else if(discriminant === 0) { 
    u1 = q2 < 0 ? cuberoot(-q2) : -cuberoot(q2); 
    root1 = 2*u1 - a/3; 
    root2 = -u1 - a/3; 
    return [root1, root2].filter(accept); 
    } 

    // one real root, two complex roots 
    else { 
    var sd = sqrt(discriminant); 
    u1 = cuberoot(sd - q2); 
    v1 = cuberoot(sd + q2); 
    root1 = u1 - v1 - a/3; 
    return [root1].filter(accept); 
    } 
} 

Вы вычислить корни для x и y функций отдельно , который даст вам два списка t значений, для которых может быть перекрестки, и любого t значения, которое появляется в обоих x и y списках является интер раздел.

Этот код основан на двух вспомогательных функций, которые довольно тривиально, но в коде я скопированные формы:

// A helper function to filter for values in the [0,1] interval: 
function accept(t) { 
    return 0<=t && t <=1; 
} 

// A real-cuberoots-only function: 
function crt(v) { 
    if(v<0) return -Math.pow(-v,1/3); 
    return Math.pow(v,1/3); 
}