Odpowiedzi:
Oto moja próba. Poniższe algorytmy są dalekie od ideału , ale są proste i uważam, że powinieneś zacząć od tego, sprawdzić, czy działają w twojej sytuacji, i przejść na coś szybszego i / lub dokładniejszego później.
Pomysł jest następujący:
Krzywa Béziera jest parametryzowana przez funkcję F(t)
wykorzystującą zestaw punktów kontrolnych i zmienny parametr t
. Liczba punktów generujących jest nieistotna.
Linia jest parametryzowana dwoma punktami A
i B
.
Niech SAMPLES = 10
na przykład
Zacznij od t0 = 0
it1 = 1
Pozwolić dt = (t1 - t0) / SAMPLES
Jeśli dt < 1e-10
(lub jakikolwiek inny warunek dokładności, który uznasz za odpowiedni), algorytm jest zakończony i odpowiedź brzmiF(t0)
.
Oblicz listę SAMPLES + 1
punktów na krzywej Béziera:
L[0] = F(t0)
L[1] = F(t0 + dt)
L[2] = F(t0 + 2 * dt)
L[SAMPLES] = F(t0 + SAMPLES * dt)
Znajdź punkt L
z indeksem i
najbliższy linii. Użyj dowolnej znanej metody odległości punkt / linia , na przykład odległości kwadratowej, ||AB^L[i]A||² / ||AB||²
gdzie ^
oznacza iloczyn krzyżowy i ||…||
jest odległością.
Jeśli i == 0
ustaw i = 1
; jeśli i == SAMPLES
, ustawi = SAMPLES - 1
Niech t1 = t0 + (i + 1) * dt
it0 = t0 + (i - 1) * dt
Wróć do kroku 3.
Tym razem mamy dwie krzywe Béziera, parametryzowane przez F(t)
i G(t)
.
Niech SAMPLES = 10
na przykład
Start z t0 = 0
, t1 = 1
, s0 = 0
is1 = 1
Pozwolić dt = (t1 - t0) / SAMPLES
Pozwolić ds = (s1 - s0) / SAMPLES
Jeśli dt < 1e-10
(lub jakikolwiek inny warunek dokładności, który uznasz za odpowiedni), algorytm jest zakończony i odpowiedź brzmiF(t0)
.
JEŻELI jest to pierwszy przebieg pętli:
6.1 Oblicz listę SAMPLES + 1
punktów na F
( patrz wyżej ).
6.2 Oblicz listę SAMPLES + 1
punktów na G
.
6.3 Znajdź, która para punktów jest najbliżej siebie.
6.4 Aktualizacja t0
, t1
, s0
, s1
jak widać powyżej.
ELSE : alternatywnie obliczyć listę punktów na F
OR listę punktów G
, które następnie znaleźć punkt F
jest najbliżej G(s0)
i aktualizacji t0
oraz t1
, LUB która punktu G
jest najbliżej F(t0)
i aktualizacji s0
oraz s1
.
Wróć do kroku 3.
Z założenia algorytmy te zawsze będą zbieżne do lokalnego minimum. Nie ma jednak gwarancji, że zostaną one dostosowane do najlepszego rozwiązania. W szczególności algorytm krzywej Béziera wcale nie jest zbyt dobry, aw przypadku, gdy dwie krzywe znajdują się blisko siebie w wielu miejscach, możesz niestety przegapić rozwiązanie z dużej odległości.
Ale jak powiedziałem, zanim zaczniesz myśleć o bardziej solidnych rozwiązaniach, powinieneś najpierw poeksperymentować z tymi prostymi.
1) Przetłumacz wszystko na jedną oś, więc zamiast obliczać długość jednego punktu do „linii”, „linią” jest, powiedzmy, oś Y.
Potem, biorąc pod uwagę krzywą Beziera, powiedziałbym, że zależy to od liczby punktów kontrolnych.
Jeśli są trzy, (początek, „kontrola” i koniec) zrobiłbym jakiś skan (powiedz każdy o kilka procent, a następnie dopracuj między najbliższymi (stosując powiedzmy podejście „binarne”).
Więcej punktów Wypróbuję parę, która była najbliżej (przetłumaczona oś Y).
Jestem pewien, że matematyk może dać ci dokładne rozwiązanie (w matematyce), ale jeśli chcesz znaleźć / rozwiązanie w grze wideo, może być lepiej z nieco ok rozwiązanie, ponieważ prawdziwe rozwiązanie może zawierać kilka odpowiedzi ( Nie mówię nawet o mocy obliczeniowej).
Niektóre odpowiedzi ze strony blogu Algorytmist , która poprawnie znajduje najbliższy punkt na danej kwadratowej krzywej Béziera.
Demo .
W przypadku krzywej Beziera - przypadek linii prostej, najdokładniejszym sposobem na znalezienie odpowiedzi jest wykonanie następujących czynności: