Liegt der Punkt im Dreieck?

Abbildung 1: Liegt P im Dreieck ABC? Liegt Q darin?

Zugegeben: Die Frage, welcher der Punkte P und Q im Dreieck ABC liegt, ist mit einem Blick auf die erste Abbildung kinderleicht zu entscheiden. Doch könnten Sie die Frage genauso schnell beantworten, hätte ich statt der Abbildung nur die Koordinaten der Punkte A (7;0), B (6;6), C (0;4), P (1;1), Q (5;3) genannt?1

Auf dieser Seite präsentiere ich vier Ansätze, wie man anhand der Koordinaten berechnen kann, ob ein Punkt in einem Dreieck liegt. Um nicht mit Sonderfällen zu langweilen, sei vereinbart, dass nie drei der gegebenen Punkte genau auf einer Geraden liegen. Aber behalten Sie im Hinterkopf, dass dieser Sonderfall berücksichtigt werden muss, wenn Sie mit beliebig angeordneten Punkten zu tun haben!

Man kann das Problem auch auf anderen als den hier gezeigten Wegen lösen. Wenn Sie mögen, können Sie ihren Lieblingsansatz gern am Ende als Kommentar ergänzen. Auch Fragen sind willkommen!

Ansatz 1: Größe von Flächen

Die erste Idee ist, die Fläche des Dreiecks mit der Fläche eines Vierecks zu vergleichen, das aus den Eckpunkten des Dreiecks und dem fraglichen vierten Punkt gebildet wird.

Abbildung 2: Die grüne Fläche des Vierecks ABCQ ist kleiner als die schraffierte Fläche des Dreiecks ABC.
Abbildung 3: Die Fläche des Vierecks ABCP ist größer als die Fläche des Dreiecks ABC.

Ein Blick auf die Abbildungen 2 und 3 zeigt: Die Vierecksfläche ist kleiner als die Dreiecksfläche, wenn der fragliche Punkt im Dreieck liegt, und größer, wenn der fragliche Punkt außerhalb des Dreiecks liegt. Doch aufgepasst! Je nachdem, in welcher Reihenfolge man einen außen liegenden vierten Punkt zwischen die Eckpunkte des Dreiecks einordnet, kann gegebenenfalls ein …

Abbildung 4: Das Viereck ABPC ist ein überschlagenes Viereck.

… überschlagenes Viereck mit einer kleineren Fläche herauskommen. Wenn der fragliche Punkt im Dreieck liegt, kommt aber ganz sicher ein einfaches Viereck ohne Überschlag heraus. Um von keinem überschlagenen Viereck in die Irre geführt zu werden, kann man die Flächen aller drei möglichen Vierecke ausrechnen und nur das größte Ergebnis mit der Dreiecksfläche vergleichen. Ist der Ausdruck

$$\max(\square ABCP,\square ABPC,\square APBC)-\triangle ABC$$

positiv, dann ist also das größte Viereck größer als das Dreieck und der fragliche Punkt liegt draußen; ist der Ausdruck negativ, dann liegt der fraglich Punkt drinnen. Lassen Sie mich diese Formel noch einmal so ändern, dass das Doppelte der Flächen verglichen wird:

$$\max(2\,\square ABCP,2\,\square ABPC,2\,\square APBC)-2\,\triangle ABC$$

Das ändert nichts am Vorzeichen des Ergebnisses, hat aber den Hintergrund, dass es zum Berechnen der doppelten Fläche beliebiger einfacher n-Ecke die wundervolle gaußsche Flächenformel in mehreren gleichwertigen Varianten gibt. Hier eine Variante:

$$\left|\sum_{i=1}^n x_i(y_{i+1}-y_{i-1})\right|$$

Sie sieht vielleicht einschüchternd aus für Leser, die mit dem griechischen Sigma Σ als Summenzeichen nicht vertraut sind. Keine Sorge, ich schreibe die Formel ohne Summenzeichen gleich aufs Dreieck und alle Vierecke angewendet aus.2 Die senkrechten Striche |…| bedeuten, dass man auch im Fall eines negativen Ergebnisses den positiven Betrag der Zahl nimmt.

$$\begin{aligned} 2\,\triangle ABC &= |x_A(y_B-y_C)+x_B(y_C-y_A)+x_C(y_A-y_B)| \\ 2\,\square ABCP &= |x_A(y_B-y_P)+x_B(y_C-y_A)+x_C(y_P-y_B)+x_P(y_A-y_C)| \\ 2\,\square ABPC &= |x_A(y_B-y_C)+x_B(y_P-y_A)+x_P(y_C-y_B)+x_C(y_A-y_P)| \\ 2\,\square APBC &= |x_A(y_P-y_C)+x_P(y_B-y_A)+x_B(y_C-y_P)+x_C(y_A-y_B)| \end{aligned}$$

Ich mag an diesem Ansatz, dass er mit Addition, Subtraktion und Multiplikation auskommt – es muss nicht einmal geteilt werden.

Ansatz 2: Lage in der halbierten Ebene

Für den zweiten Ansatz wird eine Gerade durch den fraglichen Punkt und einen Eckpunkt des Dreiecks gezogen. Die Idee ist zu prüfen, ob die beiden anderen Eckpunkte des Dreiecks auf verschiedenen Seiten dieser Geraden liegen.

Abbildung 5: Zieht man durch Q und einen der Punkte A, B, C eine Gerade, liegen die beiden übrigen Punkte jeweils auf verschiedenen Seiten der Geraden.
Abbildung 6: Zieht man eine Gerade durch P und A oder P und C, liegen die beiden übrigen Punkte jeweils auf der gleichen Seite der Geraden.

Wenn der fragliche Punkt im Dreieck liegt, landen die übrigen Eckpunkte des Dreiecks immer auf verschiedenen Seiten der Geraden. Liegt der fragliche Punkt hingegen außerhalb des Dreiecks, findet man die übrigen Eckpunkte in zwei der drei möglichen Fälle auf der gleichen Seite der Geraden. Um Klarheit zu gewinnen, muss man also maximal zwei Fälle überprüfen.

Für die Prüfung habe ich in dem Artikel „Liegen zwei Punkte auf derselben Seite?“ eine Methode hergeleitet. Für den Fall einer Geraden durch P und A rechnet man einmal den Ausdruck $\mathrm{Se}_{P,A}(x_B,y_B)$ aus, um die Seite der Geraden zu identifizieren, auf der B liegt, und dann den Ausdruck $\mathrm{Se}_{P,A}(x_C,y_C)$ für die Lage von C. Von den Ergebnissen interessieren nur die Vorzeichen. Wenn man mit sgn das Vorzeichen erfragt,3 ist

$$\begin{aligned} \mathrm{sgn}(\mathrm{Se}_{P,A}(x_B,y_B)) &= \mathrm{sgn}((y_B-y_P)(x_A-x_P)-(y_A-y_P)(x_B-x_P)) \\ \mathrm{sgn}(\mathrm{Se}_{P,A}(x_C,y_C)) &= \mathrm{sgn}((y_C-y_P)(x_A-x_P)-(y_A-y_P)(x_C-x_P)) \end{aligned}$$

Identische Vorzeichen bedeuten, dass B und C auf derselben Seite der Geraden liegen; unterschiedliche Vorzeichen bedeuten, dass sie auf verschiedenen Seiten liegen. Trifft Letzteres zu, wird das gleiche Spiel noch einmal mit einer Geraden durch P und B wiederholt:

$$\begin{aligned} \mathrm{sgn}(\mathrm{Se}_{P,B}(x_A,y_A)) &= \mathrm{sgn}((y_A-y_P)(x_B-x_P)-(y_B-y_P)(x_A-x_P)) \\ \mathrm{sgn}(\mathrm{Se}_{P,B}(x_C,y_C)) &= \mathrm{sgn}((y_C-y_P)(x_B-x_P)-(y_B-y_P)(x_C-x_P)) \end{aligned}$$

Ich mag diesen Ansatz, weil er einen noch geringeren Rechenaufwand als der erste erfordert.

Ansatz 3: Orientierung dreier Winkel

Im dritten Ansatz wird der fragliche Punkt jeweils mit den Eckpunkten des Dreiecks verbunden. Die Idee ist, dann der Reihe nach die Orientierung der Winkel zwischen diesen Verbindungen zu vergleichen.

Abbildung 7: Die Winkel AQB, BQC und CQA gehen alle in dieselbe Richtung.
Abbildung 8: Die Winkel APB und BPC gehen in eine andere Richtung als CPA.

Winkel im Uhrzeigersinn erhalten ein negatives Vorzeichen, Winkel gegen den Uhrzeigersinn ein positives Vorzeichen.4 Der fragliche Punkt liegt genau dann innerhalb des Dreiecks, wenn alle Winkel gleich orientiert sind, also das gleiche Vorzeichen haben.

Wie man das Vorzeichen des Winkels ermitteln kann, ohne den Winkel auszurechnen, habe ich im Artikel „Ist der Winkel größer als ein Halbkreis?“ hergeleitet:

$$\begin{aligned} \mathrm{sgn}(\angle APB) &= \mathrm{sgn}((y_B-y_P)(x_A-x_P)-(y_A-y_P)(x_B-x_P)) \\ \mathrm{sgn}(\angle BPC) &= \mathrm{sgn}((y_C-y_P)(x_B-x_P)-(y_B-y_P)(x_C-x_P)) \\ \mathrm{sgn}(\angle CPA) &= \mathrm{sgn}((y_A-y_P)(x_C-x_P)-(y_C-y_P)(x_A-x_P)) \end{aligned}$$

Fällt es Ihnen auf? Die Formeln haben dieselbe Form wie im zweiten Ansatz. Im zweiten Lösungsansatz musste die Formel zwei- oder viermal genutzt werden, hier im dritten Lösungsansatz sind es auch mindestens zwei, aber höchstens drei Rechnungen, bis man Gewissheit über die Position des fraglichen Punktes bezüglich des Dreiecks hat.

Der dritte Ansatz erfordert also noch weniger Rechenaufwand und dafür mag ich ihn. Doch ist das der Weisheit letzter Schluss? Ich vermute, dass es noch kürzere Wege zum Ziel gibt.

Ansatz 4: Ausblick vom Schwerpunkt

Die vierte Idee ist, die Lage des fraglichen Punktes von einem anderen Punkt zu betrachten, der garantiert im Dreieck liegt – dafür bietet sich der Schwerpunkt des Dreiecks an.

Abbildung 9: Von S aus gesehen liegt Q zwischen A und B, und die Punkte S und Q liegen auf derselben Seite der Geraden durch A und B.
Abbildung 10: Von S aus gesehen liegt P zwischen C und A, und die Punkte S und P liegen auf unterschiedlichen Seiten der Geraden durch C und A.

Genauer gesagt soll geprüft werden, ob S und der fragliche Punkt auf derselben Seite jener Kante der Dreiecks liegen, in deren Richtung der fragliche Punkt von S aus gesehen liegt. Die Berechnung ist etwas aufwendiger als die vorhergehenden Ansätze, hat aber auch einen interessanten Vorteil …

Um zu prüfen, in Richtung welcher Kante des Dreiecks der fragliche Punkt vom Schwerpunkt gesehen liegt, ist es nützlich, alle Punkte zunächst so zu verschieben, dass der Schwerpunkt auf dem Ursprung zu liegen kommt. Der Schwerpunkt S besitzt die Koordinaten $\left(\frac{x_A+x_B+x_C}{3};\frac{y_A+y_B+y_C}{3}\right)$.5 Nach dem Verschieben ergeben sich folgende Punkte:

$$\begin{aligned} A' &= (x_A-x_S;y_A-y_S) \\ B' &= (x_B-x_S;y_B-y_S) \\ C' &= (x_C-x_S;y_C-y_S) \\ P' &= (x_P-x_S;y_P-y_S) \\ S' &= (0;0) \end{aligned}$$

Im nächsten Schritt werden die Koordinaten der verschobenen Punkte A', B', C', P' jeweils in eine Funktion foo(x,y) eingespeist. Die Funktion könnte den Winkel zwischen der positiven x-Achse und der Strecke vom Ursprung zum eingespeisten Punkt zurückgeben. Berechnen kann man diesen Winkel beispielsweise so:6

$$\mathrm{foo}_1(x,y)=\arccos\left(\frac{x}{\sqrt{x^2+y^2}}\right)\times\begin{cases} \phantom{+}1 &\mathrm{falls}\quad y\geq 0 \\ -1 &\mathrm{falls}\quad y<0 \end{cases}$$

Tatsächlich interessiert nur, dass die Funktionswerte für die Koordinaten der Punkte genauso der Größe nach geordnet sind, wie sich die Reihenfolge der Punkte vom Schwerpunkt aus betrachtet darstellt. Die Berechnung der Winkel leistet das, aber auch einfacher zu berechnende Funktionen besitzen diese Eigenschaft. So könnte ohne Arkuskosinus und Wurzel auch diese Funktion genutzt werden:

$$\mathrm{foo}_2(x,y)=\left(1-\frac{x}{|x|+|y|}\right)\times\begin{cases} \phantom{+}1 &\mathrm{falls}\quad y\geq 0 \\ -1 &\mathrm{falls}\quad y<0 \end{cases}$$

Aus A', B', C' sucht man den Punkt mit dem größten Funktionswert heraus, der kleiner als jener von P' ist, sowie den Punkt mit dem kleinsten Funktionswert, der größer als jener von P' ist oder ihm gleicht.7 Falls es keinen Punkt gibt, der einen kleineren Funktionswert als P' hat, ist stattdessen der Punkt mit dem größten zu wählen. Falls es keinen Punkt gibt, der einen im Vergleich zu P' größeren oder identischen Funktionswert hat, ist stattdessen der Punkt mit dem kleinsten zu wählen.

Angenommen, entsprechend der Abbildung 10 fällt die Auswahl auf die Punkte C' und A', dann wird für die Gerade durch C und A getestet, ob S und P auf derselben Seite liegen. Das erfolgt wie im zweiten Ansatz so, dass die Vorzeichen zweier Ausdrücke ausgerechnet werden:

$$\begin{aligned} \mathrm{sgn}(\mathrm{Se}_{C,A}(x_P,y_P)) &= \mathrm{sgn}((y_P-y_C)(x_A-x_C)-(y_A-y_C)(x_P-x_C)) \\ \mathrm{sgn}(\mathrm{Se}_{C,A}(x_S,y_S)) &= \mathrm{sgn}((y_S-y_C)(x_A-x_C)-(y_A-y_C)(x_S-x_C)) \end{aligned}$$

Bei identischen Vorzeichen liegt der fragliche Punkt innerhalb des Dreiecks, bei verschiedenen Vorzeichen liegt er außerhalb des Dreiecks.

Schön an diesem Ansatz ist, dass man ihn auch auf konvexe Polygone mit mehr als drei Ecken anwenden kann und der Rechenaufwand dabei nur linear mit der Eckenzahl wächst.8

  1. Es handelt sich um kartesische Koordinaten. Das kartesische Koordinatensystem ist schlicht „unser gebräuchliches“ Koordinatensystem mit x- und y-Achse, die sich rechtwinklig kreuzen. Die erste Zahl in der Klammer ist also der x-Wert, die zweite der y-Wert.
  2. Die gaußsche Flächenformel gilt laut Wikipedia nur für einfache Polygone, also keine überschlagenen. Das macht aber im hiesigen Fall nichts, denn überschlagene Vierecke gibt es hier nur, wenn der fragliche Punkt außerhalb des Dreiecks liegt. Da dann unter den drei Vierecken mindestens ein nicht überschlagenes ist, welches größer als das Dreieck ist, und der Maximalwert der Vierecksflächen gebildet wird, kann trotz der „unerlaubten“ Verwendung der gaußschen Flächenformel auch auf die überschlagenen Vierecke am Ende kein Wert herauskommen, der fälschlicherweise kleiner als die Dreiecksfläche ist.
  3. Das lateinische Wort für Zeichen ist signum.
  4. Sie könnten einwenden, man hätte in Abbildung 8 mit Winkel CPA den Kreis auch in gleicher Richtung wie die anderen Winkel in großem Bogen schließen können. Könnte man – dann würden wir statt über die Orientierung der Winkel darüber reden, ob alle drei Winkel die Eigenschaft teilen, kleiner bzw. größer als ein Halbkreis zu sein, oder ob sie bezüglich dieser Eigenschaft gemischt sind. Letztendlich läuft das aufs Gleiche hinaus.
  5. Wenn S = P, dann liegt P im Dreieck und die Rechnung ist hier schon zu Ende.
  6. Die Berechnung des Winkels zwischen positiver x-Achse und der Strecke vom Ursprung zu einem Punkt ist so wichtig, dass viele Programmiersprachen dafür eine vorgefertigte Funktion anbieten, oft mit diesem Namen und Parametern: atan2(y,x)
  7. Auch wenn anfangs vereinbart wurde, dass keine drei gegebenen Punkte genau auf einer Geraden liegen, können S und zwei weitere Punkte auf einer Geraden liegen, denn S gehört nicht zu den gegebenen Punkten. Darin liegt die Ursache für den Vergleich „größer oder gleich“ statt einfach nur „größer“.
  8. Ein nicht überschlagenes Polygon heißt konvex, wenn alle seine Innenwinkel jeweils kleiner als ein gestreckter Winkel sind. Umgangssprachlich könnte man auch sagen: … wenn das Polygon keine Dellen hat. Ich behaupte, man kann es auch so ausdrücken: … wenn für jedes aus seinen Eckpunkten gebildete Dreieck gilt, dass alle übrigen Eckpunkte außerhalb des Dreiecks liegen.

Kommentare

  1. Sehr erstaunlich, wieviele Gedanken und Überlegungen für eine anfänglich so offensichtlich eindeutig zu beantwortende Frage man sich machen kann ... ich bekomme den Mund gar nicht mehr zu ...
    M.C.

  2. Danke für den Kommentar, M.C.!

    Ich habe auch darüber nachgedacht, ob es nicht verschwendete Zeit sei, sich um so „einfache“ Probleme viele Gedanken zu machen und ob nicht der erste Lösungsweg, der mir in den Sinn kam, genügt hätte. Warum nach weiteren Wegen suchen, wenn man schon einen hat, der zum Ziel führt? Ich denke aber, dass in der Praxis und insbesondere mithilfe der Computertechnik Lösungen komplexer Probleme oft auf den Lösungen vieler einfacherer Teilprobleme beruhen. Beispielsweise kann man aus einer größeren Zahl von Dreiecken ganz verschiedene Figuren zusammenbauen – umgekehrt lassen sich daher viele Fragen zu ganz verschiedenen Figuren einfach lösen, indem man die Figuren in Dreiecke zerteilt und die Fragen dann mit Standardverfahren für jene Teildreiecke beantwortet.

    Wenn solche Standardverfahren vielfach wiederholt angewendet werden, kann es sich lohnen, bei ihrer Entwicklung etwas mehr Zeit zu investieren, um einen möglichst effizienten Lösungsweg zu finden, findet

    Martin

  3. Man nehme den Punkt, benutze ihn zusammen mit je zwei anderen Punkten des Dreiecks um insgesamt drei neue Dreiecke zu formen. Von diesen berechne man die Flächen und summiere deren Beträge(Drehsinn ignorieren!) auf. Ist die Summe gleich der Fläche im Betrag vom Ausgangsdreieck, so liegt der Punkt im Dreieck oder auf einer seiner Kanten. Ist die Summe größer, dann liegt der Punkt außerhalb.

    Nebenbei kann bei einem Wert von null für eine oder mehrere der Fläche ein paar Aussagen über Lage auf den Kanten, den Eckpunkten oder gar Punkt-Identitäten getroffen werden.

  4. Eine clevere Methode, @3. Vielen Dank für den Kommentar!

  5. Wie kann man das auf ein 3dimensionales Koordinatensystem übertragen(XYZ) ? (Den Ansatz mit dem Flächeninhalt/Flächenberechnung)

  6. @5: Beim Übertragen vom 2- aufs 3-dimensionale Koordinatensystem stellt sich die Frage, ob noch immer geschaut werden soll, ob ein Punkt in einem Dreieck (2-Simplex) liegt, oder ob geschaut werden soll, ob der Punkt in einem unregelmäßigen Tetraeder (3-Simplex) liegt.

    Martin

  7. Mit vier Winkeln kann man das Problem auch lösen. z.B.
    1.Winkel von A zwischen C und B
    2.Winkel von A zwischen S und B
    unter Beachtung des Drehsinns ist Winkel 2 kleiner, nun nochmal prüfen:
    3.Winkel von C zwischen A und B
    4.Winkel von C zwischen S und B
    unter Beachtung des Drehsinns ist Winkel 4 kleiner, also im Dreick.
    Mit dieser Methode lassen sich sogar alle Grenzwert (Punkt auf Punkt, Punkt auf Strecke) bestimmen.
    lg voni

  8. Mit Vektortransformation scheint es auch zu funktionieren: Man spannt von A ausgehend einen Vektor jeweils zu B und zu C (AB, AC). Diese dienen als neue Koordinatenvektoren. Irgendwo liegt der Punkt Q, der Vektor von A zu Q heißt AQ.

    Über die Transformation AQ = v*AB + w*AC erhält man für v und w:

    v = (x_AQ*y_AC - y_AQ*x_AC)/(x_AB*y_AC - y_AB*x_AC)
    w = (y_AQ*x_AB - x_AQ*y_AB)/(y_AC*x_AB - x_AC*y_AB)

    Dabei sind x_AQ = x_Q - x_A, y_AQ = y_Q - y_A, ... usw.

    Wenn v und w beide >= 0 sind und gleichzeitig die Summe v + w <= 1 ist, dann liegt Q im Dreieck.

  9. ... noch ein Nachtrag:

    diese Variante funktioniert auch in 3D beim Überprüfen, ob ein Punkt in einem beliebigen Tetraeder liegt. Dazu geht man von der Gleichung AQ = u*AB + v*AC + w*AD aus und schaut nach den gleichen Forderungen:

    1) u,v,w >= 0
    2) u + v + w <= 1

    Betrachtet man ein ebenes Dreieck im Raum, benutzt man obige Gleichung mit einem beliebigen (nicht in der Dreiecksebene liegenden) Punkt D. Nun muss zusätzlich die Bedingung

    3) w = 0

    erfüllt sein.

    LG Michael

  10. Danke schön für Eure Beiträge, voni und Michael!

    Martin