Znajdowanie punktów na krzywej Beziera na podstawie odległości od innego punktu

Question

Mam więc krzywą 3D kubiczną beziera i punkt początkowy znajdujący się w dowolnym miejscu wzdłuż krzywej i potrzebuję znaleźć drugi punkt dalej w dół krzywej, która jest określoną odległością przestrzeni świata (nie odległość od odległości) od pierwszego punktu.

Inną kwestią byłoby, gdyby drugi punkt osiągnął koniec krzywej i nadal nie był w pożądanej odległości od przestrzeni świata, w którym to przypadku chciałbym, aby kontynuował wzdłuż stycznej, aż odległość zostanie osiągnięta.

Wszelkie pomysły?

Answer 1

Niestety, nie znam żadnego równania zamkniętego, które dałoby pożądany punkt. Być może najprostszą techniką przybliżenia tego punktu jest rekursywne cięcie krzywej Beziera na 2 mniejsze krzywe Beziera przy użyciu de Casteljau's algorithm. Rekurencja rozstępuje się, gdy albo (a) wszystkie punkty graniczne dla krzywej są albo zbyt blisko lub zbyt daleko od danego punktu, lub (b) wszystkie punkty graniczne krzywej są "wystarczająco blisko" do bycia równa żądanej odległości (być może wszystkie mieszczą się w tym samym pikselu).

Jestem prawie pewien, że maksymalna liczba punktów na danej krzywej Beziera, która jest daną odległością liniową od pewnego punktu, wynosi 4 punkty. (Może się to zdarzyć, gdy dana krzywa Beziera ma samo przecięcie).

EDIT:

Może powinienem przeczytać cały pytanie przed skokiem w z odpowiedzią, tak? Standardowy "czteropunktowy" segment krzywej Beziera może być postrzegany jako jeden element o nieskończenie długiej krzywej sześciennej. W jednym miejscu może znajdować się zgięcie lub pętla lub zakręt, ale wystarczająco daleko od tej ostrej krzywej ścieżka spłaszcza się, aby zamknąć 2 proste promienie, z których każdy wskazuje w dowolnym kierunku. Niestety, powyższe rozwiązanie znajduje tylko punkty znajdujące się na krótkim odcinku krzywej Beziera. Zakładam, że chcesz mieć punkt (y) wzdłuż tej nieskończenie długiej krzywej sześciennej, która jest daną odległością od danego punktu, nawet jeśli nie znajdują się one na krótkim odcinku krzywej Beziera.

== de Casteljau w odwrotnej ==

można uruchomić (środkowy) rekurencyjny algorytm de Casteljau w odwrocie, generując nowy cztery-punktową krzywą Beziera „double” rozmiar ostatni w każdej iteracji, aż masz jeden wystarczająco duży, aby zawrzeć pożądany punkt (y). (Kiedy wszystkie 4 punkty początkowe są "zbyt blisko" do danego punktu, wówczas podwojenie gwarantuje ostatecznie utworzenie segmentu krzywej z punktem początkowym "zbyt blisko", punkt końcowy "za daleko", a następnie można użyć powyższego algorytm zbieżności w punkcie, który jest pożądaną odległością od danego punktu). To podejście polega tylko na dodawaniu, odejmowaniu, mnożeniu przez dwa i uśrednianiu, , więc w zasadzie powinno być względnie numeryczne. (W rzeczywistości nigdy nie ocenia formuły sześciennej w żadnym miejscu t).

== zero-Odkrycie ==

Można przekonwertować z reprezentacją cztero punktową do sześcienny wielomianu reprezentacji i użyć dowolnego algorytmu korzeniowy rozpoznawczej do zbiegają się w jednym z pożądanych punktów. Metoda Newtona powinna działać całkiem nieźle, ponieważ krótkie fragmenty krzywej Beziera są prawie proste. Czy możemy przystosować równania metody Newtona z Finding the Minimum Distance Between a Point and a Cubic Spline do tego problemu? Użyję algorytmu bisekcji dla uproszczenia opisu, nawet jeśli działa wolniej niż metoda Newtona.

Jak zawsze, sześcienny segmentu krzywej Beziera można opisać jako

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3. 

(Niestety, to równanie nie zawsze jest liczbowo wytrzymałe - dlatego wiele osób korzysta z rekurencyjną zmniejszenie o połowę korzystając de algorytmu Casteljau zamiast).

Ja zakładając, że masz (lub może znaleźć) wartość t_given dla danego punktu,

x_given = B(t_given).x 
y_given = B(t_given).y 

odległości między danym punkcie i jakimś innym punkcie wzdłuż krzywej jest przez Pitagorasa,

distance2(t) = (x_given - B(t).x)^2 + (y_given - B(t).y)^2. 
distance(t) = sqrt(distance2(t)). 

punkt (y) szukasz są przy zerowych funkcji

given_distance2 = given_distance^2. 
f(t) = distance2(t) - given_distance2. 

Zakładając, że biorąc pod uwagę odległość nie jest zero, a dany punkt posiada algorytm t_given < 1, bisekcji byłoby coś podobnego

left = t_given 
right = 1 // the endpoint of the given Bezier curve segment 
while(distance2(right) < given_distance2){ 
    right = right*2 
} 

W tym momencie t_left jest bliżej danym punkcie niż żądana odległość, a t_right jest dalej niż wymagana odległość (lub może dokładnie równa). Ponieważ mamy jeden punkt za blisko, a inny punkt za daleko, algorytm bisekcji powinien działać.

Następnie sprawdzamy: czy pierwszy segment został pozostawiony ... punkt środkowy zawiera zero lub środek ... w prawo?

if(f(left)*f(midpoint) < 0) then 
     // throw away right half 
     right = midpoint 
    else 
     // throw away left half 
     left = midpoint 
} 

return(right) 

W tym punkcie wartość „prawda” jest wartość T i B (z prawej) jest odpowiedni punkt tak, że odległość od tego punktu do pierwotnego danym momencie jest (w przybliżeniu) dana dystans.

Answer 2

Twoja instrukcja problemu wymaga większej precyzji. W szczególności nie masz wystarczających ograniczeń, gdy pytasz o punkt B, który wynosi N jednostek od punktu początkowego A. Może być wiele punktów, które są w odległości N od A.

Oprócz tego, co powstrzymuje cię przed próbkowaniem swojej krzywej na planie interwały wzdłuż krzywej, a następnie obliczenie odległości liniowej z powrotem do A. Nie jest optymalna, ale zadziała. Aby poradzić sobie z wieloma punktami N na odległość będziesz musiał wymyślić regułę. Może być tak proste, jak znaleziono pierwszy punkt.