Zuverlässiger Test für den Schnittpunkt zweier Bezier-Kurven

Wie kann man zuverlässig herausfinden, ob sich zwei planare Bezier-Kurven schneiden? Mit "zuverlässig" meine ich, dass der Test nur dann mit "Ja" antwortet, wenn sich die Kurven schneiden, und mit "Nein" nur, wenn sie sich nicht schneiden. Ich muss nicht wissen, bei welchen Parametern die Kreuzung gefunden wurde. Ich möchte auch Gleitkommazahlen in der Implementierung verwenden.

Ich habe auf StackOverflow mehrere Antworten gefunden, die die Begrenzungsrahmen der Kurven für den Test verwenden: Dies ist nicht das, wonach ich suche, da ein solcher Test möglicherweise Schnittpunkte meldet, selbst wenn sich die Kurven nicht schneiden.

Das nächste, was ich bisher gefunden habe, ist der " Begrenzungskeil " von Sederberg und Meyers, aber er unterscheidet "nur" zwischen höchstens eins und zwei oder mehr Kreuzungen, während ich wissen möchte, ob es höchstens null gibt und eine oder mehrere Kreuzungen.

computational-geometry bezier-curve cad Ecir Hana
quelle

Ich bin mir nicht sicher, ob es als solches existiert. Es ist ziemlich trivial, festzustellen, ob es eine Möglichkeit für 0-1 oder 2 oder mehr gibt, aber die Formulierung macht es nicht wirklich einfach, sicherzustellen, dass es 0 oder 1 ist, ohne es tatsächlich zu überprüfen.

Joojaa

Was sind die Laufzeitanforderungen? Eine Lösung, die in der Lage sein sollte, ziemlich genaue Ergebnisse zu erzielen, besteht darin, beide Kurven durch eine große Anzahl kurzer gerader Segmente zu approximieren und sie dann paarweise zu schneiden. Das kostet aber viel Zeit und Speicher.

Dragonseel

@Dragonseel Nun, ich würde mich wirklich über jede Lösung freuen, aber da du O (1) gefragt hast, wäre das nett. Aber die Annäherung der Kurven mit Liniensegmenten führt zu den gleichen Problemen wie der Test für die Überlappung des Begrenzungsrahmens ...

Ecir Hana

Interessantes Problem. Ich glaube nicht, dass es eine einfache Antwort gibt, aber ich würde gerne falsch liegen. Haben Sie einen Link für das Papier von Sederberg und Meyers?

Daniel M Gessel

@DanielMGessel Ja, siehe oben.

Ecir Hana

Antworten:

Eine alternative Möglichkeit, das Problem zu formulieren, besteht darin, eine Funktion zu definieren, die den Abstand zwischen Punkten auf den beiden Kurven als Funktion der Kurvenparameter angibt. Versuchen Sie dann, das globale Minimum dieser Funktion zu finden. Wenn sich die Kurven schneiden, ist das Minimum Null. Andernfalls ist das Minimum ein positiver Abstand.

Um explizit zu sein, definieren Sie bei einem Paar von 2D-Kurven, die durch , das Distanzquadrat als $c_1, c_2 : [0, 1] \to \mathbb{R}^2$

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$

$f$

Nathan Reed
quelle

[0, 1]^{2}

$[0,1]^2$

R^{2}

$R^2$

[0, 1]

$[0,1]$

R^{2}

$\mathbb{R}^2$

x

$x$

y

$y$

x

$x$

c_{i}

$c_i$

y

$y$

@ Nathan: Ich hatte darüber nachgedacht, aber nachdem ich viel Zeit damit verbracht hatte, Code zu schreiben, um Minima in Texturkomprimierungsformaten zu finden, schien alles ein bisschen abscheulich.

Simon F

[Haftungsausschluss: Ich denke, das Folgende sollte funktionieren, habe es aber nicht selbst codiert]

Ich konnte mir keine "triviale" Methode vorstellen, um eine Ja / Nein-Antwort zu erhalten, aber das Folgende wäre ein vernünftiger Ansatz für eine praktische Lösung der Frage.

Nehmen wir an, unsere Kurven sind A (s) und B (t) mit den Kontrollpunkten { A0, A1..An } bzw. { B0, .. Bm }.

Es scheint mir, dass angesichts eines Paares von 2D-Beziers, für die wir bestimmen möchten, ob sie sich überschneiden oder nicht, sechs Fälle zu berücksichtigen sind:

Fall, in dem wir "trivial" feststellen können, dass sie sich nicht überschneiden.
Fall, in dem sie sich endlich oft schneiden und wir "leicht" feststellen können, dass sie sich definitiv mindestens einmal schneiden (aber es ist uns eigentlich egal, wo diese Schnittpunkte auftreten)
Einer der Beziers ist entartet, dh ein Punkt (der auftritt, wenn alle Kontrollpunkte identisch sind). Wir können davon ausgehen, dass wir den Fall, in dem beide Punkte sind, bereits behandelt haben.
Eine oder mehrere der Kurven sind geschlossen, z. A0 == An. Um das Leben einfacher zu machen, werden wir solche Kurven unterteilen und von vorne beginnen.
Es gibt unendlich viele Schnittpunkte, da jeder Teil eines "übergeordneten" Bezier ist und sich überlappt.
Wir sind uns über die oben genannten Fälle nicht sicher und müssen weiter untersucht werden

Im Moment werden wir 3 und 4 ignorieren, aber später darauf zurückkommen.

Fall 1

Wie Sie in Ihrer Frage andeuten , können sich die Kurven nicht schneiden , wenn sich die jeweiligen Begrenzungsrahmen der Kontrollpunkte von A und B ) nicht schneiden. Offensichtlich ist dies ein schneller Ablehnungstest, aber er ist zu konservativ. Wie Sie wahrscheinlich wissen, bildet bei einer Bezier-Kurve die konvexe Hülle ihrer Kontrollpunkte eine (engere) Grenze für die Kurve. Wir können daher die Trennachsentechnik verwenden, um zu entscheiden, ob sich die Rümpfe von A und B nicht schneiden. (zB wie in Wikipedia gezeigt :)

Fall 2

Wenn der Fall 1-Test fehlschlägt, können Sie prüfen, ob eine Kreuzung "trivial" vorhanden ist. Jetzt gibt es wahrscheinlich bessere Möglichkeiten, dies zu tun, aber mir ist der folgende, relativ billige Ansatz eingefallen:

Betrachten Sie nur Kurve A:

$A_0$ $A_n$ $\overline{A_0A_n}$ $\overline{A_0A_n}$

Wenn wir dasselbe mit Kurve B machen, erhalten wir den folgenden (möglichen) Fall:

$A_0$ $A_n$ $B_0$ $B_m$

Fall 6

$A^1, A^2, B^1, B^2$

$(A^1,B^1), (A^2, B^1)...(A^2, B^2)$

Fall 3 & 5

Hier wird es etwas langweiliger.

Wenn "Fall 3" den "Fall 1" -Test besteht, scheint es mir, dass Sie nach einer tatsächlichen Kreuzung suchen müssen. Angesichts der Tatsache, dass es einen einfachen Prozess gibt, die N Kontrollpunkte eines Bezier, A (s), auf die N-1 Punkte des Bezier, A '(s) abzubilden, die dann seine 1. Ableitung darstellen (vorausgesetzt, es wird auf die relativ seltene, sogenannte "entartete" Situationen, in denen die 1. Ableitung auf Null geht), dann könnte die Newton-Iteration (in einer Dimension) verwendet werden, um mögliche Lösungen zu finden.
Beachten Sie auch, dass, da die Kontrollpunkte von A '(s) an die Ableitungswerte gebunden sind, die Möglichkeit besteht, einige Fälle frühzeitig zu beseitigen.

Fall 5 scheint relativ unwahrscheinlich, also könnte man vielleicht nur dann, wenn nach einigen Rekursionen kein schlüssiger Beweis vorliegt, jeden Endpunkt von A gegen Kurve B versuchen und umgekehrt. Dies würde nur einen Schnittpunkt beweisen - keinen Beweis für eine Nichtkreuzung.

Simon F.
quelle

Ja, aber ich persönlich interessiere mich mehr für den Fall, in dem Bm und / oder B0 beide innerhalb des Volumens der Max- und Min-Grenze von A liegen, es aber nicht durchdringen, dann müssen Sie den Schnittpunkt unterteilen und im schlimmsten Fall berechnen Punkt. Besser wäre es, den minimalen Begrenzungsrahmen zu verwenden, der auch als Approximation dicker Linien bezeichnet wird.

Joojaa

Angesichts der Tatsache, dass mit jeder binären Unterteilung die Differenz zwischen der Kurve und dem Segment, das die Endpunkte verbindet, um einen vernünftigen Faktor abnimmt (und ich denke, dass es für Quadrate 4x gewesen sein könnte), gehen die Grenzen sicherlich ziemlich schnell zu einem "dünnen" Band konvergieren.

Simon F

Ja, aber im schlimmsten Fall beginnt das andere Bezier beim anderen.

Joojaa

Sie meinen zum Beispiel An == B0 . Definieren Sie das als Kreuzung oder nicht?

Simon F

Nicht mehr wie B0 ist irgendwo auf der Kurve. Oder sogar eine nur minimale Überfahrt

joojaa