Jak obliczyć najbliższy punkt na 2 krzywych?

Biorąc pod uwagę punkty linii i kwadratową krzywą Beziera, jak obliczyć ich najbliższy punkt? .... Podobnie, biorąc pod uwagę punkty 2 krzywych, jak uzyskać najbliższy punkt?

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:

• Próbkuj krzywą Béziera, znajdź najbliższy punkt na tej próbce
• Próbkuj okolicę wokół znalezionego punktu, znajdź nowy najbliższy punkt
• Kontynuuj, aż punkt nie zmieni się już wiele

Algorytm odległości od krzywej Béziera do linii

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 Ai B.

1. Niech SAMPLES = 10na przykład

2. Zacznij od t0 = 0it1 = 1

3. Pozwolić dt = (t1 - t0) / SAMPLES

4. 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) .

5. Oblicz listę SAMPLES + 1punktó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)

6. Znajdź punkt Lz indeksem inajbliż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ą.

7. Jeśli i == 0ustaw i = 1; jeśli i == SAMPLES, ustawi = SAMPLES - 1

8. Niech t1 = t0 + (i + 1) * dtit0 = t0 + (i - 1) * dt

9. Wróć do kroku 3.

Algorytm odległości od krzywej Béziera do krzywej Béziera

Tym razem mamy dwie krzywe Béziera, parametryzowane przez F(t)i G(t).

1. Niech SAMPLES = 10na przykład

2. Start z t0 = 0, t1 = 1, s0 = 0is1 = 1

3. Pozwolić dt = (t1 - t0) / SAMPLES

4. Pozwolić ds = (s1 - s0) / SAMPLES

5. 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) .

6. JEŻELI jest to pierwszy przebieg pętli:

   6.1 Oblicz listę SAMPLES + 1punktów na F( patrz wyżej ).

   6.2 Oblicz listę SAMPLES + 1punktów na G.

   6.3 Znajdź, która para punktów jest najbliżej siebie.

   6.4 Aktualizacja t0, t1, s0, s1jak widać powyżej.

7. ELSE : alternatywnie obliczyć listę punktów na F OR listę punktów G, które następnie znaleźć punkt Fjest najbliżej G(s0)i aktualizacji t0oraz t1, LUB która punktu Gjest najbliżej F(t0)i aktualizacji s0oraz s1.

8. Wróć do kroku 3.

Problemy

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:

1. Przekształć problem tak, aby linia prosta była zawsze pozioma przy Y = 0. Odbywa się to przez pomnożenie wszystkich punktów kontrolnych przez odpowiednią macierz afiniczną. (Zakładam, że znasz reprezentację przekształceń afinicznych płaszczyzny za pomocą macierzy 3x3 z 3 ustalonymi wpisami.)
2. Sprawdź współrzędne Y punktów kontrolnych. Jeśli nie wszystkie mają ten sam znak, może wystąpić przecięcie z linią. Oblicz pierwiastki części Y krzywej Beziera. W przypadku wielomianów można użyć dowolnej metody wyszukiwania pierwiastków, jest ich mnóstwo w literaturze. Na przykład google „wypukły marsz kadłuba” - jest to dość dobra metoda dla wielomianów używanych w krzywych Beziera. Każdy znaleziony pierwiastek jest wartością czasową przecięcia z linią, gdzie odległość wynosi zero - praca jest zakończona.
3. Jeśli wszystkie współrzędne Y mają ten sam znak, oblicz pochodną części Y krzywej Beziera. Możesz zignorować współrzędne X punktów, ponieważ nie mają one znaczenia - linia docelowa jest pozioma. Znajdź korzenie tej pochodnej. Są to wartości czasu, w których krzywa jest lokalnie najbliżej linii.
4. Jawnie oceń krzywą Beziera dla wszystkich pierwiastków znalezionych w poprzednim kroku i zgłoś pierwiastek, który daje najmniejszą odległość od linii. Musisz także sprawdzić punkty końcowe - mogą dać mniejszą odległość niż jakikolwiek root.