www.mikrocontroller.net

Forum: PC-Programmierung Algorithmus für Test auf "rechts" oder "links" einer Linie


Autor: Bert Hauser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: S. Matlok (smatlok)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 
;-)

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Überleg doch mal was das Vorzeichen von acos(w) aussagt... 
cos(x)=cos(-x) ;)

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Bert Hauser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: I_ H. (i_h)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.