Prüfen, ob sich ein Punkt im Dreieck befindet

...komplette Frage anzeigen

1 Antwort

Ach weißt Du, Varianten von Schreibweisen kann man viele entwickeln. Und wenn Du Deine Gleichungen noch nicht verstehst, hat das Zeigen von Umstellungen auch keinen Zweck. Du solltest daran denken, daß beim Schreiben und Abtippen Flüchtigkeitsfehler passieren (können), die Du natürlich selbst ausbaden können solltest.

Damit man das besser einschätzen kann: Wie weit hast Du denn schon Kenntnisse mit dem Umstellen von linearen Gleichungen? Welche Klassenstufe bist Du?

Was Du da zwischen dem Punkt und dem Seitenvektor berechnest, ist soweit kar?

Ich frage mich auch gerade, warum Du großartig was umstellen willst. Eigentlich gehts um eine stinknormale Vektormultiplikation. Da ist nichts umzustellen...

Ich bin in der 10. Klasse eines Gymnasiums. Ich brauche die Gleichung nach p aufgelöst, um diese Formel dann im einem Programm verwenden zu können. Ich habe bereits überall nach Lösungen gesucht und auch versucht, Sie selber nach p aufzulösen, was mir jedoch nicht gelungen ist.

0
@Blacktaro

Moment, bevor Du weiter sprintest...

Ich würde mit Dir gern nochmal die Vektoren betrachten, die Du da vor der Nase hast...

In der 10. Klasse hattet Ihr doch schon Vektoren. Du weißt also, daß Du die drei Seiten Deines Dreiecks als drei Vektoren darstellen kannst, und zwar so, daß Du einmal um das Dreieck herumläufst. Richtig?

v12 = p1 -> p2
v23 = p2 -> p3
v31 = p3 -> p1

Jeweils mit dx/dy - Wert.

Und Dein Punkt muß, um im Inneren des Dreiecks zu sein, sagen wir: LINKS von allen drei Seiten liegen. (Du kannst/darfst das natürlich auch andersrum machen, das ist Geschmackssache). Ist DIESES Prinzip soweit klar?

0
@WhiteGandalf

Ja, nur mir leuchtet gerade nur nicht ganz ein, wie ich prüfe, ob das der Fall ist.

0
@Blacktaro

Na ja, Du bist aber einverstanden, daß ein Punkt nur JEWEILS LINKS VON den drei Seiten-Vektoren liegen muß, um innerhalb eines Dreiecks zu sein? (Er könnte auch RECHTS von allen dreien sein, das liefe auf dasselbe hinaus...)

Dann kannst Du zustimmen, daß Du letztlich nur ein Vorzeichen prüfen mußt, oder?

================

Hast Du schon das Skalarprodukt von Vektoren behandelt?

Wie Du es berechnest?

Und was für einen Sinn (Bedeutung) das hat?

0
@WhiteGandalf

Nein, das Skalarprodukt habe ich noch nicht behandelt. Soweit ich weiß wird das in NRW erst in Q1 oder Q2 behandelt(11./12.), weil es Bestandteil der analytischen Geometrie ist...

0
@Blacktaro

Hmmm... OK, dann müßten wir das doch mal vorziehen.

Weil dessen Verständnis hier grundlegende Voraussetzung ist. Die Gleichung, die da ursprünglich diskutiert wird, handelt letztlich von nichts anderem. (Ich habe nur den Eindruck, daß es dort ein wenig "komplex" ausgedrückt wurde - wir können das einfacher, nachdem das Verständnis da ist...)

====================

Skalarprodukt zweier Vektoren...

Vektoren als solches waren aber geläufig, oder? Also sowas wie eine Strecke von einem Punkt zu einem anderen in einer Fläche oder im Raum betrachtet, und das auch in seiner Zerlegung in x-/y-/z-Komopnente?

  • Stelle Dir bitte mal bildlich vor, daß Du zwei Bleistifte in der Hand hältst!
  • Lege die vor Dir auf ein Blatt Papier, wo Du ein Koordinatensystem drauf malst! Irgendwie in irgendeine Richtung, so daß die im Koordinatenursprung beginnen und irgendwie in die Landschaft zeigen!

Du darfst übrigens runden und pauschalisieren, was das Zeug hält, es geht nur ums grobe Prinzip...

  • Lege sie dann erstmal parallel!
  • Bestimme (grob gerundet) deren x-y-Komponenten in Deinem Koosys!

Jetzt zur Überleitung zum Skalarprodukt mit Analogiebetrachtung...

  • Du kannst Dich noch grob an den "Pythagoras" erinnern?
  • Daß das Quadrat der Hypothenuse gleich der Summe der Quadrate der Katheten ist?
  • Das KANNST Du auch anders BEZEICHNEN: Das Quadrat der Länge Deines Bleistifts ist gleich der Summe der Quadrate seiner x-y-Komponenten im rechtwinkligen Koosys.

Schau erstmal genau hin, um das zu prüfen und emotional anzuerkennen! Rechne gegebenenfalls mal nach, bis Dein Kopf bereit ist, in der x-y-Zerlegung Deines Bleistifts mit diesem zusammen ein rechtwinkliges Dreieck mit dem Pythagoras-Satz zu erkennen!

Jetzt zum Skalarprodukt:

  • Statt "Quadrat" könntest Du auch davon sprechen, daß Du den Bleistift einfach mit sich selbst multipliziert hast.
  • Und zwar "skalar" mit sich selbst.
  • Was nichts weiter heißt, als daß jede einzelne Komponente des einen Bleistifts mit jeder zugehörigen einzelnen Komponente des anderen Bleistifts multipliziert wird.

Und statt von Bleistiften sprechen wir jetzt einfach wieder von Vektoren...

Wenn wir also zwei Vektoren haben (in der bei Mathematikern üblichen Vektorenschreibweise, die hier flachgelegt wurde, um sie vereinfacht in ASCII gießen zu können):

v1 = (x1,y1)
v2 = (x2,y2)

dann ist deren Skalarprodukt:

s = v1 * v2 = x1 * x2 + y1 * y2

Das ist faktisch nichts anderes als der Pythagoras für zwei in beliebige Richtungen zeigende Vektoren anstatt für einen mit sich selbst multiplizierten (sprich: quadrierten). Ohne die Wurzel zu ziehen. Wer letzteres unbedingt will, darf das auf eigene Faust.

=================

Dieses Skalarprodukt hat eine nette Eigenschaft: Es zeigt auf simpelste Weise unmittelbar an, wie parallel zwei beliebige Vektoren zueinander sind.

Das solltest Du jetzt an einem Beispiel nachrechnen (oder auch an zwei), damit Du das nicht bloß als: "ja ja, der kann ja viel reden... zum einen Ohr rein, zum anderen raus..." aufnimmst, sondern als Aha-Effekt!

  • Du hattest Deine Bleistifte eben noch parallel zu liegen.
  • Deren Skalarprodukt war positiv.
  • Wenn Du es durch das Quadrat der Bleistiftlänge teilst, ist es exakt "1".
  • Lege den zweiten Bleistift jetzt genau entgegengesetzt hin!
  • Bestimme erneut dessen x-y-Zerlegung!
  • Berechne das Skalarprodukt und teile es durch das Quadrat der Bleistiftlänge!

Jetzt solltest Du eine "-1" sehen!

  • Liegen die Bleistifte genau gleichgerichtet parallel, ist deren Skalarprodukt gleich 1 mal das Bleistiftquadrat.
  • Liegen die Bleistifte genau anti-parallel, ist deren Skalarprodukt gleich -1 mal das Bleistiftquadrat.

Jetzt wird's interessant für unsere Dreiecksgeschichte:

  • Lege mal den zweiten Bleistift genau rechtwinklig zum ersten!
  • Berechne das Skalarprodukt und teile es durch das Quadrat der Bleistiftlänge!

Jetzt solltest Du eine Null sehen!

  • Lege mal den zweiten Bleistift andersrum rechtwinklig zum ersten!
  • Berechne das Skalarprodukt und teile es durch das Quadrat der Bleistiftlänge!

Immer noch Null.

Mach nochmal einen Versuch, wo Du den zweiten Bleistift ein wenig in die Richtung des ersten zeigen läßt. Egal, ob links oder rechts vorbei, Hauptsache die Spitze zeigt ein wenig in die gleiche Richtung wie die vom ersten!

Jetzt solltest Du beim berechnen einen Wert größer Null, aber kleiner 1 erhalten. EGAL, wo der zweite Bleistift hinzeigt. Und umso näher an der 1, je paralleler die Bleistifte liegen. Wenn sie sich der exakten Parallelität annähern, nähert sich unser auf Längenquadrat skaliertes Skalarprodukt der Eins an.

Mach wenn nötig (falls das Prinzip noch nicht akzeptiert ist) nochmal Versuche mit den Bleistiften, wenn deren Spitzen in mehr oder weniger entgegengesetzte Richtungen zeigen (von rechtwinklig aus dem anti-parallelen Zustand annähern)! Du solltest merken, daß sich das skalierte Skalarprodukt der Minus Eins annähert...

(Fortsetzung folgt)

1
@WhiteGandalf

Wir sehen:

  • Das Skalarprodukt kann auf simpelste Weise berechnet werden (im D2-Raum alias Fläche einfach eine Summe aus zwei Produkten - gerade für Computer etwas, was die mit Links hinlegen).
  • Es liefert auf simpelste Weise ein Maß für die Parallelität zweier Vektoren, egal wohin die zeigen.

An der Stelle kann man noch eine Reihe von Analogiebetrachtungen ansetzen, um die allgemeine Verwendbarkeit dieser Aussage für beliebige Dimensionen zu begreifen. Aber wir wollen ja zum Dreieck mit dem drin liegenden Punkt kommen...

========================

Was hat die Lage eines Punktes gegenüber einer Strecke alias Dreiecksseite mit Parallelität zu tun?

  • Du könntest geneigt sein, eine Dreiecksseite als Vektor zu sehen:

    s1 = p1 -> p2

  • Du könntest von einem der beiden Vektor-Endpunkte eine Strecke zum zu beurteilenden Punkt ziehen...

    sx = p1 -> px

(Ich nenne den mal "px", OK? Und s1 und sx sind hier Vektoren. Ich kann bloß in ASCII keine Extra-Kennzeichen ranmachen.)

  • Du könntest das skalierte Skalarprodukt aus den beiden bilden.

Beim Multiplizieren zweier unterschiedlich langer Vektoren wird skaliert, indem durch das Produkt der Längen der beiden Vektoren dividiert wird (nichts durch das Quadrat nur eines der beiden).

Damit erhältst Du eine Aussage, wie nahe der Punkt px an der Dreiecksseite liegt.

  • Läge er genau auf der Dreiecksseite, hätte das skalierte Skalarprodukt einen Wert von +1 oder -1.
  • Läge die Strecke zum px genau rechtwinklig zur Dreiecksseite, wäre das Skalarprodukt Null.

Eine exakte und eindeutige Aussage kriegen wir also zur Lage von px IN RICHTUNG der Dreiecksseite, nicht darüber, wie der Punkt seitlich dazu liegt. Insbesondere bekommen wir keine Aussage zum Richtungssinn der seitlichen Lage (links oder rechts vorbei?)!

==================

Das läßt sich ändern: Drehen wir die Dreiecksseite um einen rechten Winkel - sagen wir: NACH LINKS!

s1' = Linksdrehung(s1)

Schon haben wir die Möglichkeit, ein Skalarprodukt zu bilden, welches uns die seitliche Abweichung unseres px MIT RICHTUNGSSINN beurteilt:

Liegt sx links von s1', ist das Skalarprodukt positiv.
Liegt sx rechts von s1', ist das Skalarprodukt negativ.

Je nachdem, wie Du Dein Dreieck umrundest, bedeutet das nichts anderes, als daß der Punkt px entweder auf der Seite von p1-p2 liegt, auf der sich die Dreiecksfläche aufspannt, oder aber entgegengesetzt. Mit anderen Worten: Entweder hat er das Potential, im Dreieck zu liegen, oder nicht.

Im Dreieck liegt der Punkt px, wenn er gegenüber allen drei Dreiecksseiten in gleicher Richtung (links davon oder rechts davon) liegt. Welches von diesen beiden ist Wurst, weil sich das automatisch aus dem konkreten Fall ergibt: Das einzige, worauf Du testen brauchts, ist die Gleichheit der Vorzeichen der Skalarprodukte.

Womit außerdem klar ist, daß Du die Sache noch vereinfachen darfst, denn Du benötigst eine Skalierung auf Längenprodukte nicht mehr. Nur das Vorzeichen.

==================

Bliebe noch zu klären, wie man einen Vektor um 90° nach links oder rechts dreht...

Das kannst Du Dir ganz einfach mit einem Bleistift klarmachen:

  • Lege den irgendwie ins Koosys (aufs Blatt Papier)!
  • Nimm jetzt einzeln jede der beiden Komponenten x und y dieses Vektors!
  • Drehe jede der beiden einzeln um 90° nach links!

Das sollte extrem einfach und offensichtlich sein:

  • Die ehemalige x-Komponente zeigt jetzt nach y.
  • Die ehemalige y-Komponente zeigt jetzt nach x, aber ins negative!

Das kannst Du auch formal schreiben als:

Linksdrehung(x,y) = (-y,x)

=================

Die fertige Formel ergibt sich jetzt aus der ganz stupiden Aneinanderreihung der drei Skalarprodukte und dem Vergleich der drei resultierenden Werte auf gleiche Vorzeichen.

  • Ich würde empfehlen, das Skalarprodukt in eine Funktion auszulagern.
  • Es zwingt Dich niemand, mit Vetoren (als Arrays oder so) zu arbeiten. Wenn es besser gefällt oder einfache ist, nimm getrennte einzelne Komponenten wie in der ursprünglich verlinkten Diskussion.

Zum Schluß könnte es ähnlich aussehen wie:

s1 = skalar(x2-x1,y2-y1,x-x1,y-y1);
s2 = skalar(x3-x2,y3-y2,x-x2,y-y2);
s3 = skalar(x1-x3,y1-y3,x-x3,y-y3);

if (s1 > 0 && s2 > 0 && s3 > 0 || s1 < 0 && s2 < 0 && s3 < 0)
{
    // Punkt im Dreieck
}
else
{
    // Punkt nicht im Dreieck
}

Ich hoffe, jetzt ist das eigentliche Anliegen der Diskussion im ursprünglich verlinkten Diskussionsforum einigermaßen klar geworden. Die haben sich dort nur etwas "kompliziert" herangetastet statt die Sache erstmal aus einem abstrakten Standpunkt zu betrachten und das Prinzip hinter den Formeln zu verstehen...

1
@WhiteGandalf

Man KÖNNTE die Formel natürlich auch noch zu einem monolithisch Block zusammenpfriemeln. Aber das ist eher sinnfrei: Das Skalarprodukt als solches brauchst Du massenhaft, wenn Du Mathematik mit Vektoren machst. Es ist die Grundoperation in der Matrizenrechnung. Grundprinzip in der Reduzierung (Lösung) von Gleichungssystemen. Grundoperation in Transformationen wie Fouriertransformation.

Und als Dreizeiler ist die Sache extrem einfach zu verstehen.

Und mir ist noch ein Flüchtigkeitsfehler reingerutscht: In dem letzten Codeschnipsel hatte ich die Drehung der Dreiecksseiten übersehen. Aber da Du jetzt weißt, wie das geht, kannst Du das selbst ganz schnell nachlegen!

1

Was möchtest Du wissen?