Die überprüfung, ob zwei kubische Bézier-Kurven kreuzen

Kreuzung von Bézier-Kurven erfolgt durch die (sehr cool) Asymptote vector graphics language: suchen Sie nach intersect() hier.

Obwohl Sie nicht erklären, der Algorithmus, die Sie tatsächlich verwenden, gibt es, außer zu sagen, dass es von p aus. 137 "Die Metafont-Buch", es scheint, dass der Schlüssel dazu ist das zwei wichtige Eigenschaften der Bézier-Kurven (welche an anderer Stelle erklärt werden auf dieser Website aber ich kann nicht finden die Seite jetzt):

• Eine Bézier-Kurve ist immer innerhalb der bounding-box definiert durch Ihre 4 Steuerpunkte
• Eine Bezier-Kurve kann immer unterteilt in eine beliebige t Wert in 2 sub-Bezier-Kurven

Mit diesen zwei Eigenschaften und ein Algorithmus für die sich schneidenden Polygone, Sie können den Parameter recurse auf beliebiger Genauigkeit:

bezInt(B₁, B₂):

1. Hat bbox(B₁) überschneiden bbox(B₂)?
   • Nein: Return false.
   • Ja: Weiter.
2. Ist Bereich(bbox(B₁)) + area(bbox(B₂)) < Schwelle?
   • Ja: Return true.
   • Nein: Weiter.
3. Split-B₁ in B_1a - und B_1b bei t = 0.5
4. Split-B₂ in B_2a - und B_2b bei t = 0.5
5. Zurück bezInt(B_1a, B_2a) ||
   bezInt(B_1a, B_2b) ||
   bezInt(B_1b, B_2a) ||
   bezInt(B_1b, B_2b).

Diese schnell, wenn die Kurven nicht schneiden-ist das üblich?

[BEARBEITEN] Es sieht aus wie der Algorithmus für die Aufteilung einer Bezier-Kurve in zwei genannt de Casteljau-Algorithmus.

Ist es ein Fehler an meinem Ende oder an Ihrem Ende?

Sind Sie stützen Sie Ihre interpretation der Determinante auf der 4. Kommentar diese Antwort? Wenn ja, ich glaube, dass ' s, wo der Fehler liegt. Die Reproduktion der Kommentar hier:

Wenn die Determinante null ist es ist
ein root in X und Y um *genau das gleiche
Wert von t, so gibt es eine
Schnittpunkt der beiden Kurven. (die t
vielleicht nicht in dem Intervall 0..1
obwohl).

Sehe ich keine Probleme mit diesem Teil, aber der Autor geht auf zu sagen:

Wenn die Determinante ist <> gleich null, Sie kann
werden Sie sicher, dass die Kurven nicht
schneiden überall.

Ich glaube nicht, dass das korrekt ist. Es ist durchaus möglich für die beiden Kurven schneiden sich in einem Ort, wo die t-Werte unterscheiden sich, und in diesem Fall gibt es eine Kreuzung, auch wenn die matrix einen nicht-null-Determinante. Ich glaube, dass dies ist, was passiert in Ihrem Fall.

Ich bin kein Experte für diese Art der Sache, aber ich Folge einer schönen blog, dass die Gespräche viel über Kurven. Er hat Verbindung zu zwei nette Artikel im Gespräch über Ihr problem (der zweite link hat eine interaktive demonstration und einige source-code). Andere Menschen haben viel besseren Einblick in das problem, aber ich hoffe, das hilft!

http://cagd.cs.byu.edu/~557/text/ch7.pdf

Ich würde sagen, dass die einfachste und wahrscheinlich Schnellste Antwort ist, unterteilen Sie Sie in sehr kleine lines und finden Sie die Punkte, wo die Kurven sich schneiden, wenn Sie es tatsächlich tun.

public static void towardsCubic(double[] xy, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, double t) {
    double x, y;
    x = (1 - t) * (1 - t) * (1 - t) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3;
    y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3;
    xy[0] = x;
    xy[1] = y;
}

public static void towardsQuad(double[] xy, double x0, double y0, double x1, double y1, double x2, double y2, double t) {
    double x, y;
    x = (1 - t) * (1 - t) * x0 + 2 * (1 - t) * t * x1 + t * t * x2;
    y = (1 - t) * (1 - t) * y0 + 2 * (1 - t) * t * y1 + t * t * y2;
    xy[0] = x;
    xy[1] = y;
}

Natürlich die brute-force-Antwort ist schlecht zu Sehen, bo{4}'s Antwort, und es gibt eine Menge von linearen geometrie und Kollisionsabfrage, die tatsächlich helfen, eine ganze Menge.

Wählen Sie die Anzahl der Scheiben, die Sie wollen, für die Kurven. So etwas wie 100 sollte groß sein.

Nehmen wir alle Segmente und Sortieren Sie basierend auf den größten Wert von y, die Sie haben. Wir fügen Sie dann eine zweite Flagge in der Liste für den kleinsten Wert von y für dieses segment.

Wir halten eine Liste von aktiven Kanten.

Durchlaufen wir die y-sortierte Liste von segment -, wenn wir begegnen, ein führender segment fügen wir es in die aktive Liste. Wenn wir auf dem kleinen y-Wert gekennzeichnet wird, entfernen wir das betreffende segment aus der aktiven Liste.

Wir dann einfach Durchlaufen den gesamten Satz von Segmenten mit welchen Mengen um eine scan-Linie, die Erhöhung unserer y-monoton, da wir einfach nur Durchlaufen der Liste. Wir iterieren über die Werte in der sortierten Liste wird in der Regel entfernen Sie ein segment und eine neue hinzufügen-segment (oder für die split-und merge-Knoten, hinzufügen von zwei Segmenten oder entfernen Sie die beiden Segmente). Dabei halten Sie eine aktuelle Liste der relevanten Segmente.

Laufen wir schnell scheitern intersect prüfen, wie wir hinzufügen eines neuen aktiven segment zu der Liste der aktiven Segmente, gegen die nur das segment und die gerade aktiven Segmente.

Also zu allen Zeiten wissen wir genau, welche linienabschnitte sind relevant, da wir Durchlaufen den in die Stichprobe einbezogenen Segmente der Kurven. Wir wissen, dass diese Segmente teilen überschneiden sich in der y-coords. Wir können schnell fehl, neues segment, das überschneidet sich nicht mit Bezug auf Ihren x-Koordinaten. In dem seltenen Fall, dass Sie überschneiden sich in die x-coords, dann überprüfen wir, ob diese Segmente überschneiden.

Dies wird wahrscheinlich reduzieren Sie die Anzahl der Zeile die Schnittmenge prüft grundsätzlich die Anzahl der Kreuzungen.

foreach(segment in sortedSegmentList) {
    if (segment.isLeading()) {
        checkAgainstActives(segment);
        actives.add(segment);
    }
    else actives.remove(segment)
}

checkAgainstActive() würde einfach prüfen, ob das segment und ein segment der aktiven Liste überschneiden sich Ihre x-Koordinaten, wenn Sie es tun, dann führen Sie die Linie sich überschneiden überprüfen, und ergreifen Sie die entsprechenden Maßnahmen.

Beachten Sie auch, das funktioniert für eine beliebige Anzahl von Kurven, jede Art von Kurven beliebiger Reihenfolge der Kurven, in beliebiger Mischung. Und wenn wir Durchlaufen die gesamte Liste der Segmente findet jeder Kreuzung. Es findet jeden Punkt einer Bezier-schneidet einen Kreis oder jeder Kreuzung, dass ein Dutzend quadratische Bezier-Kurven haben mit einander (oder sich selbst), und alle in der gleichen Sekunde.

Den oft zitierten Kapitel 7 Dokument Noten, für die Unterteilung Algorithmus:

"Einmal ein paar Kurven wurde unterteilt genug sind, dass Sie jeweils angenähert werden durch ein Liniensegment innerhalb einer Toleranz"

Können wir im wahrsten Sinne des Wortes überspringen der Zwischenhändler. Wir können dies tun, schnell genug, so einfach vergleichen Liniensegmenten, die Sie mit einem tolerierbaren Betrag der Fehler aus der Kurve. Am Ende, das ist, was die typische Antwort nicht.

Zweitens, beachten Sie, dass der Großteil der Steigerung der Geschwindigkeit für die Kollisionserkennung hier, nämlich der geordneten Liste der Segmente sortiert, basierend auf Ihrer höchsten y so fügen Sie die aktive Liste und die niedrigsten y, entfernen Sie aus der aktiven Liste, ebenso kann getan werden, für den Rumpf Polygone der Bézier-Kurve direkt. Unsere Strecke ist einfach ein polygon der Ordnung 2, aber wir konnten eine beliebige Anzahl der Punkte gerade als trivial, und die überprüfung der bounding box alle Kontrollpunkte in der Reihenfolge der Kurve wir es zu tun haben. Also anstatt eine Liste der aktiven Segmente, würden wir eine Liste der aktiven hull Polygone Punkte. Wir könnten einfach auf De Casteljau-Algorithmus zum aufteilen der Kurven, wodurch die Probenahme, da diese als unterteilt Kurven eher als Liniensegmente. Anstatt also die 2 Punkte hätten wir 4 oder 7 oder so weiter, und führen Sie die gleiche routine wird ganz leicht Richtung schnell scheitern.

Hinzufügen der entsprechenden Gruppe der Punkte bei max y, entfernen Sie es auf min y, und Vergleich nur die aktive Liste. So können wir schnell und eine bessere Umsetzung der Bezier-subdivision-Algorithmus. Durch einfach Suche nach bounding box überlappen, und dann die Unterteilung diejenigen Kurven, die sich überlappen, und entfernen Sie diejenigen, die nicht. Wie, wieder, wir können eine beliebige Anzahl von Kurven, auch diejenigen, unterteilt von Kurven in der vorherigen iteration. Und wie unsere segment-Annäherung schnell lösen Sie für jede Kreuzung position zwischen Hunderten von verschiedenen Kurven (auch aus verschiedenen Bestellungen) sehr schnell. Überprüfen Sie einfach alle Kurven zu sehen, wenn die bounding boxes überlappen, wenn Sie es tun, unterteilen wir diese, bis unsere Kurven sind klein genug, oder wir liefen aus Ihnen heraus.