DE102004006686A1 - Verfahren zur Bestimmung einer Krümmung einer durch mehrere Punkte verlaufenden Kurve - Google Patents

Abstract

Die vorliegende Erfindung betrifft ein Verfahren zur Bestimmung einer Krümmung einer durch mehrere Punkte verlaufenden Kurve, deren Verlauf sich als Verbindungslinie der Punkte ergibt, wobei den einzelnen Punkten eine Krümmung zugeordnet wird durch eine Bestimmung der Lage benachbarter Punkte relativ zu den jeweiligen Punkten, wobei die Krümmung eines Punktes (B) bestimmt wird unter weiterer Berücksichtigung von zwei weiteren Punkten (A, C), von denen einer (A) auf der Verbindungslinie vor dem jeweiligen Punkt (B) liegt und ein weiterer Punkt (C) auf der Verbindungslinie hinter dem jeweiligen Punkt (B) liegt, wobei die Punkte (A, C) derart bestimmt werden, dass diese möglichst weit weg von dem jeweiligen Punkt (B) liegen, wobei gleichzeitig keine Punkte vorhanden sind, die zwischen dem jeweiligen Punkt (B) und einem der beiden weiteren Punkte (A, C) liegen, die von den Verbindungslinien zwischen dem jeweiligen Punkt (B) und jedem der beiden weiteren Punkte (A, C) einen Abstand oberhalb eines Schwellwertes aufweisen.

Description

• Die Erfindung betrifft ein Verfahren zur Bestimmung einer Krümmung einer durch mehrere Punkte verlaufenden Kurve nach dem Oberbegriff des Patentanspruchs 1.
• Es ist bereits ein derartiges Verfahren bekannt, bei dem mehrere Punkte paarweise durch Verbindungslinien miteinander verbunden werden ( DE 196 04 364 A1 ). Es werden dann Krümmungen der sich ergebenden Trajektorie bestimmt, indem ermittelt wird, welche Punkte zu in der DE 196 04 364 A1 so bezeichneten elementaren Kurven gehören. Zu diesen elementaren Kurven werden dann die Krümmungsradien ermittelt.
• Der vorliegenden Erfindung liegt die Aufgabe zu Grunde, ein Verfahren vorzuschlagen, zur Beschreibung eines Weges hinsichtlich der Krümmungen.
• Das Verfahren soll insbesondere zur Beschreibung von Wegen in digitalisierten Karten Verwendung finden.
• Die Aufgabe wird nach der vorliegenden Erfindung gelöst, indem die Krümmung eines Punktes (B) bestimmt wird unter weiterer Berücksichtigung von zwei weiteren Punkten (A, C), von denen einer (A) auf der Verbindungslinie vor dem jeweiligen Punkt (B) liegt und ein weiterer Punkt (C) auf der Verbindungslinie hinter dem jeweiligen Punkt (B) liegt, wobei die Punkte (A, C) derart bestimmt werden, dass diese möglichst weit weg von dem jeweiligen Punkt (B) liegen, wobei gleichzeitig keine Punkte vorhanden sind, die zwischen dem jeweiligen Punkt (B) und einem der beiden weiteren Punkte (A, C) liegen, die von den Verbindungslinien zwischen dem jeweiligen Punkt (B) und jedem der beiden weiteren Punkte (A, C) einen Abstand oberhalb eines Schwellwertes aufweisen.
• Es hat sich gezeigt, dass diese Auswahl von drei Punkten, an Hand derer der Krümmungsradius im Punkt B bestimmt wird, vorteilhaft dazu führt, dass eine geeignete Punktauswahl insbesondere bei geringen Krümmungen (d. h. großen Krümmungsradien) erreicht werden kann. Indem die Punkte möglichst weit auseinander liegen, können numerische Probleme weitgehend vermieden werden. Neben eventuellen numerischen Problemen können auch Probleme dahin gehend vermieden werden, dass Ungenauigkeiten in der Lage der Punkte bei dicht beieinander liegenden Punkten insbesondere bei geringen Krümmungen zu Ungenauigkeiten bei der Bestimmung der Krümmung führen können. Indem neben dem Abstand der Punkte weiterhin der Schwellwert berücksichtigt wird, können Ungenauigkeiten in der Lage einzelner Punkte ausgeglichen werden. Liegen die Punkte außerhalb des durch den Schwellwert definierten Bandes, kann davon ausgegangen werden, dass es sich nicht mehr um eine Ungenauigkeit in der Definition der Lage des entsprechenden Punktes handelt sondern um eine Lage des Punktes entsprechend einem Verlauf der Straße.
• Mit dem vorliegenden Verfahren kann also jedem Punkt eine Krümmung zugeordnet werden. Den Punkten am Anfang und am Ende eines Bandes kann als Wert der Krümmung der entsprechende Wert des Nachbarpunktes zugewiesen werden. Der Wert der Krümmung dieser beiden Punkte kann auch auf "0" gesetzt werden.
• Bei der Ausgestaltung des Verfahrens nach Anspruch 2 werden für die Berechnung der Krümmung nur solche Punkte (A, B, C) verwendet, die einen Mindestabstand voneinander aufweisen.
• Bei der Ausgestaltung nach Anspruch 2 erfolgt eine Krümmungsberechnung nur dann, wenn die Punkte einen hinreichenden Abstand voneinander aufweisen. Werden also hinsichtlich der Verlässlichkeit der Aussage der Berechnung Probleme erwartet, unterbleibt eine Berechnung der Krümmung an dem entsprechenden Punkt vollständig.
• Bei der Ausgestaltung des Verfahrens nach Anspruch 3 wird die Krümmung im Punkt B entsprechend dem Radius des Kreises bestimmt wird, der durch die Punkte A, B und C geht.
• Dabei wird die Krümmung auf der Grundlage des Radius des Umkreises durch die drei genannten Punkte ermittelt.
• Bei der Ausgestaltung des Verfahrens nach Anspruch 4 wird die Krümmung im Punkt B entsprechend dem Radius des Kreises bestimmt, der durch den Punkt B geht und der weiterhin durch denjenigen der beiden Punkte A und C geht, der einen geringeren Abstand zum Punkt B aufweist, wobei sich der dritte Punkt der Kreislinie ergibt, indem auf der Verbindungslinie zwischen dem Punkt (A, C), der vom Punkt B den größeren Abstand aufweist, und dem Punkt B ausgehend vom Punkt B eine Strecke abgetragen wird, die der Entfernung des Punktes (A, C) entspricht, der den geringeren Abstand zum Punkt B aufweist.
• Bei dieser Vorgehensweise lässt sich unter Ausnutzung der Symmetrien der Kreis einfacher berechnen.
• Bei der Ausgestaltung des Verfahrens nach Anspruch 5 wird die Krümmung im Punkt B entsprechend dem Radius des Kreises bestimmt, der durch denjenigen der beiden Punkte A und C geht, der einen geringeren Abstand zum Punkt B aufweist, wobei sich der dritte Punkt der Kreislinie ergibt, indem auf der Verbindungslinie zwischen dem Punkt (A, C), der vom Punkt B den größeren Abstand aufweist, und dem Punkt B ausgehend vom Punkt B eine Strecke abgetragen wird, die der Entfernung des Punktes (A, C) entspricht, der den geringeren Abstand zum Punkt B aufweist, wobei sich die Lage des Punktes B zur Berechnung des Kreises ergibt, indem der Punkt B entlang der Winkelhalbierenden zu den beiden Punkten A, C verschoben wird von der Verbindungslinie zwischen den Punkten A und C weg, wobei die Verschiebung abhängt vom Abstand des Punktes B zur Verbindungslinie zwischen den Punkten A und C.
• Insbesondere bei größeren Krümmungen erweist es sich hier als vorteilhaft, dass durch diese Vorgehensweise ein homogener Verlauf der Werte entlang der Kurve erzielbar ist.
• Bei der Ausgestaltung nach Anspruch 6 wird weiterhin die Krümmung mittels der unmittelbar zum Punkt B benachbarten Punkte bestimmt, wobei die Krümmung im Punkt B auf den Wert gesetzt wird, der betragsmäßig kleiner ist, sofern die ermittelten Krümmungen das gleich Vorzeichen haben, und wobei die Krümmung im Punkt B auf den nach den vorhergehenden Ansprüchen bestimmten Wert gesetzt wird, sofern die ermittelten Krümmungen unterschiedliche Vorzeichen aufweisen.
• Es hat sich gezeigt, dass mit dieser Vorgehensweise die Aussagekraft verbessert werden kann, wenn der entsprechende Punkt im Scheitelpunkt von vergleichsweise engen Kurven liegt oder auch bei ungenau gesetzten Punkten auf Strecken mit einer geringen Krümmung.
• Mit der vorliegenden Erfindung lassen sich die Krümmungen von Kurven ermitteln, die als zweidimensionale Punktefolgen definiert sind. Mit den Punkten werden als Stützstellen der Verlauf einer Straße bzw. einer Fahrspur einer digitalisierten Karte abgebildet. Alle Punkt sollen innerhalb eines Bandes liegen, bei dem weiterhin die direkten Verbindungslinien zwischen den Punkten innerhalb des Bandes verlaufen sollen.
• Sofern die Zahl der Punkte zur Definition des Weges reduziert werden soll, ist es grundsätzlich auch möglich, ausgehend von dem Verfahren nach Anspruch 1 alle Punkte zu löschen, die zwischen den drei Punkten liegen, auf Grund derer die Krümmung der Bahnkurve an der Stelle des in der Mitte dieser drei Punkte liegenden Punktes bestimmt wird. Dadurch kann dann vorteilhaft Speicherplatz gespart werden, wobei der Verlauf der Strecke insbesondere in den Bereich mit größeren Krümmungen nach wie vor noch durch eine hinreichende Zahl von Stützstellen gestützt wird.
• Dabei zeigen:
• 1 eine Darstellung eines Kurvenverlaufs,
• 2 eine Darstellung der geometrischen Größen in dem Dreieck ABC zur Bestimmung des Umkreises
• 3 eine Darstellung zur Verbesserung bei größeren Krümmungen
• 4 eine Darstellung zur Bestimmung eines Kreises
• 5 die Verhältnisse in engen Kurven und
• 6 die Verhältnisse bei ungenau gesetzten Punkten in weiten Kurven.
• 1 zeigt eine Darstellung eines Kurvenverlaufs, bei dem drei Punkte A, B und C bezeichnet sind. Es ist zu sehen, dass der Kurvenverlauf durch weitere Punkte definiert wird, die ebenfalls eingezeichnet sind. Es soll nun die Krümmung der Kurve im Punkt B bestimmt werden. Dazu werden benachbarte Punkte A und C ausgewählt, die für die Berechnung herangezogen werden sollen. Diese Punkte A und C werden nach folgenden Kriterien ausgewählt:
• • Die Nachbarpunkte A und C sollen möglichst weit vom Punkt B entfernt liegen
• • Zwischen den einzelnen Nachbarpunkten und dem Punkt B darf kein Punkt existieren, der einen maximalen Abstand von der Geraden durch den Punkt B und dem jeweiligen Nachbarpunkt überschreitet Weiterhin kann noch als zusätzliches Kriterium herangezogen werden, dass
• • der Abstand des Nachbarpunktes A, C zum Punkt B einen bestimmten Mindestabstand aufweisen muss Es zeigt sich, dass mit den genannten Kriterien Punkt definiert werden, mit denen der Krümmungsverlauf möglichst glatt nachgebildet werden kann. Eventuelle Ungenauigkeiten in der Definition der Lage der Punkte können weitgehend ausgeglichen werden.
• 2 zeigt die relevanten Größen, mit denen der Krümmungsradius der Kurve im Punkt B bestimmt werden soll.
• Zunächst werden die Abstände der Punkte A und B sowie B und C berechnet: |AB| = √((xB – xA)2 + (yB – yA)2) |BC| = √((xC – xB)2 + (yC – yB)2)
• Weiterhin erfolgt die Berechnung des Winkels β: cos(β) = ((xB – XA)·(xC – xB) + (yB – yA)·(yC – yB))/ (|AB|·|BC|)
• Daraus lässt sich der Sinus-Wert des halben Winkels bestimmen: sin(β/2) = √((1 – cos(β))/2)
• Wegen der einfacheren und damit schnelleren Berechnung der Krümmung kann aus dem Dreieck ABC ein gleichschenkliges Dreieck A1BC1 gebildet werden. Die kürzere der beiden Strecken von B nach A sowie von B nach C wird dabei beginnend am Punkt B auf der längeren der beiden Strecken abgetragen. Die Sehnenlänge 1 = |A1B| = |BC1| des neuen Dreiecks ergibt sich unter Berücksichtigung von h = |BH| <= h_max nach folgender Gleichung: l = min (min(|AB|, |BC|), (hmax/sin(β/2)))
• Der Abstand h = |BH| lässt sich anschließend berechnen: h = l/sin(β/2)
• Weiterhin kann bei einem großen Abstand h davon ausgegangen werden, dass an dieser Stelle der Krümmungsverlauf des abzubildenden Bandes durch die Punktefolge nur ungenau wieder gegeben wird. Diesem Effekt kann dadurch begegnet werden, dass der Punkt B entlang der Winkelhalbierenden zwischen AB und BC verschoben wird, wie dies in 3 dargestellt ist. Der Punkt wird dabei von der Verbindungslinie zwischen den Punkten A1 und C1 weg verschoben.
• Der Abstand zwischen dem original Punkt B und dem neuen Punkt B1 wird nachfolgend unter Verwendung eines konstanten Faktors ermittelt: d = h·faktor
• Für eine glättende Korrektur ist ein Faktorwert zwischen 0 und 1 zu verwenden.
• 4 zeigt ein Beispiel zur Berechnung des Kreises. Durch die Punkte A1, B1, C1 soll ein Kreis gelegt und dessen Radius bestimmt werden. Der Radius des Kreises soll mit dem des Bandes, das mittels der Punktfolge abgebildet ist, möglichst genau überein stimmen. Der Radius kann aus folgenden drei Gleichungen hergeleitet werden: r2 = x2 + y2 l2 = h2 + x2 r + d = y + hmit: r = |MA1| = |MB1| = |MC1| y = |MH| x = |A1H| = |HC1|
• Durch Einsetzen der Gleichungen ergibt sich die nachfolgende Formel zur Berechnung des Radius r des Kreises durch die drei Punkte A1, B1 und C1: r = (l2 + d2 – 2·d·h)/(2·(h – d))
• Durch Substitution von h mit h = 1 * sin(β/2) und auflösen nach sin(β/2) ergibt sich ein maximaler Grenzwinkel für einen definierten minimalen Radius r_min. sin(β/2) = (l2 + d2 + 2·d·rmin)/(2·l·(rmin + d))
• Für Winkel zwischen 0 < sin(β/2) < sin(β/2)_max lässt sich die vorzeichenbehaftete Krümmung kr am Punkt B1 aus nachfolgender Gleichung berechnen: kr = sign((xB – xA)·(yC – yB) – (xC – xB)·(yB – yA))·l/r
• Für alle anderen Winkel ergibt sich die vorzeichenbehaftete Krümmung kr am Punkt B1 zu: kr = sign((xB – xA)·(yC – YB) – (xC – xB)·(yB – yA))·1/rmin
• Dabei gilt:
• • positive Krümmungen entsprechen einer Linkskurve,
• • negative Krümmungen entsprechen einer Rechtskurve.
• 5 zeigt die Verhältnisse in engen Kurven. Daraus lässt sich ableiten, dass neben den aufgestellten Kriterien für die Auswahl der Punkte weiterhin die Krümmung am Punkt unmittelbar aus den Nachbarpunkten berechnet werden kann.
• Dieser Wert wird dann mit dem bisherigen Wert verglichen. Wenn beide Werte gleiches Vorzeichen, wird im weiteren der betragsmäßig kleinere Wert verwendet. Besitzen beide Wert unterschiedlichen Vorzeichen, so wird im weiteren der Wert verwendet, der mit den weiter entfernt liegenden Punkten ermittelt wurde.
• Im dargestellten Beispiel der 5 wird die Krümmung 1kr aus den direkten Nachbarpunkten 1A und 1C sowie dem Punkt B ermittelt. Die Krümmung 2kr wird mit dem beschriebenen Auswahlverfahren für weiter entfernt liegenden Punkte ermittelt. Die Beiden ermittelten Werte der Krümmungen haben das gleiche Vorzeichen. Dem Punkt B wird die Krümmung mit dem betragsmäßig kleineren Wert (1kr) zugewiesen. Es ist zu sehen, dass der berechnete Krümmungswert 2kr für die realen Verhältnisse am Punkt B zu groß wäre.
• 6 zeigt die Verhältnisse bei ungenau gesetzten Punkten in weiten Kurven. Die Krümmung 1kr wird wiederum aus den Nachbarpunkten 1A und 1C ermittelt. Die Krümmung 2kr wird wieder mit dem beschriebenen Verfahren mit den weiter entfernt liegenden Punkten 2A und 2C ermittelt. Beide Krümmungen haben wieder gleiches Vorzeichen, so dass dem Punkt B die Krümmung mit dem kleineren Betrag zugewiesen wird (2kr).
• Mit dem beschriebenen Verfahren zur Beschreibung von Kurven lassen sich Informationsausgaben für den Fahrzeugführer ansteuern. Dazu können relevante Informationen unter weiterer Heranziehung eines Navigationssystems ausgegeben werden, bevor entsprechende Wegpunkte erreicht werden. Weiterhin ist es möglich, mit den beschriebenen Daten direkt in Steuersysteme eines Kraftfahrzeugs einzugreifen. Dies kann beispielsweise eine automatische Geschwindigkeitsvorwahl sein, bei der dann beispielsweise vor Kurven die Sollgeschwindigkeit in geeigneter Weise reduziert werden kann. Ebenso kann damit vorausschauend das Leuchtfeld von Scheinwerfern entsprechend zu durchfahrenden Kurven eingestellt werden.

Claims (6)

1. Verfahren zur Bestimmung einer Krümmung einer durch mehrere Punkte verlaufenden Kurve, deren Verlauf sich als Verbindungslinie der Punkte ergibt, wobei den einzelnen Punkten eine Krümmung zugeordnet wird durch eine Bestimmung der Lage benachbarter Punkte relativ zu den jeweiligen Punkten, dadurch gekennzeichnet, dass die Krümmung eines Punktes (B) bestimmt wird unter weiterer Berücksichtigung von wenigstens zwei weiteren Punkten (A, C), von denen einer (A) auf der Verbindungslinie vor dem jeweiligen Punkt (B) liegt und ein weiterer Punkt (C) auf der Verbindungslinie hinter dem jeweiligen Punkt (B) liegt, wobei die Punkte (A, C) derart bestimmt werden, dass diese möglichst weit weg von dem jeweiligen Punkt (B) liegen, wobei gleichzeitig keine Punkte vorhanden sind, die zwischen dem jeweiligen Punkt (B) und einem der beiden weiteren Punkte (A, C) liegen, die von den Verbindungslinien zwischen dem jeweiligen Punkt (B) und jedem der beiden weiteren Punkte (A, C) einen Abstand oberhalb eines Schwellwertes aufweisen.
2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass für die Berechnung der Krümmung nur solche Punkte (A, B, C) verwendet werden, die einen Mindestabstand voneinander aufweisen.
3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die Krümmung im Punkt B entsprechend dem Radius des Kreises bestimmt wird, der durch die Punkte A, B und C geht.
4. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die Krümmung im Punkt B entsprechend dem Radius des Kreises bestimmt wird, der durch den Punkt B geht und der weiterhin durch denjenigen der beiden Punkte A und C geht, der einen geringeren Abstand zum Punkt B aufweist, wobei sich der dritte Punkt (A1, C1) der Kreislinie (A1, C1) ergibt, indem auf der Verbindungslinie zwischen dem Punkt (A, C), der vom Punkt B den größeren Abstand aufweist, und dem Punkt B ausgehend vom Punkt B eine Strecke abgetragen wird, die der Entfernung des Punktes (A, C) entspricht, der den geringeren Abstand zum Punkt B aufweist.
5. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die Krümmung im Punkt B entsprechend dem Radius des Kreises bestimmt wird, der durch denjenigen der beiden Punkte A und C geht, der einen geringeren Abstand zum Punkt B aufweist, wobei sich der dritte Punkt (A1, C1) der Kreislinie ergibt, indem auf der Verbindungslinie zwischen dem Punkt (A, C), der vom Punkt B den größeren Abstand aufweist, und dem Punkt B ausgehend vom Punkt B eine Strecke abgetragen wird, die der Entfernung des Punktes (A, C) entspricht, der den geringeren Abstand zum Punkt B aufweist, wobei sich die veränderte Lage des Punktes B für die Berechnung des Kreises ergibt, indem der Punkt B entlang der Winkelhalbierenden zu den beiden Punkten A, C verschoben wird (B1) von der Verbindungslinie zwischen den Punkten A und C weg, wobei die Verschiebung abhängt vom Abstand des Punktes B zur Verbindungslinie zwischen den Punkten A und C.
6. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass weiterhin die Krümmung mittels der unmittelbar zum Punkt B benachbarten Punkte bestimmt wird, wobei die Krümmung im Punkt B auf den Wert gesetzt wird, der betragsmäßig kleiner ist, sofern die ermittelten Krümmungen das gleich Vorzeichen haben, und wobei die Krümmung im Punkt B auf den nach den vorhergehenden Ansprüchen bestimmten Wert gesetzt wird, sofern die ermittelten Krümmungen unterschiedliche Vorzeichen aufweisen (1kr, 2kr).