0

Hallo,

Im Rahmen einer Programmieraufgabe wurde mir folgende Formel vorgegeben:

DFV(A,B,C)=Ax*(By-Cy)+Bx*(Cy-Ay)+Cx*(Ay-By)

Wenn A,B,C Punkte in 2d sind (heißt jeder Punkt ht nur x und y komponente) und eine gerichtete Gerade von A Richtung B verläuft,

dann gilt:

ist obiger Wert >0, so liegt C links der Geraden.

ist der Wert <0, ist er rechts davon.

Man solle sich das Ganze so vorstellen , dass man auf dem Punkt A ist und guckt Richtung B.

Diesbezüglich ist dann C links oder rechts der Gerade.

Obige Formel kann auch als Determinante der Matrix ((Ax,Bx,Cx)^T, (Ay,By,Cy)^T, (1,1,1)^T))

geschrieben werden (ist ja dasselbe wie oben der Term).

 

Mich würde nun echt gerne der mathematische Hintergrund des Ganzen interessieren, wie man auf die Formel kommt.

Leider wurde das Ganz nur so vorgeben (es geht ja ums Programmieren unter Nutzung der Formeln, nicht um Mathe).

Ich hätte, wenn ich jetzt mal laienhaft das prüfen wollte, den Winkel zwischen den Vektoren AB und AC mittels Skalarproduktgleichung bestimmt.

Je nahc Vorzeichen des Winkels wäre C links oder rechts.

 

Aber da hier in dieser Formel der WInkel nicht mal vorkommt, muss hier irgendwie anders gerechnet worden sein,

ich weiß nur nicht wie.

Laut weiterem Fließtext beschreibe das irgendwie eine "Dreiecksfläche mit Vorzeichen" oder so, aber ich durchblicke es nicht.

 

Ist vermutlich was ganz einfaches.

Kann sich vielleicht Jemand von euch vorstellen, was hier gemahct wird und warum es geht? :-/

 

 

EDIT vom 24.04.2022 um 10:06:

Edit: Hier auf Seite 14 ist die Stelle zu finden wo ich die Formel her habe:

https://silo.tips/download/mathematik-und-informatik-5

EDIT vom 24.04.2022 um 10:38:

Edit2: Nach langem Googeln stieß ich auf diese Seite:

https://de.serlo.org/mathe/2021/fl%C3%A4cheninhalt-eines-dreiecks-im-koordinatensystem

 

Wenn man mal die unterschiedliche Notation ignoriert (Ax heißt dort xa und Ähnliches) und unten auf der Seite sich die letzten 2 Ausdrücke anguckt, dann gibt die Determinante der MAtrix dort gerade unsere Formel wenn man es ausmultipliziert und etwas zusammenfasst.

halt nur ohne den Vorfaktor 1/2 und das komische FE, was auch immer das heißen soll.

Aber die Richtung ist schon mal die Richtige.

Frage nun nur noch wo das herkommt und woher man weiß welches Determinantenvorzeichen für links oder rechts der Gerade steht.

 

Diese Frage melden
gefragt

Student, Punkte: 271

 
Kommentar schreiben
1 Antwort
0
Links oder rechts heißt ja in 2d schlicht drüber oder drunter. Das geht mit Schulmathematik:
Geradengleichung durch die Punkte A und B aufstellen, also $f(x)=....$. Dann prüfen, ob $f(Cx)>Cy$ oder $f(Cx)<Cy$. Im Fall = liegt C auf der Geraden.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 24.03K

 

Hm, laut Google ist
y=(By-Ay)/(Bx-Ax)*x+(Bx*Ay-AxBy)/(Bx-Ax)

Es müsste also:
Cy>(By-Ay)/(Bx-Ax)*Cx+(Bx*Ay-AxBy)/(Bx-Ax) sein.
entsprechend < für unterhalb.

Macht Sinn.
Nur gehts bei meinem Fall ja um eine gerichtete Gerade, heißt wenn ich bspw. A=(1,1) und B=(-1,-1),zeigt die Richtung der Geraden nach unten links und demnach würde
nun
"oberhalb"->rchts der Geraden bzw.
"unterhalb"->links der Geraden bedeuten.

irgendwas muss da noch fehlen um auf die eingängliche Formel zu kommen...
  ─   densch 24.04.2022 um 10:00

Eine Gerade hat keine Richtung und die Ungleichungen gelten ja trotzdem.   ─   cauchy 24.04.2022 um 10:51

In meinem Fall HAT die Gerade eine Richtung und ich will wissen ob der Punkt links oder rechts davon liegt.
Ist nötig zum Bauen des Konturpolygons
  ─   densch 24.04.2022 um 11:49

Wenn es eine Richtung hat, ist es keine Gerade. Dann geht es Dir um Vektoren.
Die obige Ungleichung gilt für die Richtung vom kleineren x-Wert zum größeren. Wenn die Richtung andersrum ist, muss die Ungleichung eben andersrum gelesen werden. Wenn man das Programmieren will, kann man das mit Multiplikation mit sgn(Ax-Bx) erledigen.
Den Sonderfall, dass beide x-Werte identisch sind, muss man noch getrennt behandeln.
  ─   mikn 24.04.2022 um 12:11

Vermutlich läuft es adarauf raus, welcher Vektor rotationsmässig linsk vom Anderen ist.
Wobei logisch betrachtet die VektorenAB und AC und ihre "Ausrichtung§ entsprechend ein gegensätzliches Vorzeichen als die Vektoren -AB und AC haben müssen.
Nur welche Formel die jetzt afür benutzt haben zur Herleitung, weiß ich nicht. Vielleicht sollte ich doch mal den Professor direkt befragen
  ─   densch 28.04.2022 um 01:55

Ich weiß nicht, warum Du auf einer anderen Lösung beharrst.
Die Geradengleichung durch $A$ und $B$ lautet:
$y=f(x)=\frac{By-Ay}{Bx-Ax}(x-Ax) + Ay $ (Schulmathematik, ohne google).
Dann haben wir die Fälle:
1. $Ax\lt Bx$: Dann $Cy>f(Cx) \iff C$ links von der gerichteten Geraden. Multipliziere beiden Seiten mit $Bx-Ax$ und erhalte $DFV>0$.
2. $Ax>Bx$: Dann $Cy\lt f(Cx) \iff C$ links von der gerichteten Geraden. Multipliziere beiden Seiten mit $Bx-Ax$ und erhalte $DFV>0$.
Beide Fälle liefern also $DFV>0$ für "$C$ liegt links davon" (und andersrum), weil sich im 2. Fall das Ungleichungszeichen umdreht, was es ja auch soll.
Der 3. Fall $Ax=Bx$ geht nicht mit dieser Schulmathe-Geradengleichung, den kann man zu Fuß prüfen.
Fazit: Alle 3 Fälle führen ohne Vektorrechnung, Winkel, Rotationen auf die von Dir vorgegebene Bedingung mit dem DFV.
  ─   mikn 28.04.2022 um 13:45

Gute Frage, vermutlich bin ich nicht ganz mitgekommen :-D

Mit deiner Geradengleichung oben hätte ich die Fälle wie folgt konstruiert:
links: das ist der Fall wenn (Cx-Ax)*(Cy-f(Cx))>0
da entweder bildlich gesehen C links von A liegt und unterhalb der geraden ist(in dem Fall sind beide Terme negativ, das Produkt aber wieder positiv)
oder C rechts von A liegt und oberhalb der Geraden liegt.

Für rechts entsprechend die 2 anderen Fälle, wo das Produkt dann negativ ist.

Multipliziert man das Produkt aus und sortiert nach den y Werten, kommt gerade die DFV raus.

Man kann es ganz umständlich auch über Vektoren versuchen:
betrachten wir den Fall dass C links von A, B links von A auf der Geradne liegt (gerade halt nahc links zeigt) und unter der Geraden liegt.
Dann können wir von A aus ein Stück weit entlang der Geraden nach links gehen,
bis wir an einem Punkt P dann senkrecht nach unten gehen.

Den Vektor von A nach P kann man shcreiben als k*n, wobei n der normiete EInheitsvektor nahc links ist (n=AB/|AB|)
Also AP=k/|AB|*AB, mit einem bestimmten unbekannten k aus R.
Den senkrechten Vektor von P nahc C kann man naheliegenderweise schreiben als (0,dy), wobei dy<0 wenn C unter der Geraden und >0 wenn oberhalb.

Damit ergibt sich
AC=AP+PC
(Cx-Ax,Cy-Ay)=k/|AB|*(Bx-Ax,By-Ay)+(0,dy)

Die beiden Komponentengleichungen ausgeschrieben also:
Cx-Ax=k/|AB|*(Bx-Ax)
Cy-Ay=k/|AB|*(By-Ay)+dy

Also ein LGS mit 2 Unbekannten k und dy und 2 Gleichungen, wobei wir eigentlich nur dy brauchen am Ende.
Umstellen nach k/|AB| der ersten Gleichung und einsetzen in die 2. Gleichung liefert:
Cy-Ay=(Cx-Ax)/(Bx-Ax) *(By-Ay)+dy
Also dy=(Cy-Ay)-(Cx-Ax)/(Bx-Ax) *(By-Ay)

Nun analog zur ersten berehcnung muss nun für "links" gelten:
(Bx-Ax)*dy>0
Bx-Ax gibt an ob nahc links oder rechts zeigend und dy eben den senkrechten, mit Vorzeichen behafteten Abstand zur Geraden.
Wenn man nun in Kleinarbeit das Ausmultiplizieren würde, käme man vermutlich auf die selbe Formel für DFV :-)
  ─   densch 02.05.2022 um 14:59

"....links: das ist der Fall wenn (Cx-Ax)*(Cy-f(Cx))>0": Das verstehe ich nicht, Tippfehler? So führt es auch nicht auf DFV... .Mit "(Bx-Ax)*(Cy-f(Cx))>0" würde es passen, fasst meine beiden Fälle oben zusammen. Der Fall Ax=Bx müsste noch getrennt betrachtet werden.
Zu Deiner Herleitung: Es lässt sich etwas straffen, wenn Du die Normierung weglässt. Der Vektor von A nach P ist immer k*n, egal ob n normiert ist oder nicht. Beim Lösen des LGSs fällt ja auch k*|AB| wieder raus.
  ─   mikn 02.05.2022 um 15:31

Klar, das war ein Tippfehler.
(Bx-Ax) zeigt ja gerade an ob die Gerade nahc links oder rechts zeigt.

Klar, k ist ja nur ein Faktor.
Wollte halt ordentlich erst mal den Vektor normieren und dann wieder auf die passende Länge "strecken".
  ─   densch 04.05.2022 um 11:34

Wenn alles geklärt ist, bitte als beantwortet abhaken (grüner Haken), damit wir den Überblick behalten. Kann man auch noch nachträglich für frühere Fragen machen ;-)   ─   mikn 04.05.2022 um 12:22

Kommentar schreiben