Hallo, in welchem Kapitel meiner alten Schulbücher oder mit welchen Stichwörtern befrage ich Google wenn ich einen Algorithmus suche, mit dem ich in der Ebene festellen kann, ob ich eine Linie überquere? Die Linie ist hinterlegt als zwei Koordinatenpaare für Anfang und Ende und kann beliebig in der Ebene liegen. Dann habe ich jeweils zwei Punkte und ich muß wissen, ob die Punkte auf "verschiedenen Seiten" der Linie liegen. Danke für Tipps Bert
Bring die Linie auf eine Darstellung der Form f:x->y und berechne für deine jeweilige x-Koordinate die zugeh. y Koordinate der Linie. Dann vergleiche das mit deinem Punkt. Hast du 2 Punkte px1:py1 und px2:py2 gegeben wär das zB. f(x)=(x-px1)*(py2-py1)/(px2-px1)+py1. Ist dein Testpunkt etwa tx:ty so berechnest du f(tx)>ty, kommt da wahr raus bist du auf der einen Seite, sonst auf der anderen (oder auf der Linie).
hm, das funktioniert aber auch nur wenn die line "von link nach rechts" geht, sonst hast du schon den ersten sonderfall. Desweiteren hast du probleme wenn der vektor "senkrecht" im koordinatensystem steht, dann versuch diesen mal automatisch in die form f:x->y zu bringen.. Ich würde ganz einfach den Winkel zwischen den zwei vektoren testen, ob er größer oder kleiner 0 ist, das funktioniert ohne sonderfälle und in alle richtungen der x-y ebene. vektor 1: starkpunkt - endpunkt der linie vektor 2: startpunkt - zu testender punkt für die google suche: "winkel zwischen vektoren" oder mathe grundkurs ;-)
Abl.: Falls die Linie in der Form [(x1,y1)-(x2,y2)] gegeben ist, dann setze (dx,dy) := (x2-x1,y2-y1), (sx,sy) := (-dy,dx) (oder alternativ (sx,sy) := (dy,-dx)). (su,sv) ist damit eine Senkrechte. Zu einem zu testenden Punkt (px,py) setzt du nun (hx,hy) := (px-x1,py-y1) und bildest das innere Produkt p := hx*sx+hy*sy. Je nach relativer Lage zur Linie erhälst du dann p=0 für Punkt auf Linie, p>0 fur Punkt über Linie und p<0 für Punkt unter Linie. Bem: (sx,sy) := (-dy,dx) definiert eine Orientierung bzgl. der Linie. Damit erhälst du eine kompakte Formel: p := (px-x1)*(y1-y2) + (py-y1)*(x2-x1) p = 0 : Punkt auf Linie p < 0 : Punkt unter Linie p > 0 : Punkt über Linie (p := (px-x1)*(y2-y1) + (py-y1)*(x1-x2) liefert das umgekehrte Ergebnis bzgl. Orientierung) Gruss Jörg
Dann berechne mal den Winkel... aber bitte nicht den Cosinus davon, der nutzt dir nämlich garnix ;). Der Sinus zwar schon, aber da musst du schon ein bissel was tun. Zum letztendlichen Rechnen ist meine Methode schon die einfachste, eine Multiplikation, 2 Subtraktionen und ein Vergleich auf >< 0. Allgemein geht am besten indem man die Normale auf die Linie ausrechnet und das innere Produkt mit einem Vektor von der Seite zum Punkt berechnet. Mit den Bezeichnungen von oben ist eine Normale auf die Linie (py2-py1):-(px2-px1) =: n. <n, p> (Inneres Produkt) wenn p auf der Linie gibt nun einen konstanten Wert, den braucht man (zB. <n, p1> =: d mit p1:=px1:py1). Nun bekommt man die Position ggü. der Linie über <n, p>-d, wobei sich die 3 Fälle >0 -> auf der einen Seite, =0 -> auf der Linie, und <0 -> auf der anderen Seite unterscheiden lassen. Wählt man p1 und p2 zur Berechnung der Normalen sinnvoll (zB. px1 stets < px2, wenn nicht möglich py1 stets < py2) sind die Fälle immer identisch, zB. >0 => Punkt liegt oben/links der Linie. Die Methode lässt sich auf nD erweitern, man kann damit errechnen auf welcher Seite einer Hyperfläche (n-1 D) man in nD liegt. Die Berechnung der Normalen wird aber komplizierter.
@Jörg Einfacher rechnet es sich, wenn man die absoluten Koordinaten vom Punkt nimmt, und einmal einen Punkt der Linie einsetzt. So wird aus der Vektorsubtraktion eine skalare, außerdem braucht man keinen Aufpunkt mehr. In 2D macht das kaum einen Unterschied, bei mehr Dimensionen (zb. 5..10) macht das dann schon mal 30% Unterschied.
Hast recht, mein Ansatz ist ja noch nicht optimiert. Nimmt man wie du ja angedeutet hast die Hesse-Form, so erspart man sich die relativen Koordinaten (bzgl. Linie); setze (sx,sy) := (y1-y2,x2-x1) als Senkrechte (muss nur einmal für mehrere Tests berechnet werden) und das innere Produkt d := <(x1,y1),(sx,sy)> = x1*sx + y1*sy, so erhält man für einen Punkt (px,py) e := <(px,py),(sx,sy)> = px*sx + py*sy e = d : Punkt auf Linie e > d : Punkt über Linie e < d : Punkt unter Linie Die >,=,< Tests muss du auch bei der Winkelberechnung machen, ist also der gleiche Aufwand; meistens muss aber nur festgestellt werden, ob ein Punkt unter oder über einer Linie (inkl Linienpunkte) ist, also nur einen Test machen. Die Winkelberechnung (z.B. per atan etc.) ist zwar kompakter im Code aber wesentlich rechenaufwendiger. Gruss Jörg
Na es geht auch "direkt" - so wie im inneren Produkt der Cosinus vom Winkel enthalten ist, ist im äußeren Produkt der Sinus enthalten, der hilft einem sogar weiter. Aber das äußere Produkt ist halt schon Rechenaufwand.
Der Winkel ergibt sich ja aus der Schwarz'schen Ungleichung |(px-x1,py-y1)*(x2-x1,y2-y1)| <= |(px-x1,py-y1)| * |(x2-x1,x1-y1)| (mit |(x,y)| := sqrt(x^2+y^2) als Eulernorm. Damit ergibt sich ja mit H := (px-x1,py-y1)*(x2-x1,y2-y1)/(|(px-x1,py-y1)|*|(x2-x1,x1-y1)|) -1 <= H <= 1 und somit mit cos(w) := H w = acos(H). Da beim nichtnormierten Hesse-Verfahren keine normierten Vektoren auftreten, haben die Ausdrücke d,e in meinen Formeln nur entfernt was mit dem Winkel zu tun, den Winkel zu berechnen (oder den Cosinus von w) muss mindenstens die Wurzel berechnet werden (zweimal sogar). Da sich aber die Vorzeichen für den Vegleich d<>=e aber dadurch nicht ändern, ist das auch nicht erforderlich. Gruss Jörg
http://de.wikipedia.org/wiki/Kreuzprodukt Guck mal unter "andere wichtige Eigenschaften" - da taucht der Sinus vom Winkel auf. Mit dem geht's auch ohne Normale. Damit braucht man nicht mehr die 90° gedrehte Normale, sondern kann direkt mit einem Vektor entlang der Geraden arbeiten, da der Sinus ungerade und nicht gerade symmetrisch ist.
Das der Cosinus (als periodische Funktion) ja nicht vollständig bijektiv ist, ist schon klar und das die Inverse acos nur von 0..pi abbildet auch (siehe z.B. www.wikipedia.de). Aus der Schwarzchen Definition des Winkels ist damit auch klar, dass das Vorzeichen die Orientierung bzw. Lage des Punkts zur Linie liefert. Aber wie gesagt, zum Cosinus sind zwei Normalisierungen erforderlich, die aber zur Entscheidung nicht benötigt werden. Will man den Test also unbnedingt auf einen Vorzeichentest reduzieren, hilft es, f := e-d in meiner obigen Gleichung zu setzen. Gruss jörg
Nein, das geht eben nicht mit dem Cosinus. Egal ob der Winkel +10° oder -10° beträgt, das Vorzeichen bleibt gleich. Das gibt dir nur Auskunft, ob du in -90°..90° oder 90..180 bzw. -90..-180 liegst. Daher brauchst du die Normale, dann hast du den eingeschlossenen Winkel+90° und dann passt das auch wieder mit dem Vorzeichen vom Cosinus, also das wechselt genau dann, wenn du von der einen Seite auf die andere wechselst. Wenn du dagegen das äußere Produkt bildest, bekommst du den Sinus vom Winkel (zwischen Gerade und Gerade von Punkt auf Gerade und Testpunkt). Und über dessen Vorzeichen kannst du problemlos aussagen, ob das nun in -180..0° oder 0..180° liegt, also auf der einen oder auf der anderen Seite liegt. Da brauchst du keine 90° Drehung über die Normale.
Sorry, kleines Missverständnis: nicht das Vorzeichen vom cos(w), sondern das Vorzeichen von acos(w), war mein Fehler. Wenn du zwei Vektoren normierst (z.B. (dx,dy),(sx,sy) => (ndx,ndy),(nsx,nsy)), dann erhälst du ja acos(w) = <(ndx,ndy),(nsx,nsy)> (inneres Produkt). Das Vorzeichen erklärt sich ja auch aus der Vektortheorie im Hilberraum L2 (R2 mit innerem Produkt impliziert aus der Eulernorm). Der Richtungsvektor (dx,dy) und die Senkrechte (sx,sy) bilden zusammen einen Vektorraum. Das innere Produkt mit (ndx,ndy) bzw. (nsx,nsy) liefert ja gerade die Koordinaten u bzw. v bzgl. der von der Linie definierten System, v ist hier die Koordinate bzgl. der Normalen (nsx,nsy). Das Vorzeichen entscheidet also, ob der Punkt bzgl. des neuen Koordinatensystems über/auf/unter der neuen X-Achse (d.h. der Linie) ist. Gruss Jörg
Überleg doch mal was das Vorzeichen von acos(w) aussagt... cos(x)=cos(-x) ;)
Sorry, mein Fehler: nicht das Vorzeichen des acos(e) nehmen, sondern testen, ob <,=,> PI/2 gilt (bzgl. Normale). Nimm man einen Punkt Senkrecht über p1 (z.B. p := p1 + N), so erhält man als inneres Produkt mit N für p <p-p1,N>= 1; für p := p1 - N erhält man -1, für p := p1 +/- (dx,dy) erhält man 0. Es gilt: acos(1) = 0.0, acos(-1) = PI und acos(0) = PI/2 (0: p-p1 steht senkrecht zu N). Also muss einfach auf >,=,< PI/2 getestet werden. Für die relative Lagebestimmung ist das Ganze aber irrelavant, da ja nur das Vorzeichen von acos(w) bzw. asin(w) betrachtet wird. Bei acos(w) hast du den (gerichteten) Winkel zwischen Gerade und Punkt-P1, bei asin(w) den Winkel zwischen Normale und Punkt-P1. Da der Winkel bzw. acos(e) bzw. asin(e) nur als implizite Symbole auftauchen -- du verwendest ja nur h := u*v/|u|/|v| -- und vergleichst h mit 0 auf >,=,<; da spielt der Ansatz, welchen Winkel du wo ansetzt keine Rolle. Z.B. ergibt p1+N für h = 1, p1-N für h = -1 und p1+(dx,dy) = 0, d.h. wieder eine einfache Vorzeichenprüfung. In physikalischen (2D/3D) Simulationen (z.B. einfache Kollisionstests) wird idR immer der Hesse-Ansatz ohne Normalisierung verwendet. Im 3D muss allerding das Kreuzprodukt berechnet werden, d.h. 6 Mult's und 3 Add's extra. Gruss Jörg
Klar, im Endeffekt ist's egal. Was halt nur nicht funktioniert, ist den Winkel zwischen Gerade und Testpunkt-Geradenpunkt über das innere Produkt auszurechnen, weil einem der Cosinus in dem Fall nicht wirklich hilft. Ich hab den ganzen Spaß schon bei Volumenberechnungen in 5D benutzt (Größenordnung 1k..10k Punkte und Seiten, die auch errechnet werden müssen), dabei ist es dann wichtig den Test ob innerhalb/außerhalb so schnell wie möglich zu machen, ein bisschen Vorberechnung mit O(1) pro Seite stört da nicht. Inzwischen wird das Volumen aber schon nicht mehr punktweise ermittelt, sondern linienweise.
Hallo, danke für Eure zahlreichen Beiträge. Aber nachdem ich inzwischen über Google fündig geworden bin, merke ich, daß man sich im Zeitalter moderner PCs wohl keine Gedanken über effiziente Lösungen macht / machen muß. Ich hatte vergessen zu erwähnen, daß der Code dann auch auf einen AVR soll. Hab eine Lösung namens "Streckenschnitt" auf der Basis der Bestimmung der Determinanten gefunden. ls2-www.cs.uni-dortmund.de/lehre/winter200304/dap2ergseminar/vortr/algge o.ppt Ohne aufwändige Trigonometrie, nur ein paar Multiplikationen und mit konstantem Aufwand: O(1) Trotzdem Danke Bert Hauser
Das hängt alles davon ab, wieoft du das machen willst/musst. Bei 10k Punkten in 5D kommen locker 20k Seiten raus, wenn du dann das Volumen auf vll 16 Bits genau haben willst, dauert das schon bis zu einer Minute. Die Algorithmen oben sind schon die einfachsten, Determinante klingt gruselig, läuft wahrscheinlich auf das äußere Produkt hinaus.
Die Determinantenformel ist im Prinzip die Hesseformel: nimmt man für einen Punkt p die Matrix (p-p1,p2-p1) = ((px-p1x,py-p1y),(p2x-p2x,p2y-p1y)) so erhält man die Determinante D = (px-p1x)*(p2y-p1y)-(py-p1y)*(p2x-p2x) und durch Umstellung die oben genannte Formel nach Hesse. Die Matrix enthält ja nichts anderes als den Richtungsvektor (vorgegeben durch die Linie) und den Vektor p-p1 (von Linienanfang zum Punkt). Beide Vektoren spannen einen R2 auf, das Vorzeichen definiert dann die Orientierung (=0: Vektoren fallen zusammen, >0: System positiv definit, p über Linie, <0: negativ definit, p unter Linie). Für den Ansatzt gibt's mindestens sechs verschiedene Bezeichnungen, durch einfaches Umstellen kriegt man aber immer wieder die selbe kompakte Formel. Einfacher geht's nur mit Trickserei z.B. wie oben von S. Matlok angedeutet durch Vorsortierung der Linienpunkte. Gruss Jörg
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.