Wiarygodny test na przecięcie dwóch krzywych Beziera

Jak niezawodnie dowiedzieć się, czy przecinają się dwie płaskie krzywe Beziera? Przez „niezawodnie” rozumiem, że test odpowie „tak” tylko wtedy, gdy krzywe się przecinają, i „nie” tylko wtedy, gdy się nie przecinają. Nie muszę wiedzieć, przy jakich parametrach znaleziono skrzyżowanie. W implementacji chciałbym również użyć liczb zmiennoprzecinkowych.

Znalazłem kilka odpowiedzi na StackOverflow, które używają obwiedni krzywych do testu: nie o to mi chodzi, ponieważ taki test może zgłosić przecięcie, nawet jeśli krzywe się nie przecinają.

Jak dotąd znalazłem najbliższy „ klin ograniczający ” Sederberga i Meyersa, ale „tylko” rozróżnia skrzyżowanie co najwyżej jeden i dwa lub więcej, podczas gdy chcę wiedzieć, czy jest co najwyżej zero i jedno lub więcej skrzyżowań.

computational-geometry bezier-curve cad

— Ecir Hana
źródło

Nie jestem pewien, czy istnieje jako takie, określenie wetehr lub istnieje możliwość dla 0-1 lub 2 lub więcej jest dość trywialna, ale sformułowanie tak naprawdę nie sprawia, że łatwo jest upewnić się, że jego wartość 0 lub 1 nie jest sprawdzana.

— joojaa

Jakie są wymagania dotyczące czasu wykonywania? Rozwiązaniem, które powinno być w stanie dawać całkiem dokładne wyniki, byłoby przybliżenie obu krzywych dużą liczbą krótkich prostych odcinków, a następnie ich przecięcie parami. Ale to kosztuje dużo czasu i pamięci.

— Dragonseel

@Dragonseel Cóż, byłbym szczęśliwy dla każdego rozwiązania, naprawdę, ale skoro poprosiłeś O (1), byłoby miło. Ale przybliżanie krzywych za pomocą segmentów linii prowadzi do tych samych problemów, co test nakładania się ramki granicznej ...

— Ecir Hana

Ciekawy problem. Nie wydaje mi się, żeby istniała łatwa odpowiedź, ale chciałbym się mylić. Czy masz link do artykułu Sederberga i Meyersa?

— Daniel M Gessel

@DanielMGessel Tak, patrz edycja powyżej.

— Ecir Hana

Odpowiedzi:

Alternatywnym sposobem sformułowania problemu jest zdefiniowanie funkcji określającej odległość między punktami na dwóch krzywych, w zależności od parametrów krzywych. Następnie spróbuj znaleźć globalne minimum tej funkcji. Jeśli krzywe przecinają się, minimum będzie wynosić zero; w przeciwnym razie minimum będzie dodatnim dystansem.

Mówiąc wprost, biorąc pod uwagę parę krzywych 2D zdefiniowanych przez $c_1, c_2 : [0, 1] \to \mathbb{R}^2$ , zdefiniuj kwadrat do kwadratu jako

f (u, v) : [0, 1]^{2} \to R_{\geq 0} \equiv | c_{2} (v) - c_{1} (u) |^{2}

$f(u,v) : [0,1]^2 \to \mathbb{R}_{\geq 0} \equiv \bigl|c_2(v) - c_1(u)\bigr|^2$

Dla krzywych sześciennych funkcja $f$ jest wówczas wielomianem szóstego stopnia w dwóch zmiennych. Następnie można zastosować techniki optymalizacji numerycznej, takie jak metoda simpleks lub sprzężone zejście gradientu . Niestety funkcja może mieć kilka lokalnych minimów (nie jest wypukła), więc optymalizacja nie jest łatwa. Mogą istnieć bardziej wyspecjalizowane metody optymalizacji wielomianów, ale nie jest to dla mnie specjalizacja.

— Nathan Reed
źródło

Dlaczego jest to wielomian szósty stopień, a nie trzeci, jeśli mówimy o sześciennych Beziersach? Dwie metody, z którymi się łączysz, umożliwiają znalezienie rozwiązań tylko w

[0, 1]^{2}

$[0,1]^2$ , w przeciwieństwie do całości

R^{2}

$R^2$ ?

— Ecir Hana

@EcirHana Jest to 6 stopień, ponieważ jest to odległość w kwadratach. (Można go wyrównać do kwadratu, ale wtedy nie jest on już wielomianowy i będzie nierównomierny przy zerach.) Zauważ, że

[0, 1]

$[0,1]$ jest przestrzenią parametrów, a nie przestrzenią, w której żyją splajny, tzn. są to splajny z punktami końcowymi. W każdym razie metody będą działać dobrze

R^{2}

$\mathbb{R}^2$ , ale „tylko zjeżdżają z góry” od wstępnego odgadnięcia i znajdują lokalne minimum; potrzeba czegoś więcej, aby zbadać cały region parametru i znaleźć globalne minimum. Ograniczenie przestrzeni parametrów jest prawdopodobnie tam pomocne.

— Nathan Reed

Nathan - niezła formuła! Jestem zardzewiały, ale: Myślę, że można podzielić każdą krzywą Beziera na maksymalnie 5 segmentów, według miejsca

x

$x$ lub

y

$y$ zmień kierunek na krzywej.

x

$x$ , jako funkcja

c_{i}

$c_i$ co najwyżej dwukrotnie zmienia kierunek (pierwiastki pochodnej), dzieląc krzywą na 3 segmenty, z których 2 można ponownie podzielić przez zmiany kierunku

y

$y$ . Teraz masz nie proste segmenty, ale segmenty, które „nie wyginają się zbytnio”. Myślę, że jeśli zaczniesz wyszukiwanie od 25 punktów, wybranych parami segmentów, zawsze możesz znaleźć globalne minima, ale nie do końca wiem, jak to udowodnić (lub obalić).

— Daniel M Gessel

@Nathan: Zastanawiałem się nad tym, ale po spędzeniu dużo czasu na pisaniu kodu, aby znaleźć minima w formatach kompresji tekstur, wszystko to wydawało się trochę ohydne.

— Simon F

[Oświadczenie: Myślę, że następujące elementy powinny działać, ale sam ich nie kodowałem]

Nie mogłem wymyślić „trywialnej” metody udzielania odpowiedzi tak / nie, ale poniższe podejście byłoby rozsądnym podejściem do praktycznego rozwiązania tego pytania.

Załóżmy, że nasze krzywe to A (s) i B (t) z punktami kontrolnymi odpowiednio { A0, A1..An } i { B0, .. Bm }.

Wydaje mi się, że biorąc pod uwagę parę Beziers 2D, dla których chcemy ustalić, czy przecinają się, czy nie, należy rozważyć sześć przypadków:

Przypadek, w którym możemy „w trywialny sposób” ustalić, że się nie przecinają.
Przypadek, w którym przecinają się one skończoną liczbę razy, a my możemy „łatwo” ustalić, że zdecydowanie przecinają się przynajmniej raz (ale tak naprawdę nie obchodzi nas, gdzie występują te skrzyżowania)
Jeden z Beziersów jest zdegenerowany, tj. Punkt (który wystąpi, jeśli wszystkie punkty kontrolne są identyczne). Możemy założyć, że już załatwiliśmy sprawę, w której oba są punktami.
Jedna lub więcej krzywych jest zamkniętych, np. A0 == An. Aby ułatwić życie, podzielimy takie krzywe i zaczniemy od nowa.
Istnieje nieskończona liczba punktów przecięcia, ponieważ każdy jest podzbiorem „nadrzędnego” Beziera i nakładają się na siebie.
Nie jesteśmy pewni powyższych przypadków i potrzebujemy dalszego dochodzenia

Na razie zignorujemy 3 i 4, ale wrócimy do nich później.

Przypadek 1

Jak sugerujesz w swoim pytaniu, jeśli odpowiednie pola ograniczające punktów kontrolnych A i B ) nie przecinają się, wówczas krzywe nie mogą się przecinać. Oczywiście jest to szybki test odrzucenia, ale jest zbyt konserwatywny. Jak zapewne wiesz, z krzywą Beziera wypukły kadłub punktów kontrolnych tworzy (węższe) wiązanie na krzywej. Możemy zatem użyć techniki osi oddzielającej, aby zdecydować, czy kadłuby A i B nie przecinają się. (np. jak pokazano w Wikipedii :)

Przypadek 2

Jeśli test przypadku 1 nie powiedzie się, możesz sprawdzić „trywialne” istnienie skrzyżowania. Teraz są prawdopodobnie lepsze sposoby, aby to zrobić, ale przyszło mi do głowy następujące stosunkowo tanie podejście:

Rozważ tylko krzywą A:

Wiemy, że krzywa zaczyna się od $A_0$ kończy się o godz $A_n$ i będzie leżeć wewnątrz wypukłego kadłuba. Dla uproszczenia obliczmy kierunek odcinka linii $\overline{A_0A_n}$ i obliczyć granice po obu stronach (tj. wziąć iloczyn iloczynu pozostałych punktów kontrolnych względem prostopadłej do $\overline{A_0A_n}$ ).

Jeśli zrobimy to samo z krzywą B, otrzymamy następujący (możliwy) przypadek:

Jeśli znajdziemy $A_0$ i $A_n$ znajdują się poza przeciwnymi granicami B i tamto $B_0$ i $B_m$ znajdują się poza granicami A, a zatem, dzięki ciągłości Beziersa, musi istnieć co najmniej jedno skrzyżowanie.

Przypadek 6

Jeśli nie możemy natychmiast pokazać żadnego z powyższych przypadków, podziel każdy Beziers na dwie „połowy”, tj $A^1, A^2, B^1, B^2$ . Jest to stosunkowo proste (pozostawione jako ćwiczenie dla czytelnika), ale jest szczególnie trywialne dla kwadratowego Beziersa :

Rekurencyjnie porównaj 4 kombinacje: $(A^1,B^1), (A^2, B^1)...(A^2, B^2)$ . Oczywiście, jeśli wszystkie przypadki przypadku 1 są spełnione, nie ma przecięcia. W przypadku niepowodzenia 1, kontynuuj pozostałe testy z tym zredukowanym podzbiorem.

Przypadek 3 i 5

Tutaj staje się nieco bardziej nużące.

Jeśli „przypadek 3” przejdzie test „przypadek 1”, wydaje mi się, że trzeba rozwiązać rzeczywiste skrzyżowanie. Biorąc pod uwagę, że istnieje prosty proces mapowania N punktów kontrolnych Beziera, A (s), do punktów N-1 Beziera, A (s), reprezentujących wówczas jego 1. pochodną (pod warunkiem zachowania ostrożności stosunkowo rzadkie, tak zwane „zdegenerowane” sytuacje, w których 1. pochodna ma wartość zerową), następnie iteracja Newtona (w jednym wymiarze) może być wykorzystana do znalezienia potencjalnych rozwiązań.
Należy również zauważyć, że ponieważ punkty kontrolne A '(s) są powiązane z wartościami pochodnymi, istnieje możliwość wcześniejszej eliminacji niektórych przypadków.

Przypadek 5 wydaje się stosunkowo mało prawdopodobny, więc być może tylko wtedy, gdy po kilku rekurencjach nie będzie rozstrzygającego dowodu, można wypróbować każdy punkt końcowy A względem krzywej B i odwrotnie. Dałoby to tylko dowód skrzyżowania - a nie dowód braku skrzyżowania.

— Simon F.
źródło

Tak, ale osobiście jestem bardziej zainteresowany przypadkiem, w którym o przypadku, w którym Bm i / lub B0 znajdują się zarówno w granicach maksymalnego i minimalnego ograniczenia A, ale go nie przebijają, musisz podzielić, aw najgorszym przypadku obliczyć przecięcie punkt. Lepszym sposobem byłoby użycie minimalnej ramki granicznej znanej również jako przybliżenie grubej linii.

— joojaa

Biorąc pod uwagę, że z każdym podziałem binarnym różnica między krzywą a odcinkiem łączącym punkty końcowe zmniejsza się o rozsądny czynnik (i, z góry mojej głowy, myślę, że może to być 4x dla kwadratyków) na pewno granice dość szybko zbiegać się w „cienką” wstążkę.

— Simon F.

Tak, ale najgorszym scenariuszem jest to, że drugi Bezier zaczyna się od drugiego.

— joojaa

Masz na przykład na myśli An == B0 . Czy określasz to jako skrzyżowanie czy nie?

— Simon F

Nie ma już czegoś takiego jak B0 gdzieś na krzywej. Lub nawet minimalnie przekraczający

— joojaa