Gegeben:

(X, Y) -Koordinate, die die Position eines Fahrzeugs ist.Array von (X, Y), die Eckpunkte in einer Polylinie sind. Beachten Sie, dass die Polylinie nur aus geraden Segmenten und keinen Bögen besteht.

Was ich möchte:

Um zu berechnen, ob sich das Fahrzeug links oder rechts von der Polylinie befindet (oder natürlich oben).

Mein Ansatz:

Durchlaufen Sie alle Liniensegmente und berechnen Sie den Abstand zu jedem Segment. Dann machen Sie für das nächstgelegene Segment einen einfachen Linkstest (wie erklärt)Hier zum Beispiel).

Mögliche Probleme:

Wenn drei Punkte einen Winkel bilden, der kleiner als 90 Grad ist (wie in der Abbildung gezeigt), entsteht ein komplizierteres Szenario. Befindet sich das Fahrzeug wie unten gezeigt im roten Segment, kann das nächstgelegene Segment eines der beiden sein. Dieübrig von Test wird ergebenRecht wenn das erste Segment als nächstgelegenes Segment ausgewählt wird, undlinks Andernfalls. Wir können leicht sehen (zumindest hoffe ich), dass das richtige Ergebnis sein sollte, dass das Fahrzeug istlinks der Polylinie.

Meine Frage:

Wie kann ichelegant, aber meistenseffizient sich um diese spezielle Situation kümmern?

Mein Fix bisher:

Berechnen Sie für beide Segmente einen Punkt auf diesem Segment, beginnend mit dem Scheitelpunkt.Berechnen Sie die Entfernung vom Fahrzeug zu beiden Punkten unter Verwendung der euklidischen EntfernungBehalten Sie das Segment bei, für das der berechnete Punkt am nächsten liegt.

Ich bin mit diesem Fix nicht sehr zufrieden, da ich das Gefühl habe, dass mir eine weitaus elegantere Lösung fehlt. Mein Fix fühlt sich eher "hackig" an. Effizienz ist jedoch der Schlüssel, da sie in einem eingebetteten Echtzeitsystem verwendet wird.

Die vorhandene Codebasis befindet sich in C ++. Wenn Sie also in einer bestimmten Sprache schreiben möchten, hat C ++ meine Präferenz. Vielen Dank!

[bearbeiten] ich habe mich verändertMein Fixvon einem senkrechten Punkt zu einem parallelen Punkt, da es meiner Meinung nach einfacher ist, dem Liniensegment zu folgen, als die äußere Normalen zu berechnen.