Testen, ob ein Punkt im Umkreis eines Dreiecks liegt

Ich lese gerade über Methoden der Delaunay-Triangulation. Insbesondere dieser Artikel von Leach: Improving Worst-Case Optimal Delaunay Triangulation Algorithms (1992)

Darin beschreibt Leach eine Methode zum Testen, ob ein Punkt D befindet sich im Umkreis eines Dreiecks △ A B C . Dies steht im Gegensatz zur üblichen Determinantenmethode (siehe die Wikipedia-Seite zur Delunay-Triangulation, wenn Sie mehr darüber lesen möchten).

Der Test wird wie folgt beschrieben

Wir verwenden stattdessen einen Test basierend auf j -Koordinaten der Mittelpunkte des Umkreises. Wie in Abbildung 4 gezeigt, für zwei feste Standorte A Und B das Zentrum des Umkreises von A , B und ein dritter Punkt liegt auf der Winkelhalbierenden von A Und B .

Abbildung 4: Umfangskreistest

Da der Zusammenführungsschritt des Algorithmus immer die beste Kandidatenstelle oberhalb der obersten Querkante, einer Stelle, sucht D ist eine bessere Website als eine Website C wenn sein Umkreismittelpunkt tiefer auf der Winkelhalbierenden liegt. Die beste Kandidatenstelle ist diejenige, deren Umkreiszentrum am niedrigsten ist. Ersetzen ( X A , j A ) , ( X B , j B ) Und ( X C , j C ) hinein

( X − P ) 2 + ( j − Q ) 2 = R 2
und Lösung für Q gibt
Q = 1 2 ⋅ ( X A 2 + j A 2 ) ( X C − X B ) − ( X B 2 + j B 2 ) ( X C − X A ) + ( X C 2 + j C 2 ) ( X B − X A ) ( X B − X A ) ( j C − j A ) − ( X C − X A ) ( j B − j A ) .
Diese Berechnung erfordert 23 Operationen (wobei die Division durch 2 ignoriert wird und die gemeinsame Teilausdruckseliminierung angenommen wird). Zwei solche Berechnungen sind erforderlich, um die ersten beiden Kandidatenstellen zu vergleichen; Danach wird nur noch einer pro Kandidatenstandort benötigt, wodurch sich die Testkosten InCircleum etwa die Hälfte reduzieren.

Ich verfolge nicht, was hier passiert. Ich verstehe, warum die Umkreismittelpunkte auf der Linie dazwischen liegen A Und B , aber es ist mir nicht sofort klar:

  1. Warum niedriger Q ist besser für die Delaunay-Triangulation.
  2. Was die Methode tun soll, wenn die Q unter die Mitte fällt A B . Ist niedriger noch besser, oder ist uns die Entfernung von der Mitte wirklich wichtig?

Wenn jemand (1) erklären und (2) beantworten könnte, wäre dies sehr hilfreich für mich, danke.

Antworten (1)

Nach einigem Nachdenken habe ich es hinbekommen.

Wenn wir uns an den Satz über den einbeschriebenen Winkel erinnern, haben wir das

Verwenden Sie den einbeschriebenen Winkelsatz, um den Winkel bei D vom Mittelpunkt des Kreises durch A, B und D zu bestimmen

und daraus können wir sehen, dass der Winkel des Dreiecks bei ist D kann aus dem Anstieg über den Mittelpunkt von ermittelt werden A B , Q , und die halbe Entfernung von A B , dh

θ = A T A N ( | A B | 2 Q )
und darüber hinaus als | A B | 2 Ist repariert, θ wird mit größer abnehmen Q .

Daraus ergibt sich auch die Antwort auf die zweite Frage: Die Größe, die wir für diese Methode berücksichtigen müssen, ist der Abstand vom Mittelpunkt von A B .

Testen, ob ein Punkt im Umkreis eines Dreiecks liegt
AntwortenHierDatenschutz-Bestimmungen1y, 0v