www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Überschreitung einer Linie AVR - GPS


Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich bräuchte ein paar Lösungsideen, irgendwie weiß ich nicht wirklich, 
wie man es umrechnet.

Es werden 2 GPS Koordinaten festgelegt, die die Endpunkte einer Linie 
bilden sollen. Am AVR hängt ein GPS Sensor, der NMEA Daten liefert. Nun 
soll die Überschreitung dieser imaginären Linie festgestellt werden.

Wie geht man da am besten vor?

Danke!

Autor: Mmmh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ist Dir klar wie das Problem in der ebenen Geometrie gelöst wird?
Genauso geht es in der sphärischen.

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja in der Ebene ist mir das klar. Ich würde einfach versuchen einen 
Schnittpunkt zu berechnen. Existiert dieser, dann schneiden sich die 
Geraden.

Aber wie mache ich es mit den GPS Koordinaten?

Autor: Mmmh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
GPS schrieb:
> Aber wie mache ich es mit den GPS Koordinaten?

Schreibe bitte mal was Dein spezifisches Problem ist. GPS-Koordinaten 
sind einfach sphärische Koordinaten (mit der Einschränkung, das sowas 
wie WGS oder ähnliches noch reingerechnet wurde).

Als Einstiegspunkt mal hier lesen: 
http://de.wikipedia.org/wiki/Sph%C3%A4rische_Geome...

Dann kannst Du vielleicht Dein Problem genauer beschreiben.

> Ich würde einfach versuchen einen
> Schnittpunkt zu berechnen.
Genauso machst Du es auf der Kugel. Den Schnittpunkt zweier Grosskreise 
berechnen.

Autor: Mmmh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mmmh schrieb:
> enauso machst Du es auf der Kugel. Den Schnittpunkt zweier Grosskreise
> berechnen.

Wobei zu beachten ist, das es zwei Schnittpunkte gibt.

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also ich finde gar keinen Ansatzpunkt.
Eine Möglichkeit wäre doch die Koordinaten in 2D umzurechnen, oder?

Dann der Schnittpunkt der Geraden:
Da sehe ich das Problem, dass ja eigentlih schon ein Schnittpunkt 
gefunden wird, wenn ich zwei Messungen VOR der eigentlichen Linie habe - 
die Gerade durch die zwei Punkte hat ja auch einen Schnittpunkt mit der 
"Ziellinie", allerdings soll nur ausgelöst werden, wenn diese Linie 
überquert wurde.

Autor: Uwe ... (uwegw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie sind denn überhaupt die Rahmenbedingungen für die Aufgabe? Bei 
kleinem Abstand zwischen den Punkten könnte es vielleicht reichen, die 
Welt als Scheibe mit rechtwinkligem Koordinatensystem zu betrachten...

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Punkte der "Ziellinie" befinden sich ca 30-40 Meter auseinander. Das 
wäre jetzt auch mein Ansatz gewesen, alles "flach" zu betrachten. Aber 
wie stellt man eine Überquerung fest?

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei 30-40m ist die Erdkrümmung so gering, das sollte ohne Kugelgeometrie 
gehen.

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie projeziert man die Koordinaten in eine Ebene? Ich habe irgendwas im 
Kopf, dass man in Bogenmaß umrechnen muss, dann den cos von Nord und sin 
von Ost?

Autor: Mmmh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Meister, das ist doch nun wirklich nur ein Problem des Nachschlagens. 
Schau mal zuhause in Deinen Bronstein oder im Internet nach. Ich bin 
einfach zu faul dazu für Dich zu arbeiten.
Wenn Du mit dem Verfahren dann ein spezielles Problem hast, kannst Du 
gerne wieder hier fragen.

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Umrechnung ist nicht so das Problem, sondern die Idee, wie man eine 
Überschreitung feststellt.

Ich glaube alleine mit dem Schittpunkt kann man ja nicht arbeiten:
Da sehe ich das Problem, dass ja eigentlich schon ein Schnittpunkt
gefunden wird, wenn ich zwei Messungen VOR der eigentlichen Linie habe -
die Gerade durch die zwei Punkte hat ja auch einen Schnittpunkt mit der
"Ziellinie", allerdings soll nur ausgelöst werden, wenn diese Linie
überquert wurde.

Autor: Mmmh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nun, Du musst halt feststellen ob der aktuelle Standpunkt von dem 
ursprünglichen aus, diesseits oder jenseits der Verbindungslinie (der 
Ziellinie) liegt. Das macht man im Prinzip genauso wie in der Ebene.

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Die Punkte der "Ziellinie" befinden sich ca 30-40 Meter auseinander.

Bei dem kleinen Abstand wird das nix mit GPS.

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
holger schrieb:
> Bei dem kleinen Abstand wird das nix mit GPS.

Das ist doch Quatsch. Oder hat dein Sensor eine Ungenauigkeit von +-20 
Metern?

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ GPS
>> Bei dem kleinen Abstand wird das nix mit GPS.

>Das ist doch Quatsch. Oder hat dein Sensor eine Ungenauigkeit von +-20
>Metern?

Hast du schon mal eine Langzeitaufzeichnung mit GPS gemacht?
Du wirst dich wundern wie weit auch neuere GPS noch abweichen können.

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Meine Aufzeichnungen laufen in der Regel 20 Minuten. Der Sensor ist mit 
einer Genauigkeit von 2.5 Metern angegeben.

Bei längeren Testfahrten habe ich auch keine derartigen Probleme 
festgestellt.

Autor: Gast? (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mach das doch mit zwei Linien: Eine von Punk A nach Punkt B, die zweite 
von Punkt A zum aktuellen Standort.

Wenn du dich bewegst, hast du irgendwann einen anderen Winkel zwischen 
den zwei Linien. Liegen die Linien fast aufeinander (Winkel z.B. <1°), 
stehst du auf der Linie oder bist kurz davor/dahinter.
Bei der möglichen Abweichung von GPS brauchst du auch nicht genauer zu 
rechnen.

Autor: spess53 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

>Der Sensor ist mit einer Genauigkeit von 2.5 Metern angegeben.

Vergiss es. Nimm mal z.B. Visual GPS, schliess deinen Empfänger an und 
lass ihn mal am selben Ort.

MfG Spess

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gast:
Die Idee ist gut, funktioniert aber nicht, wenn man im Kreis fahren will 
;)

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, Lösungsidee, erstmal selber versuchen das umzusetzen:
Du hast zwei Punkte A und B, die definieren deine "Grenzlinie".

Du hast zwei Punkte X1 und X2, die Position des GPS-Empfängers JETZT und 
von vor 1 Sekunde (10 sekunden, 1 Minute, ... nach Lust und Laune), 
diese definieren deine "Bewegungslinie".

Wenn sich diese beiden Linien schneiden: Grenze überschritten.

Wie stellt man fest, ob sich zwei Strecken schneiden (= Einen 
gemeinsamen Punkt enthalten)? => Geometrie 5. Klasse. Wikipedia. Oder 
mal scharf nachdenken.

Autor: Hagis (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

Ich hätte da folgende Idee, ohne Schnittpunkt (den es ja eigentlich 
nicht braucht):

Die Punkte A und B seien gegeben. Die Gerade durch die Punkte ist deine 
feste Linie. Der Punkt P ist ein Messpunkt vom GPS.

Die Geraden AB und AP haben eine gewisse Steigung m bzw. n. t sei die 
Differenz der Beträge der beiden Steigungen.

Also etwa so:
m = |(A_y - B_y) / (A_x - B_x)|
n = |(A_y - P_y) / (A_x - P_x)|
t = m - n

Wenn t von der einen Messung zur nächsten das Vorzeichen wechselt, wurde 
in dieser Zeit die Linie überschritten. Im Fall t=0 sollte man noch eine 
Messung machen.

Wenn du das Ganze noch etwas umformst, sollte es sogar ohne die Division 
zu programmieren sein (du brauchst nur das Vorzeichen => Vergleiche).

Nur so grob im Kopf skizziert...

Gruss Hagis

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das klingt gut, ich werde mir das mal skizzieren. Danke!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hagis schrieb:

> Die Geraden AB und AP haben eine gewisse Steigung m bzw. n. t sei die
> Differenz der Beträge der beiden Steigungen.


nicht!

In der Geometrie ist die Geradengleichung
   y = m * x + d

praktisch nicht zu gebrauchen!

Den Schnittpunkt 2-er Geraden rechnet mit mit diesem Ansatz

 gegeben 2 Gerade A und B mit den Endpunkten
      PA1, PA2
 bzw. PB1, PB2

Für jeden Punkt PA auf der Geraden A gibt es ein tA, sodass gilt
    PA = PA1 + tA * dA            ( wobei dA = PA2 - PA1 )

Genauso gilt für jeden Punkt PB auf der Geraden B ein tB, sodass
    PB = PB1 + tB * dB            ( wobei dB = PB2 - PB1 )

Gibt es einen Schnittpunkt der beiden Geraden, nennen wir ihn PS,
dann muss dieser Punkt logischerweise auf Gerade A liegen
    PS = PA1 + tAs * dA     (I)

und er muss auch auf Geraden B liegen
    PS = PB1 + tBs * dB     (II)

Da es sich aber in beiden Fällen um denselben Punkt handelt, muss 
klarerweise gelten
    PA1 + tAs * dA  =  PB1 + tBs * dB

Dies ist eine Vektorgleichung, da ja jeder Punkt dir x und y beschrieben 
ist. Also haben wir da in Wirklichkeit 2 Gleichungen
    PA1x + tAs * ( PA2x - PA1x )  =  PB1x + tBs * ( PB2x - PB1x )
    PA1y + tAs * ( PA2y - PA1y )  =  PB1y + tBs * ( PB2y - PB1y )

Das sind 2 Gleichungen in 2 Unbekannten (tAs und tBs) und das lässt sich 
lösen. Heraus kommt eine Lösungsformel, die den ganzen Zirkus den du bei 
Anwenden der linearen Gleichung y = k*x+d nicht hast. Bei dir ist 
nämlich das Problem, dass die Steigung k bei Geraden, die nahezu 
senkrecht stehen über alle Grenzen wächst und im Grenzwert 90° unendlich 
wird. All das hast du mit dem t-Ansatz nicht. Die Lösungsformel ergibt 
einen Bruch. Und wie immer bei Brüchen muss man darauf achten, dass 
nicht durch 0 dividiert wird. In diesem Fall hat aber eine versuchte 
DIvision durch 0 auch eine geometrische Sonderrolle: In diesem Fall sind 
die Geraden parallel und es existiert kein Schnittpunkt. Aber abgesehen 
von diesem Parallel-Sonderfall gibt es keinen anderen Sonderfall, der 
einem das Leben schwer machen könnte. Die Geraden können liegen wie sie 
wollen.


Und im übrigen muss man gar keinen Schnittpunkt berechnen.
Es genügt völlig, wenn man berechnet, auf welcher Seite der Geraden ein 
bestimmter Punkt liegt. Das Überschreiten der Geraden wird dann dadurch 
angezeigt, dass der nächste Testpunkt, auf der anderen Seite der Geraden 
liegt.
Wie bestimmt man, auf welcher Seite einer Geraden ein Punkt liegt?
Ganz einfach: (keine Sorge, die Mathe dahinter fägnt jetzt erst mal 
kompliziert an, aber sie vereinfacht sich zum Schluss hin extrem, bis 
eine ganz einfache Formel übrig bleibt)

Man geht vom 2D ins 3D.
Gegeben sind dann 2 Vektoren in einer Ebene. Der eine wird gebildet von 
der Geraden, gegeben durch 2 Punkte PA1 und PA2. Der andere wird 
gebildet von dem Testpunkt P und einem der beiden Endpunkte der Linie, 
nehmen wir einfach mal PA1.
  V1:    ( PA2x - PA1x ; PA2y - PA1y ; 0.0 )
  V2:    ( Px - PA1x   ; Py - PA1y   ; 0.0 )

(Zur Erinnerung: Wir sind vom 2D ins 3D gegangen und die beiden Vektoren 
liegen in der x/y Ebene. Daher sind die z-Komponenten der Vektoren 
jeweils 0.

Nun kann man im 3D mit 2 Vektoren ein Koordinatensystem aufspannen. Die 
z-Komponente des Koordinatensystems erhält man, indem man das 
Kreuzprodukt der beiden Vektoren bildet. Und auf diese z-Komponente sind 
wir aus: Sie muss logischerweise senkrecht auf die x/y stehen. Aber: je 
nachdem wie die beiden Vektoren zueinander orientiert sind, zeigt der 
z-Vektor (von aussen betrachtet) einmal in die x/y Eben hinein und 
einmal heraus. Und genau das ist unser Kriterium, auf welcher Seite der 
Geraden sich der Punkt befindet.

Wir rechnen also
       V1x              V2x
       V1y     kreuz    V2y
       0.0              0.0

und das ergibt
       V1y * 0.0 - 0.0 * V2y    = Rx
       0.0 * V2x - V1x * 0.0    = Ry
       V1x * V2y - V1y * V2x    = Rz

die x bzw. y Komponente des Z-Vektors müssen 0 sein (weil ja der 
Z-Vektor senkrecht auf die x/y Ebene steht) und genau das ist im 
Ergebnis auch der Fall. Sowohl Rx als auch Ry sind jeweils 0.

Für uns ist nur das Vorzeichen von Rz interessant. Ist es positiv so 
befindet sich der Testpunkt auf der einen Seite der Geraden, ist es 
negativ, so ist der Testpunkt auf der anderen Seite. Ist Rz 0, dann 
liegt der Testpunkt exakt auf der Geraden PA2 - PA1

Um also zu bestimmen, auf welcher Seite der Geraden PA1 PA2 ein 
Testpunkt P liegt, berechnen wir
  V1x * V2y - V1y * V2x

wobei V1x = PA2x - PA1x ; V1y = PA2y - PA1y
      V2x = Px - PA1x ; Py - PA1y

in Summe also
   ( PA2x - PA1x ) * ( Py - PA1y ) - ( PA2y - PA1y ) * ( Px - PA1x )

Das Vorzeichen dieses Ausdrucks sagt uns, auf welcher Seite der Geraden 
sich der Punkt befindet.

Nun kann man das alles natürlich auch auf Grosskreise übertragen und 
sich fragen auf welcher Seite einer Ebene sich ein Punkt befindet, wobei 
die Punkte durch die beiden Endpunkte der Geraden und dem Erdmittelpunkt 
gebildet werden. Allerdings ist die Kugel gross genug, dass man den 
Fehler, der durch Projektion auf eine Tangetialebene in der Mitte der 
Geraden gemacht wird, vernachlässigen kann.
-> die GPS Koordinaten in 2D Koordinaten umwandeln. Obige Gleichung 
anwenden und feststellen ob bei 2 aufeinanderfolgenden Punkten sich das 
Vorzeichen des Testausdrucks geändert hat.

Autor: Dieter B. (debe)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich würde zwei Linen ziehen. Eine von Punkt X zu A und eine von X zu B. 
Ist der Winkel dieser beiden Linien zueinander > 180° dann ist man vor 
der Ziellinie bei <180° hinter der Linie.

debe

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dieter B. schrieb:
> Hallo,
>
> ich würde zwei Linen ziehen. Eine von Punkt X zu A und eine von X zu B.
> Ist der Winkel dieser beiden Linien zueinander > 180° dann ist man vor
> der Ziellinie bei <180° hinter der Linie.

So etwas ähnliches macht letztendes mein Vorschlag. Nur brauch ich dazu 
keine Trigonometrie. :-)

Die Endformel berechnet im Grunde nichts anderes als den Sinus des 
Winkels zwischen ( B - A ) und ( X - A )

Autor: GPS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl Heiz:
Danke, ich muss mir das mal in Ruhe zu Gemüte führen

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.