DE69617172T2 - System zum verbinden von elementen mit komplizierten kreuzungen und einmündungen in einer strassennetzdarstellung für fahrzeuge - Google Patents

Description

• Die Erfindung betrifft ein Verfahren zum Speichern geographischer Straßendaten in mehrfachen, hierarchisch organisierten Ebenen durch Ableiten einer abstrahierten Darstellung auf einer zweiten Ebene aus ersten Darstellungen aus einer ersten Ebene, die solche ersten Darstellungen von Straßenverbindungen und Knotenpunkten aufweist, die elementare Straßenverbindungen und elementare Knotenpunkte umfassen. Das US-Patent Nr. 4,914,605 beschreibt die Darstellung einer Straßenkarte zur Anzeige. Verschiedene Straßen in einer solchen Straßenkarte weisen eine Ebenenkennung auf, wobei Schnellstraßen eine höhere Ebenenkennung, Hauptstraßen eine mittlere Ebenenkennung und Nebenstraßen eine niedrigere Ebenenkennung aufweisen. Die Anzahl von Ebenen ist im Prinzip beliebig. Zur visuellen Darstellung ist der Anzeigemaßstab variabel. Bei einem großen Vergrößerungsfaktor wird nur ein kleines geographisches Gebiet mit allen darin befindlichen Straßen angezeigt. Bei einem mittleren Vergrößerungsfaktor wird ein relativ größeres geographisches Gebiet angezeigt, wobei nur Straßen der beiden höheren Ebenen darin gezeigt werden. Bei einem kleinen Vergrößerungsfaktor wird ein relativ noch größeres geographisches Gebiet angezeigt, wobei nur die Straßen der obersten Ebene darin gezeigt werden.
• Die Erfinder der vorliegenden Erfindung haben festgestellt, dass es notwendig ist, nicht nur Straßen, sondern auch komplexe Schnittmuster zwischen Straßen auf vereinfachte Weise so darzustellen, dass eine Entsprechung zwischen verschiedenen Darstellungsebenen garantiert bleibt. Diese Darstellung bedingt nicht notwendigerweise eine visuelle Darstellung, sondern kann auf eine Darstellung in einer Datenbank beschränkt sein. Auf einer abstrahierten Ebene stellt das System dann eine komplexe Kreuzungs-, Schnittpunkt-, Fly-over- oder ähnliche Struktur als einen offensichtlichen Ebenenübergang mit einer entsprechenden Anzahl von Verbindungen dar, wobei jedoch einige Genauigkeit bezüglich der korrekten Geometrie verschiedener Elemente aufgeopfert werden muß. Für eine Anwendung, die ausführliche Entscheidungen erfordert, behält das System weiter die korrekten Bezüge auf die detaillierte Ebene. Zum Beispiel kann die Abstrahierungsoperation eine bestimmte Schleife auf einen einzigen Punkt schrumpfen lassen, so dass der scheinbare Abstand zwischen zwei geographischen Positionen, wenn der Weg dazwischen die Schleife durchlaufen hätte, beeinflußt wird. Tatsächlich führt die Berechnung eines Abstands mit einer exakten Darstellung häufig zu einem größeren Wert als bei der Verwendung des Erscheinungsbilds der abstrahierten Darstellung. Für bestimmte Verwendungszwecke ist die Diskrepanz irrelevant, wie zum Beispiel bei der Fernroutenplanung. Für andere Anwendungen, wie zum Beispiel das Angeben ausführlicher Handlungsanweisungen für einen Fahrer bezüglich des nächsten Schnittpunkts und auch zur Bestimmung der tatsächlichen Position eines Fahrzeugs, ist jedoch nur eine exakte Darstellung der geographischen Daten ausreichend. Im ersten Fall könnte die Erfindung sowohl für Schnellstraßen als auch für Straßen mit einer niedrigeren Klassifizierungsebene Anwendung finden.
KURZE DARSTELLUNG DER ERFINDUNG
• Folglich besteht eine Aufgabe der vorliegenden Erfindung u. a. darin, ein ausfallsicheres Verfahren zum Umsetzen einer Darstellung auf detaillierter Ebene in eine globalere bereitzustellen. Deshalb ist die Erfindung gemäß einem ihrer Gesichtspunkte durch die folgenden Schritte gekennzeichnet:
• a) Verknüpfen einer Menge der elementare Knotenpunkte zu einem komplexen Knotenpunkt auf der Basis vorbestimmter Attribute der elementaren Knotenpunkte der Menge auf einer derartigen ersten Ebene,
• b) Wiederholen des Schritts a), bis alle komplexen Knotenpunkte gefunden wurden,
• c) Festlegen von Randknoten eines ersten komplexen Knotenpunkts und Festlegen aller elementaren Verbindungen zwischen diesen Randknoten und jedem Element eines zweiten komplexen Knotenpunkts als elementare externe Straßenverbindungen, einschließlich aller zulässigen Verkehrsrichtungen auf derartigen elementaren externen Straßenverbindungen, und Ersetzen aller elementaren externen Straßenverbindungen zwischen Randknoten des ersten komplexen Knotenpunkts und jedem Element des zweiten komplexen Knotenpunkts durch eine einzige Ersatzstraßenverbindung, während die zulässigen Verkehrsrichtungen darauf abgebildet werden,
• d) Wiederholen von Schritt c), bis alle Ersatzstraßenverbindungen zwischen zwei beliebigen, auf diese Weise gepaarten komplexen Knotenpunkten festgelegt wurden,
• e) Darstellen jedes verbleibenden elementaren Knotenpunkts und jedes komplexen Knotenpunkts durch einen jeweiligen einzelnen Knoten, während jede verbleibende elementare externe Straßenverbindung und jede Ersatzstraßenverbindung durch eine einzelne Straßenverbindung auf der zweiten Ebene mit zugehörigen originalen beziehungsweise abgebildeten Verkehrsrichtungen dargestellt werden.
• Auf diese Weise wird eine Menge elementarer Knotenpunkte auf einfache Weise zu einer komplexen zusammengestellt, während außerdem die zwei elementare oder komplexe Knotenpunkte verbindenden Straßenverbindungen verbunden werden können, wodurch die erforderliche Speicherkapazität stark vermindert wird. Die Reduktion gespeicherter Daten ermöglicht einen schnelleren Zugriff, was ebenfalls ein Vorteil sein kann. Im obigen ist ein elementarer Knotenpunkt der Verbindungspunkt zwischen elementaren Verbindungen. Diese elementaren Verbindungen werden als das Rückgrat der Organisation der Speicherung beschrieben.
• Ein Randknoten ist ein Knoten, der mit einem elementaren Knotenpunkt außerhalb des in Frage stehenden komplexen Knotenpunkts oder mit einem anderen komplexen Knotenpunkt verbunden ist.
• Vorteilhafterweise umfaßt das Verbinden das Ausführen sukzessiver und in Schleifen ausgeführter Erweiterungsschritte von Eintrittsknotenpunkten zu Nachfolgerknotenpunkten und Austrittsknotenpunkten und rückwärts von allen Austrittsknotenpunkten zu Vorgängerknotenpunkten und Eintrittsknotenpunkten, bis ein endgültiger Schluß der Erweiterung erfaßt wird, wodurch alle bei der Erweiterung gefundenen Knotenpunkte in der zugehörigen Menge enthalten sind. Ein Eintrittsknotenpunkt wird später definiert; allgemein stellt er den ersten Verzweigungspunkt einer Straße bei Annäherung an einen komplexen Knotenpunkt dar. Umgekehrt stellt ein Austrittsknotenpunkt den letzten konvergierenden Punkt beim Verlassen eines komplexen Knotenpunkts dar. Ein Eintrittsknotenpunkt geht Nachfolgerknotenpunkten (oder möglicherweise einem Austrittsknotenpunkt) voraus. Ein Austrittsknotenpunkt folgt Vorgängerknotenpunkten (oder möglicherweise einem Eintrittsknotenpunkt).
• Die Erfindung betrifft außerdem ein Datenverarbeitungssystem zum Verarbeiten und Speichern von Daten gemäß dem Verfahren der Erfindung. Verschiedene weitere vorteilhafte Gesichtspunkte der Erfindung werden in den abhängigen Ansprüchen angeführt. Frühere Arbeiten des Erfinders der vorliegenden Erfindung, einschließlich einer Beschreibung einer Mehrebenendarstellung eines Straßennetzes, wurden publiziert in: Carla Emmerink und Hans Schulte, Route Planning & Route Guidance in the Philips In-Car Navigation System "CARIN", Proc. of the ist world congress on applications of transport telematics and intelligent vehicle highway systems (Paris, FR, ER- TICO Brussels publ.), Band 1, S. 240-248, 1994.
KURZE BESCHREIBUNG DER ZEICHNUNG
• Diese und andere Gesichtspunkte und Vorteile der Erfindung werden ausführlich unter Bezugnahme auf die nachfolgende Offenlegung bevorzugter Ausführungsformen und insbesondere mit Bezug auf die angefügten Figuren besprochen. Es zeigen:
• Fig. 1A, 1B Beispiele für detaillierte bzw. abstrahierte Darstellungen;
• Fig. 2A, 2B ein zweites Beispiel hierfür;
• Fig. 3A, 3B ein drittes Beispiel hierfür;
• Fig. 4 ein schematisches Diagramm der Datenstruktur;
• Fig. 5 ein Diagramm verschiedener elementarer Knotenpunkte;
• Fig. 6 ein Flußdiagramm des erfindungsgemäßen Verfahrens;
• Fig. 7 ein Fahrzeug mit einem Navigationssystem gemäß der Erfindung;
• Tabellen 1-3 verschiedene Aspekte der Datenstrukturorganisation.
ALLGEMEINE BETRACHTUNGEN
• Wie in einem Artikel von M.L.G. Thoone, CARIN, a car information and navigation system, Philips Technical Review, Band 43, Nr. 11/12, Dezember 1987, S. 317-329, beschrieben wird, enthält das CARIN-System ein autonomes Kraftfahrzeug- Navigationssystem, das einen Fahrer unter Verwendung einer auf Compact Disc gespeicherten digitalisierten Karte zu einem Ziel führt. Die Routenplanungsfunktion findet schnell eine optimale Route von einer tatsächlichen Fahrzeugposition zu einem Ziel. Die Betriebsgeschwindigkeit des Systems wird durch die Anzahl von Straßen beschränkt, die untersucht werden müssen, und durch die Abrufgeschwindigkeit von der Compact Disc zu dem Halbleiter-Vordergrundspeicher. Als eine Lösung wird die Karte in mehreren Versionen gespeichert, die alle dasselbe geographische Gebiet abdecken, aber verschiedene Auflösungsgrade aufweisen. Die Versionen basieren auf der Straßenklassifizierung, die durch die funktionelle Bedeutung einer bestimmten Straße bestimmt wird. Deshalb besteht jedes Netzwerk aus einer Teilmenge des nächstniedrigeren hierarchischen Netzwerks, während der Rest unterdrückt wird. Die niedrigste Ebene umfaßt alle Straßen mit einem hohen geometrischen Genauigkeitsgrad. Das Netzwerk auf der höchsten Ebene umfaßt nur die wichtigsten Straßen, aber mit demselben Genauigkeitsgrad, wobei die Genauigkeit von verschiedenen anderen Funktionen als der Routenplanungsfunktion benötigt wird. Deshalb wird automatisch ein globales Netzwerk aus einem detaillierteren erzeugt. Das globale Netzwerk kann in bestimmter Hinsicht, u. a. durch Verallgemeinerung komplexer Knotenpunkte, weniger genau sein. Dies geschieht durch Reduzieren eines komplexen Mehrfach-Knotenpunkts auf einen einzelnen Knotenpunkt. Außerdem werden Straßen, die diese Knoten verbinden und aus zwei Spuren bestehen, die einander entgegengesetzte Richtungen des Verkehrs ermöglichen, durch eine einzige Verbindung ersetzt, die Verkehr in beiden Richtungen zuläßt. Auf diese Weise müssen weniger Daten auf Compact Disc gespeichert werden, während außerdem die Anzahl bei einer bestimmten Aufgabe zu durchsuchender Verbindungen wesentlich geringer ist.
• Zur Verallgemeinerung des Netzwerks wird die folgende Strategie befolgt. Man definiert zunächst die komplexen Knotenpunkte mit Hilfe geographischer Attribute in der digitalen Karte, wie z. B. Straßennamen, Art des Knotenpunkts, physische Form und verkehrstechnische Eigenschaften. Solche Attribute stellen im allgemeinen eine bestimmte Form von Kohärenz zwischen elementaren Knotenpunkten eines komplexen Knotenpunkts dar. Man ersetzt einen komplexen Knotenpunkt durch einen einzelnen Knoten. Als nächstes sucht man die Straßen, die einen bestimmten komplexen Knotenpunkt mit einem anderen bestimmten komplexen Knotenpunkt verbinden. Bei nur einer Straße behält die externe Straßenverbindung ihre Identität. Bei mehr als einer Straße werden sie kollektiv durch eine einzige komplexe externe Straße ersetzt; wenn die ursprünglichen Straßen zusammen Verkehr in beiden Richtungen zulassen, wie zum Beispiel durch zwei Spuren mit entgegengesetzten Richtungen des Verkehrsflusses, ist die komplexe Verbindung für Verkehr in beiden Richtungen offen. Wenn es nicht möglich ist, an dem Knotenpunkt von einer externen Verbindungsstraße zu einer anderen externen Verbindungsstraße abzubiegen, wird eine Abbiegebeschränkung an den komplexen Ersatzknotenpunkt angebunden, die das zugehörige Abbiegen verbietet. Man definiert die Länge der neuen Verbindung durch Addieren der mittleren Länge der ursprünglichen Verbindung und der Größe des den komplexen Knotenpunkt darstellenden Knotens. Als letztes definiert man die Verbindungen mit den anderen Netzwerken an den Knoten der Verbindungen, die zu dem in Frage stehenden komplexen Knotenpunkt führen oder diesen verlassen.
• Nach der Vereinfachung des Netzwerks der niedrigsten Ebene verbleiben viele Informationen, da im allgemeinen nur die wichtigen Straßen komplexe Knotenpunkte entstehen lassen. Diese Straßen stellen nur einen kleinen Teil der Gesamtzahl von Straßen auf der niedrigsten Ebene dar. Falls nun das Netzwerk der niedrigsten Ebene nicht nur von dem Routenplaner sondern auch von anderen Funktionen in dem Fahrzeug, die hohe Genauigkeit benötigen, verwendet wird, werden sowohl die globalisierte Ebene als auch die lokale Ebene des Netzwerks beibehalten.
AUSFÜHRLICHE BESCHREIBUNG VON BEVORZUGTEN AUSFÜHRUNGSFORMEN
• Fig. 1A, 1B sind ein erstes Beispiel für detaillierte bzw. abstrahierte Darstellungen einer sogenannten "Kleeblatt"- Kreuzung zwischen zwei Hauptstraßen. Als erstes wird die detaillierte Darstellung von Fig. 1A betrachtet. Fern von dem tatsächlichen Schnittpunkt bestehen die beiden Straßen für jede Richtung aus Spuren, die einen Wechsel erlauben, und werden durch einzelne Linien dargestellt. Bei Annäherung an den tatsächlichen Schnittpunkt von einem bestimmten Punkt (Eintrittsknotenpunkt), der durch einen Punkt angezeigt wird, muß der Fahrer zwischen Mittelspuren und Seitenspuren wählen, wobei jede Kategorie durch eine getrennte Linie angezeigt wird. Die Seitenspuren ermöglichen ein Abzweigen, die Mittelspuren nicht. Noch näher am Schwerpunkt des tatsächlichen Schnittpunkts kann der Fahrer zunächst zwischen einem Abzweigen nach rechts (zweiter Punkt) und einem Abzweigen nach links (vierter Punkt) wählen. Beide haben ihr Gegenstück für zufließenden Verkehr (fünfter bzw. dritter Punkt, wenn kein Abzweigen bewirkt wird). Als letztes treffen die Seitenspuren wieder die Mittelspuren (sechster Punkt, der einen Austrittsknotenpunkt darstellt).
• Fig. 1B ist die abstrahierte Darstellung derselben Kreuzung. Die Kreuzung an sich wird nun als einzelner Punkt dargestellt. Der Kreuzungspunkt beendet vier als einzelne Linien gezeigte Straßen. Jede der Straßen weist eine Eigenschaft "bidirektional" auf. Die Kreuzung weist eine komplexe Eigenschaft auf, die anzeigt, dass jede Zubringerstraße ein Ausfahren durch jede der anderen drei Straßen ermöglicht. Als weitere Vereinfachung wird der Schnittwinkel der beiden Straßen auf standardmäßige Weise dargestellt, in diesem Fall als ein Schnitt in einem Winkel von 90º. Bei einer anderen Realisierung kann dieser Winkel anders und realitätsgetreuer sein. Eine komplexe Verbindung zwischen Kreuzungen kann als eine gerade Linie oder als eine Folge von mehr als einer geraden Linie dargestellt werden.
• Fig. 2A, 2B sind ein zweites Beispiel für detaillierte bzw. abstrahierte Darstellungen. Tatsächlich ermöglicht dieses Straßenmuster genau dieselben Wahlmöglichkeiten wie Fig. 1A. Das heißt, dass die abstrahierte Darstellung in Fig. 2B mit der von Fig. 1B identisch ist. Die Abfolge des Auswählens ist jedoch verschieden, und detaillierte Anzeigen für einen Fahrer sind folglich von denen in Fig. 1A verschieden.
• Fig. 3A, 3B sind ein drittes Beispiel für detaillierte bzw. abstrahierte Darstellungen eines etwas komplizierteren Schnittmusters. Der Einfachheit halber wurden verschiedene Mehrebenenkreuzungen nur auf elementare Weise gezeigt. Bei flüchtiger Betrachtung wird deutlich, dass Anweisungen häufig gegen die "Intuition des Fahrers" gehen können. Dies gilt insbesondere insofern, als die möglichen Dimensionsunterschiede zwischen solchen komplexen Konfigurationen relativ groß sind, so dass kein standardmäßiges "Bild" im Kopf des Fahrers mit diesen übereinstimmt. Die abstrahierte Darstellung in Fig. 3B gleicht drei sich schneidenden geraden Straßen mit standardisierten Schnittwinkeln. Wiederum weisen alle Straßen sowie die Kreuzung selbst adäquate Eigenschaften auf, die in der Figur nicht gezeigt sind.
• Fig. 4 ist ein schematisches Diagramm der Datenstruktur. Für eine ausführliche Offenlegung dieser wird auf die folgenden eigenen Patentschriften Bezug genommen: EP 302 547, entsprechend dem US-Patent Nr. 4,954,986, EP 306 075, entsprechend dem US-Patent Nr. 4,962,458 und EP 479 364, entsprechend der US-Patentanmeldung Nr. 07/769,613. Das Rückgratelement der Datenstruktur ist die Verbindung (die auch als Kette bezeichnet wird), die zwei Knotenpunkte oder Knoten verbindet. Für jeden der beiden Knoten weist die Verbindung einen Thread-Zeiger auf, der systematisch auf die nächste folgende Verbindung zeigt, die an dem in Frage stehenden Knoten endet. Die Folge von Verbindungen ist durchweg im Uhrzeigersinn. Wenn die Folge die Grenze eines sogenannten Eimers durchlaufen würde, bestünde statt dessen ein Dummy-Thread- Zeiger. Ein Eimer ist eine Dateneinheit mit Standardgröße, die ein geographisches Gebiet beliebiger Größe abdecken kann. Eine entsprechende Referenzierung von Eimer zu Eimer ermöglicht einen schnellen Transfer während einer Suche in der Datenstruktur. Für die genauen Definitionen von Knoten, Verbindung und Thread-Zeiger wird auf die Zitate Bezug genommen. Eine Verbindung oder Kette enthält weiterhin eine Information bezüglich ihrer Klasse, wie zum Beispiel Schnellstraße, Nebenstraße usw., der zulässigen Verkehrsrichtung und ihrer Länge. Weitere optionale Datenelemente sind möglich.
• Nunmehr sind in Fig. 4 drei numerierte Eimer 20, 22, 24 als in eine doppelt verbundene Kette integriert gezeigt. Einzelheiten wurden nur in bezug auf Eimer 22 angegeben. Als erstes weist ein Eimer einen Organisiererteil auf, der eine Kennung des in Frage stehenden Eimers enthält, sich auf alle physisch benachbarten Eimer auf der in Frage kommenden Ebene und außerdem auf die logisch benachbarten Eimer 20, 24 in der Kette bezieht. Die Bezugnahme auf physisch benachbarte Eimer erfolgt durch Zahlen; man beachte, dass die geographische Größe eines Eimers auf jeder einzelnen Ebene und auch zwischen den verschiedenen Ebenen ungleichförmig ist. Die Ausbildung des Eimers wurde als Stand der Technik betrachtet. Somit bezieht sich das Eimerelement 28 zurück auf den Vorgängereimer und wird mit Element 26 gepaart, bei dem es sich um das Bezugsziel des Vorgängereimers handelt, Element 30 bezieht sich vorwärts auf den Nachfolgereimer und wird mit Element 31 gepaart, bei dem es sich um das Bezugsziel des Nachfolgereimers handelt. Der Organisierer enthält einen Bezugsteil auf die Verbindungsstruktur 42-45 und auf die Knotenstruktur 38-41. Wie gezeigt, werden die beiden letzteren Datenstrukturen wiederum durch eine doppelt verbundene Kette gebildet. Jeder Block 42-45 stellt eine Verbindung dar, jeder Block 38-41 stellt einen Knoten dar.
• Wie erwähnt, bezieht sich eine Kette oder Verbindung in der Kettendatenstruktur mittels eines Thread-Zeigers an jedem ihrer Schlußknoten auf höchstens eine andere Kette. Eine Auswahl dieser Bezugnahmen wurde am rechten Rand der Verbindungsdatenstruktur gezeigt. Weiterhin bezieht sich jede Verbindung auf ihre Schlußknoten, die in der Knotendatenstruktur 38-41 gespeichert sind. Eine Auswahl dieser Bezugnahmen wurde durch Pfeile von der Verbindungsdatenstruktur zu der Knotendatenstruktur dargestellt. Schließlich bezieht sich jeder Knoten auf eine einzige Kette, die an dem in Frage stehenden Knoten endet, wobei die Kette auf systematische Weise gewählt wurde. Eine Auswahl dieser Bezugnahmen wurde durch Pfeile von der Knotendatenstruktur zu der Kettendatenstruktur dargestellt. Diese Organisation ermöglicht einen vorteilhaften Kompromiß zwischen minimalen Speicheranforderungen und maximaler Suchgeschwindigkeit. Die Bezugnahmen wurden lediglich als Beispiel gezeigt.
• In diesem Kontext geben die Tabellen 1-3 verschiedene Aspekte der Datenstrukturorganisation an. Tabelle 1 gibt den Datenbankeintrag des Eimers (Bucket) in der bucket list an, die eine Eimerkennung, die Bezugnahmen auf benachbarte Eimer und auf die Knotenliste und die Kettenliste enthält. Tabelle 2 gibt den Datenbankeintrag des Knotens in der node list an, die eine Knotenkennung, die geographischen Koordinaten, eine Bezugnahme auf die benachbarte Kettenliste und Bezugnahmen auf die benachbarten Knoten enthält. Tabelle 3 gibt den Datenbankeintrag der Kette in der chain list an, die ein Gültigkeitsindikator, eine Kettenkennung, Bezugnahmen auf die Schlußknoten, zwei Thread-Zeigerbezugnahmen, die Länge der Kette, eine Bezugnahme auf einen (komplexen) Knotenpunkt, einen Verkehrsrichtungsindikator, einen Straßenklassenindikator, eine Form von Wegindikator, einen Straßennamen, einen Abbiegeeinschränkungsindikator und Bezugnahmen auf die benachbarten Ketten enthält.
• Fig. 5 ist ein Diagramm der verschiedenen elementaren Knotenpunkte. Diese Knotenpunkte wurden auf die in der Offenlegung mit Bezug auf Fig. 6 erläuterte Weise gefunden und jeweils als ein Punkt gezeigt und mit allen elementaren Verbindungen, die die Knotenpunkte verbinden, versehen. Die Geographie wurde lediglich als Beispiel dargestellt. Zehn der elementaren Knotenpunkte wurden zu einer als A bezeichneten Menge verknüpft. Sieben weitere wurden zur Menge B bzw. C verknüpft. Ein einzelner Knotenpunkt D wurde nicht verknüpft. Die Mengen A und B werden durch elementare externe Straßenverbindungen 100, 102 miteinander verbunden, die auf diese Weise jeweils zwei Randknotenpunkte der in Frage kommenden Mengen miteinander verbinden. Bei der Abstrahierung werden die Mengen A, B und C jeweils durch einen einzigen komplexen Knotenpunkt dargestellt. Dabei werden außerdem die elementaren Straßenverbindungen 100, 102 auf eine einzige komplexe externe Straßenverbindung abgebildet, so wie es symbolisch durch die Schleife 108 angezeigt wird. Wie gezeigt, weisen die beiden Verbindungen 100, 102 einander entgegengesetzte Verkehrsrichtungen auf. Das heißt, dass bei der Verknüpfung der komplexe Straßenknotenpunkt eine bidirektionale Verkehrsanzeige erhalten kann. Andererseits können alle elementaren Straßenverbindungen, die ein anderes Paar von Mengen von elementaren Knotenpunkten miteinander verbinden, dieselben Verkehrsrichtungen aufweisen. Das heißt, dass der verknüpfte komplexe Straßenknotenpunkt ebenfalls eine unidirektionale Verkehrsanzeige aufweist. Dieser Fall wurde nicht in der Figur gezeigt. Der Straßenknotenpunkt zwischen der Menge A und dem Knoten D behält seine unidirektionale Verkehrsanzeige bei. Das Beispiel weist hier nur elementare Verbindungen mit einer einzigen Verkehrsrichtung auf. In bestimmten Fällen können jedoch auch bestimmte elementare Straßenverbindungen eine bidirektionale Verkehrsrichtung aufweisen. Dies kann die letztendliche Kennzeichnung der komplexen externen Straßenverbindungen beeinflussen. Eine weitere Verkomplizierung kann darin bestehen, dass bestimmte elementare Straßenverbindungen für bestimmte Verkehrskategorien, wie zum Beispiel für schwere Lastwagen, blockiert sind. Dies kann zu einem Verkehrsrichtungsanzeiger mit drei oder noch mehr Werten führen. Dies kann sich wiederum auf die Kennzeichnung der komplexen externen Straßenverbindungen auswirken. Beide letzteren Situationen wurden in Fig. 5 ignoriert.
• Bei der abstrahierten Darstellung muß nun der Abstand zwischen den komplexen Knotenpunkten reproduziert werden. Die einfachste Lösung besteht darin, die Größe des durch einen komplexen Knotenpunkt abgedeckten Gebiets zu ignorieren. Dies ist zwar rechnerisch wünschenswert, bedingt aber eine zu niedrige Einschätzung von Abständen, manchmal um einen wesentlichen Betrag. Die nächste Ebene der Verbesserung ist die folgende. Als erstes werden die Breite (106) und die Höhe (104) eines komplexen Knotenpunkts als der horizontale bzw. vertikale Abstand zwischen den am weitesten auseinanderliegenden elementaren Knotenpunkten gesucht. Die Datenbank gemäß der obigen Tabelle 2 ermöglicht eine leichte Berechnung dieser. Der Mittelwert dieser wird als der scheinbare Durchmesser des komplexen Knotenpunkts genommen, von dem angenommen wird, dass er ein kreisförmiges Gebiet abdeckt. Eine Hälfte dieses Werts wird zu der Länge aller einzelnen oder komplexen Straßenknotenpunkte auf der nächsthöheren Ebene addiert. Weitere Verbesserungen würden berücksichtigen, dass die Menge elementarer Knotenpunkte ein in etwa elliptisches Gebiet abdecken könnte. Für eine Verbindung zwischen zwei komplexen Knotenpunkten würde die Vergrößerung an beiden Extremitäten der in Frage stehenden Verbindung auftreten.
• Ein weiteres Problem taucht auf, wenn bestimmte Wege zwischen externen Verbindungen zu einem komplexen Knotenpunkt behindert werden, so dass es keinen solchen elementaren Verbindungsweg in der Menge elementarer Knotenpunkte gibt. In diesem Fall wird dies dadurch erkannt, dass kein benutzbarer Weg eine beliebige, mit einer ersten komplexen externen Straßenverbindung zu irgendeiner elementaren Ausgangsstraßenverbindung einer zweiten komplexen externen Straßenverbindung (oder genauso in der anderen Richtung) zu verknüpfende elementare Eingangsstraßenverbindung verbindet. Bei Darstellung des komplexen Knotenpunkts durch einen einzigen Knoten wird für das zugehörige Straßenverbindungspaar der höheren Ebene des zugehörigen komplexen Knotenpunkts eine Behinderungseigenschaft beibehalten. Zum Beispiel gibt es keinen benutzbaren Weg von der Menge B zu dem Knoten D. Bei einer einfachen Version kann dies als "Rechtsabbiegen unmöglich" auf der komplexen Straßenverbindung 108 übersetzt werden. Zu dieser Situation kann es unter bestimmten Umständen auch dann kommen, wenn die Verkehrs-Richtungen auf den externen Verbindungen im Prinzip übereinstimmen würden. Wenn zum Beispiel kein benutzbarer Weg zwischen dem Knoten D und der externen Straßenverbindung 102 vorläge, würde die ankommende Straßenverbindung von Knoten D eine Eigenschaft "Linksabbiegen unmöglich" erhalten.
• Fig. 6 ist ein Flußdiagramm des Verfahrens der Erfindung zum Finden und Abstrahieren eines komplexen Knotenpunkts. Im Block 60 wird das System durch Laden der notwendigen Daten aus der detaillierten Darstellung der niedrigeren Ebene des Netzwerks initialisiert. Im Block 62 wird ein elementarer Knotenpunkt geladen und als sogenannter Eintritts- Knotenpunkt erkannt. Kandidaten kommen in zwei Varianten. Ein erster Typ von Eintrittsknotenpunkt ist eine sogenannte Verzweigung, die eine Verbindung aufweist, die auf den Knoten zukommenden Verkehr zuläßt, und mindestens zwei andere Ketten aufweist, die eine Verkehrsbewegung von dem Knoten weg zulassen. Ein zweiter Typ von Eintrittsknotenpunkt ist ein Elementarknotenpunkt, der mindestens drei Ketten verbindet, die jeweils bidirektionalen Verkehr zulassen; es ist klar, dass die zweite Kategorie von Eintrittsknotenpunkt als eine Unterkategorie der ersten ausgedrückt werden kann. Als eine zusätzliche Bedingung für einen Eintrittsknotenpunkt sollte mindestens eine Kette, die ankommenden Verkehr zuläßt, eine zu dem vorherigen Knotenpunkt gemessene minimale Länge aufweisen, die zum Beispiel im Bereich zwischen 900 und 1200 Meter liegt. Die Einstellung dieses Werts richtet sich nach der Beschaffenheit des Straßennetzes. Bei einem zu großen Wert könnte ein komplexer Knotenpunkt mit zu breiter Spanne resultieren, der die funktionellen Routen maskieren oder sogar ganze komplexe Knotenpunkte unsichtbar machen würde. Bei einem zu kleinen Wert könnte die Verknüpfung insofern unvollständig bleiben, als der Komplex nur auf mehrere komplexe Unterknotenpunkte reduziert werden würde.
• Eine dritte Bedingung für das Finden eines Eintritts besteht darin, dass eine der abgehenden Ketten als "Ausfahrt" markiert werden sollte. Für sich wird der "Ausfahrtknotenpunkt" auf umgekehrte Weise wie der Eintrittsknotenpunkt definiert. Eine erste Ausnahme für die dritte Bedingung besteht nun, wenn eine Schnellstraße direkt mit einer Nicht-Schnellstraße verbunden ist; diese Situation wird jedoch korrekt erkannt, wenn die in Frage stehende Verbindung in dieser bestimmten Kategorie codiert worden ist. Eine zweite Ausnahme dafür besteht, wenn eine elementare Verzweigung auftritt und die Kettenlänge bis zu der nächsten elementaren Verzweigung oder elementaren Verknüpfung von Verbindungen kleiner als ein weiterer Abstand ist, der wiederum abhängig von der Beschaffenheit des Netzes im Bereich zwischen 1800 und 2300 Metern liegen kann. Diese zweite Ausnahme ermöglicht eine Aufnahme von Verzweigungen in die Menge von zu einem komplexen Knotenpunkt gehörenden Knoten. Das Erkennen von Eintrittsknotenpunkten wird fortgesetzt, bis alle Knotenpunkte betrachtet wurden. Das Schleifenverfahren wurde nur auf allgemeine Weise skizziert.
• Wenn nun ein solcher Eintrittsknotenpunkt gefunden wurde, wird er als Startpunkt zur Identifizierung eines komplexen Knotenpunkts verwendet. Jede Verbindung zu diesem wird aufgelistet und gespeichert, und es wird auf eine davon, die früher noch nicht betrachtet wurde, zugegriffen (64). Der andere Schlußknoten davon wird nun als der neue Startpunkt genommen, solange er noch nicht bei der Suche betrachtet worden ist. Wenn der neue Knoten ein Nicht-Austrittsknoten ist (66), wird der Prozeß wiederholt. Wenn der neue Knoten jedoch ein Austrittsknotenpunkt ist, werden die Daten des dorthin befolgten Weges gespeichert, und es erfolgt ein Zugriff auf den zuletzt gespeicherten Knoten für die Behandlung auf die obige Weise (70). Wenn keine weitere Erweiterung in der Richtung der Austrittsknotenpunkte möglich ist (64), geht das System zu der unteren Hälfte der Figur über.
• Ein Austrittsknotenpunkt wird ähnlich wie ein Eintrittsknotenpunkt durch Umkehren der Richtungen des zulässigen Verkehrs bestimmt; die Bedingungen sind ein Spiegelbild der Bedingungen der Eintrittsknotenpunkte. Die Verarbeitung von Eintrittsknotenpunkten und jedes daraus abgeleiteten Knotenpunkts wird wie oben erläutert fortgesetzt, bis keine weiteren unverarbeiteten elementaren Knotenpunkte übrigbleiben, die sich als Eintrittsknotenpunkt herausstellen könnten.
• Als nächstes wird die Erweiterung von den so gefundenen Austrittsknoten auf eine der oben beschriebenen entsprechende Weise ausgeführt, wobei der einzige Unterschied in der Richtung entlang der Verbindungen und dem Anhalten, wenn ein neuer Eintritt gefunden wird, besteht. Das Zugreifen wird fortgesetzt, bis keine weiteren in der oberen Hälfte der Figur gefundenen potentiellen Austrittsknotenpunkte übrig sind. Wiederum können neue Eintrittsknotenpunkte gefunden werden. Diese neuen Eintrittsknoten werden wiederum auf die oben für den ersten Austrittsknotenpunkt beschriebene Weise in der oberen Hälfte der Figur verarbeitet. Der Prozeß alterniert so zwischen der Suche nach Eintrittsknotenpunkten und der Suche nach Austrittsknotenpunkten. Das Verfahren endet (82), wenn kein neuer Knotenpunkt gefunden wurde (80). Das Verfahren ist dann für den nächsten in Frage kommenden komplexen Knotenpunkt bereit, indem an einem neuen Eintrittsknotenpunkt begonnen wird, der noch nicht betrachtet wurde. Zum Finden aller komplexen Knotenpunkte muß auf alle elementaren Knotenpunkte in der Gesamtmenge mindestens einmal zugegriffen werden, um zu sehen, ob sie Anfangs- Eintrittsknotenpunkte sind.
• Nun wird von allen Knoten in einer bestimmten Menge von Knoten bestimmt, ob sie Randknoten sind: dies sind Knoten, die mit einem elementaren Knotenpunkt außerhalb der in Frage stehenden Menge oder mit einer anderen Menge elementarer Knotenpunkte verbunden sind. Zunächst werden, wenn zwei oder mehr Knoten in einer Menge mit derselben anderen Menge von Knoten verbunden sind, die zulässigen Verkehrsrichtungen auf den Zwischenverbindungen bestimmt, und die externen Straßenzwischenverbindungen werden zu einer komplexen externen Straßenverbindung verknüpft. Die letztere Verbindung erhält alle zulässigen Verkehrsrichtungen auf den elementaren Verbindungen zwischen den beiden Mengen. Wenn anwendbar, wird eine ähnliche Prozedur auf den Verbindungen zwischen einer Menge von nun verknüpften elementaren Knotenpunkten und einem einzigen weiteren elementaren Knotenpunkt, der nicht in einen komplexen Knotenpunkt verbunden ist, bewirkt.
• Fig. 6 ist das Flußdiagramm des erfindungsgemäßen Verfahrens zum Finden und Abstrahieren eines komplexen Knotenpunkts. Die verschiedenen Blöcke sind folgendermaßen gekennzeichnet.
• 60 START: Laden.
• 62 EINTRITTSKNOTENPUNKT FINDEN, nur durch einmaliges Zugreifen auf alle Knotenpunkte, auf die noch nicht zugegriffen worden ist.
• 64 EINER ÜBRIG, Erkennen, ob der Eimer unverarbeiteter Knotenpunkte der Menge mindestens einen Knotenpunkt enthält; wenn man von 62 kommt, ist dies der dort gefundene.
• 66 NICHT-AUSTRITT? Erkennen, ob der vorliegende Knotenpunkt ein Nachfolger- oder Austrittsknotenpunkt ist; wenn man von 62 kommt, ist dies eine Dummy-Frage, die immer mit Ja beantwortet wird.
• 68 ERWEITERN, wenn positiv in 68 und Speichern anderer Knotenpunkte, die mit dem neuen Nachfolgerknotenpunkt in dem Eimer verbunden sind.
• 70 FINDE NEUEN KNOTENPUNKT aus dem Eimer, entweder nach Erweiterung oder direkt aus 66, wenn negativ.
• Wenn negativ in 64, wird der Eimer nach Nicht-Eintritts- oder Vorgängerknotenpunkten in derselben Konfiguration (72, 74, 76, 78) wie bei der Suche nach Nachfolgerknotenpunkten durchsucht. Wenn negativ in 72, gehe zu 80. Wenn positiv in 80, gehe zu 70. Gewöhnlich benötigt ein komplexer Knotenpunkt nur eine Durchquerung von der oberen Hälfte zu der unteren Hälfte in Fig. 6.
• 80 ETWAS GEFUNDEN, entweder ein neuer Nachfolgerknoten in der oberen Hälfte oder ein neuer Vorgängerknoten in der unteren Hälfte der Figur. Wenn negativ, wurden nun alle elementaren Knotenpunkte des komplexen Knotenpunkts gefunden und der Prozeß endet.
• 82 STOP. Wenn positiv, geht das System jedoch zurück zum Block 70. Andere komplexe Knotenpunkte als der einzelne in Frage stehende wurden in der Figur nicht betrachtet.
• Die obige Behandlung kann mit der Verarbeitung auf der Grundlage der Eigenschaft Knotenpunkt in der in bezug auf Tabelle 3 angeführten chain list kombiniert werden. Zum Beispiel kann diese Eigenschaft anzeigen, dass die in Frage stehende elementare Verbindung Teil eines Kreisverkehrknotenpunkts ist. Dies ermöglicht zunächst eine Abstrahierung solcher Kreisverkehrknotenpunkte auf einfache Weise zu einem komplexen Knotenpunkt, der auf eine abstrahierte Weise zum schnellen Zugriff oder zur leichten Anzeige dargestellt werden kann. Außerdem ermöglicht dies eine Verknüpfung des Kreisverkehrs mit noch mehr nahe gelegenen elementaren Knotenpunkten zu einem komplexen Knotenpunkt einer höheren Ebene. Auf ähnliche Weise kann eine Kohärenz elementarer Knotenpunkte durch ihre gegenseitige Nähe allein diktiert werden; bestimmte Gegenmaßnahmen können dann erforderlich sein, um die Darstellung größerer Städte durch nur einen einzigen komplexen Knotenpunkt zu vermeiden. Zum Beispiel kann die Gesamtgröße einer Menge elementarer Knotenpunkte eine obere Grenze entweder der Zahl elementarer Knotenpunkte oder des Abstands über die Menge hinweg aufweisen.
• Fig. 7 zeigt ein Fahrzeug mit einem Navigationssystem gemäß der Erfindung, das nur sehr schematisch gezeigt worden ist. Das Auto hat ein Chassis 120, Vorderräder 122 und Hinterräder 124, die durch eine Kombination von Motor und Getriebe 126 angetrieben werden. Der Einfachheit halber wurden die Benutzerschnittstelle zu dem Motor und andere mechanische Steuergrößen des Autos nicht gezeigt. Das gezeigte Auto enthält verschiedene Systeme zur Bestimmung seiner tatsächlichen Position. Erstens gibt es einen Kompaß 130. Zweitens gibt es eine Schrittmesserkombination 132, die einen getrennten Schrittmesser an jedem Rad eines Radpaars aufweisen kann. In der Figur wurde dies für die angetriebenen Hinterräder gezeigt, obwohl in der Praxis gewöhnlich die nicht angetriebenen Räder gewählt werden. Die mittlere Verschiebung, die durch die beiden Schrittmesser in Kombination mit dem Kompaß-Ablesewert signalisiert wird, ergibt die zurückgelegte Entfernung und die Richtung. Die Differenz zwischen den beiden Schrittmesser-Meßwerten wird zur Berechnung von Abbiegungen verwendet, die zusammen mit dem Kompaß Korrekturen und/oder Kalibrierungen der zurückgelegten Entfernung erzeugen können. Diese und andere Berechnungen werden in dem Prozessor 134 bewirkt. An sich können die notwendigen mathematischen Berechnungen herkömmlich sein.
• Ein zweites Positionsbestimmungssystem besitzt eine Scheibenantenne 150, die Wellenmuster von verschiedenen GPS- Satelliten empfängt, und aus diesen Wellenmustern wird in dem Prozessor 148 eine tatsächliche Position berechnet. Ein drittes Positionsbestimmungssystem besitzt eine Antenne 154, die Positionscodes von Baken am Straßenrand empfängt, die eine begrenzte Sendereichweite aufweisen. Durch Erkennung der Codes wird in dem Prozessor 156 die tatsächliche Position bestimmt.
• Block 140 ist ein CD-ROM-Player, der eine optische Direktzugriffsplatte mit geographischen Daten enthält, einschließlich der wie oben angeführt angeschafften Datenbank. Auf diese Datenbank kann für vielfältige Zwecke durch den Routenplanerprozessor 138 unter selektiver Steuerung von der Benutzerschnittstelle 142, die eine Anzahl betätigbarer Tasten enthält, zugegriffen werden. Die Eingabe einer Startposition und eines Ziels aktiviert den Zugriff auf entsprechende Kartendaten aus dem Player 140. Aus diesen berechnet der Prozessor 138 eine optimale Route, eine erwartete Ankunftszeit. Der Prozessor 158 kombiniert die Positionsdaten, die von den Prozessoren 134 (sensorbestimmt), 148 (GPS- bestimmt) und 156 (durch Bakensignale) erzeugt werden, soweit wie angemessen, greift auf die geographischen Daten aus dem Player 140, die für die berechnete vorläufige tatsächliche Position relevant sind, zu und bildet diese auf die tatsächliche Karte ab. Eine Koppeloperation bildet die berechnete vorläufige Position auf die wahrscheinlichste tatsächliche Straßenposition ab, wenn eine Off-Road-Bewegung ignoriert werden kann. Die tatsächliche Position und die geplante Route in der Umgebung der tatsächlichen Position können in Kartenform auf dem Anzeigeelement 146 angezeigt werden. Außerdem können andere für den Fahrer relevante Daten angezeigt werden, wie zum Beispiel die aktuelle Uhrzeit, die erwartete Ankunftszeit, momentane Führungsanzeigen, wie zum Beispiel Pfeile, und das Ziel.
• In der Praxis werden nicht alle drei Positionsdatenerzeugungsmechanismen notwendig sein. Zum Beispiel kann das GPS-System für sich ausreichen, wenn Hindernisse, wie zum Beispiel Hochhäuser, selten genug sind und die GPS- Genauigkeit gut ist. In der Praxis ist die CD-ROM- Unterstützung jedoch notwendig, um das durch ungenaue Sensoren entstehende Driften zu vermeiden oder einen vorübergehenden Ausfall der anderen Verfahren zu überbrücken. Auf die Routenplanung kann bei bestimmten Realisierungen der vorliegenden Erfindung verzichtet werden.
• Der Block 128 kann eine diskrete interne Änderung des Status des Fahrzeugs, wie zum Beispiel das Starten oder Stoppen des Fahrzeugs, erkennen. Andere interne Änderungen des Status des Fahrzeugs bezüglich der Navigation können in dem zentralen Prozessor 158 erkannt werden. Dieser Prozessor ist mit dem Sender/Empfänger 144, mit dem Routenplanungsprozessor 38 und auch mit den Positionsbestimmungsprozessoren 134 und 156 verbunden. Ein Beispiel für eine solche andere Änderung ist, dass ein vorbestimmter Abstand abgedeckt wurde.
• Der Block 144 ist ein Sender/Empfänger für ein zellulares Rundsendesystem mit beschränkter Reichweite. Das Element 152 ist die zugehörige Antenne. Die Erkennung einer internen Änderung des Zustands, die entweder durch das Element 128 oder den zentralen Prozessor 158 erkannt wird, führen den zentralen Prozessor dazu, ein Senden der tatsächlichen Position durch den Sender/Empfänger 144 zu verursachen. Die tatsächliche Position wird dann formatiert und über die Antenne 152 zu der Zentralstation 200 rundgesendet. Das beschriebene Fahrzeug wurde ausführlicher in der eigenen US-Anmeldung mit der laufenden Nr. 08/433,669, entsprechend EP 959915293.5 (PHN 14.843) offengelegt.

Claims (8)

1. Verfahren zum Speichern geographischer Straßendaten in mehrfachen, hierarchisch organisierten Ebenen durch Ableiten einer abstrahierten Darstellung auf einer zweiten Ebene aus ersten Darstellungen aus einer ersten Ebene, die solche ersten Darstellungen von Straßenverbindungen und Knotenpunkten aufweist, die elementare Straßenverbindungen und elementare Knotenpunkte umfassen, gekennzeichnet durch folgende Schritte:

a) auf einer derartigen ersten Ebene Verknüpfen einer Menge der elementaren Knotenpunkte zu einem komplexen Knotenpunkt auf der Basis vorbestimmter Attribute der elementaren Knotenpunkte der Menge,

b) Wiederholen des Schritts a), bis alle komplexen Knotenpunkte gefunden wurden,

c) Festlegen von Randknoten eines ersten komplexen Knotenpunkts und Festlegen aller elementaren Verbindungen zwischen diesen Randknoten und jedem Element eines zweiten komplexen Knotenpunkts als elementare externe Straßenverbindungen, einschließlich aller zulässigen Verkehrsrichtungen auf derartigen elementaren externen Straßenverbindungen, und Ersetzen aller elementaren externen Straßenverbindungen zwischen Randknoten des ersten komplexen Knotenpunkts und jedem Element des zweiten komplexen Knotenpunkts durch eine einzige Ersatzstraßenverbindung, während die zulässigen Verkehrsrichtungen darauf abgebildet werden,

d) Wiederholen von Schritt c), bis alle Ersatzstraßenverbindungen zwischen zwei beliebigen, auf diese Weise gepaarten komplexen Knotenpunkten festgelegt wurden,

e) Darstellen jedes verbleibenden elementaren Knotenpunkts und jedes komplexen Knotenpunkts durch einen jeweiligen einzelnen Knoten, während jede verbleibende elementare externe Straßenverbindung und jede Ersatzstraßenverbindung durch eine einzelne Straßenverbindung auf der zweiten Ebene mit zugehörigen originalen beziehungsweise abgebildeten Verkehrsrichtungen dargestellt werden.

2. Verfahren nach Anspruch 1, wobei jede einzelne Straßenverbindung der zweiten Ebene durch eine gerade Linie dargestellt wird.

3. Verfahren nach Anspruch 1 oder 2, wobei die Darstellung auf einer Sichtanzeige ausgeführt wird.

4. Verfahren nach Anspruch 1, 2 oder 3, wobei das Festlegen bezüglich eines bestimmten komplexen Knotenpunkts das Aufsuchen eines zulässigen Verkehrswegs in der dazugehörigen Menge elementarer Knotenpunkte, der eine ankommende zulässige Verkehrsrichtung auf einer Straßenverbindung der ersten Ebene mit einer abgehenden zulässigen Verkehrsrichtung auf einer Straßenverbindung der zweiten Ebene verbindet, aber im Falle der Unzulässigkeit das Beibehalten einer Sperrkennzeichnung für das zugehörige Straßenverbindungspaar des zugehörigen komplexen Knotenpunkts der zweiten Ebene umfaßt.

5. Verfahren nach einem der Ansprüche 1 bis 4, wobei die Länge einer komplexen Straßenverbindung der zweiten Ebene auf eine mittlere Länge der zugehörigen elementaren Straßenverbindungen plus einen Größenwert einer oder beider Mengen durch sie verbundener elementarer Knotenpunkte gesetzt wird.

6. Verfahren nach einem der Ansprüche 1 bis 5, wobei das Verknüpfen das Ausführen aufeinanderfolgender und rückgeführter Erweiterungsschritte von Eintrittsknotenpunkten zu Folgeknotenpunkten und Austrittsknotenpunkten und rückwärts von allen Austrittsknotenpunkten zu Vorgängerknotenpunkten und Eintrittsknotenpunkten umfaßt, bis ein endgültiger Schluß der Erweiterung erfaßt wird, wodurch alle bei der Erweiterung gefundenen Knotenpunkte in der zugehörigen Menge enthalten sind.

7. Verfahren nach einem der Ansprüche 1 bis 6, wobei die erzeugte Datenstruktur auf einem Speichermedium gespeichert wird.

8. Datenverarbeitungssystem zum Verarbeiten und Speichern geographischer Straßendaten in mehrfachen, hierarchisch organisierten Ebenen durch Ableiten einer abstrahierten Darstellung auf einer zweiten Ebene aus ersten Darstellungen aus einer ersten Ebene, die solche ersten Darstellungen von Straßenverbindungen und Knotenpunkten aufweist, die elementare Straßenverbindungen und elementare Knotenpunkte umfassen, wobei das System folgendes umfaßt:

a) Verknüpfungsmittel zum Verknüpfen einer Menge elementarer Knotenpunkte zu einem komplexen Knotenpunkt auf der Basis vorbestimmter Attribute der elementaren Knotenpunkte der Menge auf einer derartigen ersten Ebene,

b) erste Abfolgesteuerungsmittel zum periodischen Aktivieren der Verknüpfungsmittel von Punkt a), bis alle komplexen Knotenpunkte gefunden wurden,

c) Ermittlungsmittel zum Festlegen aller Randknoten eines ersten komplexen Knotenpunkts und zum Festlegen aller elementaren Verbindungen zwischen diesen Randknoten und jedem Element eines zweiten komplexen Knotenpunkts als elementare externe Straßenverbindungen, einschließlich aller zulässigen Verkehrsrichtungen auf derartigen elementaren externen Straßenverbindungen, und Ersetzen aller elementaren externen Straßenverbindungen zwischen Randknoten des ersten komplexen Knotenpunkts und jedem Element des zweiten komplexen Knotenpunkts durch eine einzige Ersatzstraßenverbindung, während alle zulässigen Verkehrsrichtungen darauf abgebildet werden,

d) zweite Abfolgesteuerungsmittel zum periodischen Aktivieren der Ermittlungsmittel von Punkt c) bis alle Ersatzstraßenverbindungen zwischen zwei beliebigen auf diese Weise gepaarten komplexen Knotenpunkten gefunden wurden,

e) Darstellungsmittel zum Darstellen jedes verbleibenden elementaren Knotenpunkts und jedes komplexen Knotenpunkts durch einen jeweiligen einzelnen Knoten, während jede verbleibende, elementare externe Straßenverbindung und jede Ersatzstraßenverbindung durch eine einzelne Straßenverbindung auf der zweiten Ebene mit zugehörigen originalen beziehungsweise abgebildeten Verkehrsrichtungen dargestellt werden.