NL8701738A

NL8701738A - Werkwijze voor het opslaan van een topologisch netwerk in een geheugen en voor het opzoeken van een 2-cel uit dat netwerk, alsmede inrichting voor het uitvoeren van de werkwijze voor het opzoeken.

Info

Publication number: NL8701738A
Application number: NL8701738A
Authority: NL
Original assignee: Philips Nv
Priority date: 1987-07-23
Filing date: 1987-07-23
Publication date: 1989-02-16
Also published as: EP0302547A3; JP2801208B2; ES2042713T3; EP0302547B1; EP0302547A2; JPS6482259A; CA1308493C; US4954986A; DE3882100D1; DE3882100T2

Description

V

* * PHN 12.197 1 N.V. Philips' Gloeilampenfabrieken te Eindhoven

Werkwijze voor het opslaan van een topologisch netwerk in een geheugen en voor het opzoeken van een 2-cel uit dat netwerk, alsmede inrichting voor het uitvoeren van de werkwijze voor het opzoeken.

De uitvinding heeft betrekking op een werkwijze voor het digitaal opslaan van een twee-dimensionaal topologisch, door middel van een verzameling 0-, 1- en 2-cellen weergegeven, netwerk in een geheugen, waarbij voor elke 1-cel ten minste één geheugenadres is voorzien 5 waar voor die 1-cel telkens een eerste en een tweede bij die 1-cel aangesloten 0-cel wordt opgeslagen alsmede aan genoemde eerste respektievelijk tweede 0-cel een respektievelijke thread-pointer wordt toegekend die een 1-cel aanwijst, welke aansluit aan de 0-cel aan dewelke hij is toegekend.

10 Een dergelijke werkwijze is bekend uit het artikel “A

Tiger for tomorrow" van R.H. Moore en gepubliceerd in het konferentieverslag van de "Joint symposium for urban data management systems and the spatially oriented referencing systems association" (3 juni 1985, Den Haag, Nederland).

15 Bij de bekende werkwijze wordt er voor elke 1-cel van het topologisch netwèrk telkens een eerste en een tweede 0-cel opgeslagen die het begin-en eindpunt van de 1-cel aangegeven. Aan die 0-cel wordt dan zonder enige systematiek een thread-pointer toegekend die een willekeurige verdere bij die 0-cel aangesloten 1-cel aanwijst. Ten einde de topologie 20 te herkennen worden er bij die 1-cel nog verdere gegevens opgeslagen, zoals bijvoorbeeld de 2-cellen links en rechts uitgestrekt van de betreffende 1-cel, alsook thread-pointers toegekend aan die 2-cellen.

Een nadeel van de bekende werkwijze is dat de threadpointer toegekend aan een 0-cel een willekeurige verdere 1-cel, 25 welke aansluit bij de betreffende 0-cel, aanwijst. Door deze willekeurige keuze is er geen enkele systematiek of structuur in het toekennen van thread-pointers. Dat heeft dan voor consequenties dat de topologie van het netwerk of niet te achterhalen is uit de tabel waarin de 1-cellen zijn opgeslagen, of dat er additionele geheugenruimte 30 nodig is om verdere gegevens op te slaan die de topologie weergeven. Het gebruik van additionele geheugenruimte kost dan weer geheugencapaciteit die niet voor andere doeleinden beschikbaar is.

; ί -λ * H y o w PHN 12.197 2

De uitvinding beoogt een werkwijze voor het opslaan van een topologisch netwerk in een geheugen te realiseren waarbij een structuur en een systematiek is aangebracht in de aan de 0-cellen toe te kennen thread-pointers.

5 Een werkwijze volgens de uitvinding heeft daartoe het kenmerk, dat een punt behorende tot de beschouwde 1-cel en gelegen nabij de beschouwde 0-cel volgens een voorafbepaalde draairichting rond een as door de beschouwde O-cel en nagenoeg loodrecht op het vlak van het netwerk wordt gedraaid totdat het genoemde punt samenvalt met een punt 10 van een verdere 1-cel die aansluit aan de beschouwde 0-cel, en dat aan de beschouwde 0-cel die thread-pointer wordt toegekend die genoemde verdere 1-cel aanwijst.Door gebruik te maken van een draaiing in een voorafbepaalde richting ligt de keuze van de door de thread-pointer aan te wijzen 1-cel vast en dus ook de keuze van de thread-pointer. Deze 15 systematiek introduceert dan extra informatie waardoor gegevens betreffende de topologie mede opgeslagen zijn. Doordat een thread-pointer nu telkens wijst naar een volgende 1-cel die door rotatie in de voorafbepaalde richting wordt verkregen, wordt zodoende alle aan die 0-cel aangesloten 1-cellen gevonden en is zodoende de topologie bekend.

20 Bij topologische netwerken waarbij ten minste één 1- cel gevormd is door een geloten lus, is de eerste en de tweede O-cel behorende bij zo'n 1-cel identiek. Om de behandeling van zulke gesloten lussen eenvoudiger te maken is het gunstig dat in een punt van een gesloten lus, welk punt verschillend is van een junctie 0-cel die de 25 aansluiting van die gesloten lus met een overige 1-cel van het netwerk aangeeft, een virtuele o-cel wordt aangebracht, en dat de gesloten lus als een eerste en een tweede deel-1-cellen wordt opgeslagen waarbij de eerste respektievelijk de tweede 0-cel aangegeven bij de eerste deel-1-cel gevormd is door de junctie 0-cel respektievelijk de virtuele 0-cel 30 en de eerste respektievelijk de tweede 0-cel aangegeven bij de tweede deel-1-cel gevormd is door de virtuele 0-cel respectievelijk de junctie 0-cel.

De uitvinding beoogt verder een werkwijze te realiseren voor het, in een topologisch netwerk, opgeslagen in een geheugen, 35 opzoeken van de 1- en de 0-cellen die een 2-cel begrenzen, waarbij gebruik wordt gemaakt van de systematiek en de structuur die toegepast werd bij het opslaan van de 1-cellen.

8701736 4 * PHN 12.197 3

Een werkwijze volgens de uitvinding, voor het opzoeken van de 1- en de O-cellen die een 2-cel begrenzen heeft daartoe het kenmerk dat uitgaande van een eerste stelsel gevormd door een eerste 1-cel uit het netwerk en één zijner aangesloten O-cellen een tweede 5 stelsel wordt gevormd door de andere O-cel aangesloten aan genoemde eerste 1-cel te kiezen alsook de 1-cel aangewezen door de aan genoemde andere O-cel toegekende thread-pointer, met welk tweede stelsel een derde stelsel wordt gevormd door de 1-cel uit het tweede stelsel in het geheugen te adresseren en de bij die geadresseerde 1-cel aangesloten 10 andere O-cel dan diegene opgenomen in het tweede stelsel te nemen alsook de 1-cel aangewezen door de thread-pointer toegekend aan laatstgenoemde andere O-cel, welk derde stelsel vervolgens met het eerste stelsel wordt vergeleken en in geval van overeenkomst de gezochte 2-cel door het eerste, tweede en derde stelsel is begrensd, en in geval van niet-15 overeenkomst het tweede stelsel wordt gebufferd en vervolgens door het derde gesubstitueerd om, uitgaande van het gesubstitueerde tweede stelsel,een verder derde stelsel te vormen en dat deze operaties telkens worden herhaald totdat het eerste stelsel overeenkomt met een aldus gevormd derde stelsel.

20 Door telkens de andere O-cel te kiezen, wordt het andere uiteinde van de 1-cel bereikt en door voor het vormen van een stelsel telkens die 1-cel te kiezen die wordt aangewezen door de thread-pointer toegekend aan die andere O-cel worden de contouren van de op te zoeken 2-cel herkend. Door de keuze bij het toekennen van de thread-pointer is de 25 1-cel aangewezen door de thread-pointer steeds diegene die bij het te vormen contour aansluit, hierdoor wordt het contour van de 2-cel snel herkend aangezien het niet noodzakelijk is additionele gegevens op te halen die de topologie weergeven. Wanneer eerste en derde stelsel met elkaar corresponderen volgt onmiddellijk dat de op te zoeken 2-cel 30 gecontourneerd is.

Wanneer er bij het opslaan van het netwerk geen gebruik is gemaakt van virtuele O-cellen om 1-cellen gevormd door gesloten lussen in deel-1-cellen te verdelen, is het gunstig dat uitgaande van een eerste stelsel gevormd door een eerste 1-cel uit het netwerk en 35 één zijner aangesloten O-cellen een tweede stelsel wordt gevormd door de andere O-cel aangesloten aan genoemde eerste t-cel te kiezen alsook de 1-cel aangewezen door de aan genoemde andere Ö-cel toegekende 8701733 PHN 12.197 4 thread-pointer, en dat vervolgens de 1-cel uit het tweede stelsel in het geheugen wordt geadresseerd en uit de opgehaalde gegevens wordt onderzocht of de eerste en de tweede 0-cel aangesloten bij die 1-cel identiek zijn en waarbij in het geval van identieke eerste en tweede 0-5 cel een derde stelsel wordt gevormd door de identieke 0-cel te kiezen alsmede die 1-cel, aangewezen door de aan één van beide 0-cellen toegekende thread-pointer, die verschillend is van de 1-cel uit het tweede stelsel, en waarbij in het geval van niet identieke eerste en tweede 0-cellen het derde stelsel wordt gevormd door de bij die 10 geadresseerde 1-cel aangesloten andere 0-cel dan diegene opgenomen in het tweede stelsel te nemen alsook de 1-cel aangewezen door de thread-pointer toegekend aan laatstgenoemde andere 0-cel, welk derde stelsel vervolgens met het eerste stelsel wordt vergeleken en in geval van overeenkomst de gezochte 2-cel door het eerste, tweede en derde stelsel 15 is begrensd, en in geval van niet-overeenkomst het tweede stelsel wordt gebufferd en vervolgens door het derde gesubstitueerd om uitgaande van het gesubstitueerde tweede stelsel een verder derde stelsel te vormen en dat deze operaties telkens worden herhaald totdat het eerste stelsel overeenkomt met een aldus gevormd derde stelsel.

20 Het onderzoek naar identieke eerste en tweede 0-cellen laat onmiddellijk zien of de betreffende 1-cel een gesloten lus vormt. Immers bij gesloten lussen vallen begin en eindpunt samen. Door in het geval van identieke eerste en tweede 0-cellen het derde stelsel te vormen door één van beide 0-cellen alsmede die 1-cel aangewezen door 25 de aan één van beide 0-cellen toegekende thread-pointer, die verschillend is van de 1-cel uit het tweede stelsel wordt vermeden dat er steeds opnieuw dezelfde 1-cel wordt gekozen en dat er zodoende in de gesloten wordt rondgedraaid.

Het is gunstig dat de eerste 1-cel uit het eerste stelsel 30 in het geheugen wordt geadresseerd en dat uit de opgehaalde gegevens wordt onderzocht of de eerste en de tweede 0-cel aangesloten bij de eerste 1-cel, identiek zijn, en dat in het geval van identieke eerste en tweede 0-cel de te zoeken 2-cel diegene is die door de eerste 1-cel wordt omsloten.

35 Hierdoor kan meteen worden vastgesteld of de 1-cel uit het eerste stelsel een gesloten lus vormt.

De uitvinding heeft eveneens betrekking op een inrichting 8701738 te te PHN 12.197 5 voor het uitvoeren van de werkwijze voor het opzoeken van de 1- en de 0-cellen die een 2-cel begrenzen. Een inrichting volgens de uitvinding heeft het kenmerk dat in het geheugen het topologisch netwerk is opgeslagen, en dat de inrichting een adresgenerator bevat voor het 5 genereren van geheugenadressen voor het adresseren van de in de eerste en tweede stelsels aangegeven 1-cellen, en een vergelijkeenheid voor het uitvoeren van een vergelijkingsoperatie tussen genoemde eerste en derde stelsel.

De inrichting volgens de uitvinding is in het bijzonder 10 toepasbaar in een land-voertuignavigatiesysteem dat voorzien is van een positiebepalingseenheid voor het bepalen van positiekoördinatie van het voertuig alsook van een omzeteenheid voor het omzetten van positiekoördinaten in een eerste stelsel.

De uitvinding zal nader worden beschreven aan de hand van 15 de tekening waarin: figuur 1 een voorbeeld van een topologisch netwerk laat zien; figuur 2 een gedeelte van het netwerk uit figuur 1 laat zien; 20 figuur 3 een voorbeeld laat zien van een topologisch netwerk dat een gesloten lus bevat; figuur 4 schematisch de hoofdbestanddelen van een voorbeeld van een land-voertuignavigatiesysteem laat zien; figuur 5 een stroomdiagram laat zien voor een voorbeeld 25 van een programma voor het opzoeken van de 1- en de 0-cellen die een 2-cel begrenzen.

Figuur 1 laat een voorbeeld van een topologisch netwerk zien. Dat netwerk is bijvoorbeeld een wegennetwerk zoals weergegeven op een wegenkaart, een stadsplan, een sporennetwerk of de bedrading van een 30 elektronische schakeling.

Eenvoudigheidshalve zal er worden verondersteld dat het netwerk een wegennetwerk of een stadsplan is. De cijfers 1, 2, ..., 6 geven verkeersknooppunten aan en de letters a, b, c, d, e, f, genh geven telkens een weggedeelte aan dat door twee knooppunten is begrensd. Zo is 35 bijvoorbeeld het weggedeelte b door de knooppunten 2 en 3 begrensd. Ten einde ook een oriëntatie voor de verschillende weggedeeltes vast te leggen, wordt er voor elke weggedeelte een begin- en een eindpunt s 7 3 É PHN 12.197 6 aangegeven. Zo is bijvoorbeeld knooppunt 1 het beginpunt van weggedeelte C en knooppunt 4 het eindpunt.

Bij topologische netwerken worden nu zulke knooppunten als O-cel aangeduid en de weggedeeltes als 1-cel. Algemeen geldt er dat een n-cel 5 een aaneengesloten, n-dimensionaal, geometrisch objekt voorstelt. Een door weggedeelten omsloten oppervlak vormt dus een 2-cel. In het netwerk afgebeeld in figuur 1 zijn er vier 2-cellen weergegeven, namelijk de 2-cellen A, B, C en E. 2-cel A wordt omsloten door de 1-cellen a, b, h en c en door de 0-cellen 1, 2, 3 en 4.

10 Wanneer nu zo'n netwerk gedigitaliseerd in een geheugen, bijvoorbeeld een optische schijf, moet worden opgeslagen, ten einde verwerking met behulp van een computer mogelijk te maken, bijvoorbeeld bij een voertuignavigatiesysteem, is het niet alleen noodzakelijk om de verschillende 0, 1 en 2-cellen op te slaan maar moeten ook de relaties 15 tussen deze verschillende cellen bekend zijn. Immers de topologie van het netwerk moet uit de opgeslagen gegevens te achterhalen zijn.

Tabel I (TAB 1) laat een voorbeeld zien van de inhoud van een geheugentabel waarin de gegevens van het in figuur 1 afgebeelde topologisch netwerk zijn opgeslagen. In de eerste kolom van deze tabel 20 is een lijst met alle 1-cellen, alfabetisch gerangschikt, opgenomen.

Elke 1-cel vormt dus als het ware een adres voor een geheugenplaats. Bij iedere 1-cel is een eerste respektievelijk een tweede O-cel opgenomen welke het beginpunt respektievelijk het eindpunt van het bij die 1-cel behorende weggedeelte aangeeft. Zo zijn bijvoorbeeld bij 1-cel a de 0-25 cellen 1 en 2 als eerste respektievelijk tweede O-cel opgenomen. Bij voorkeur wordt als beginpunt de O-cel met de kleinste X-koordinaat (meest links gelegen) gekozen. Verder is er bij de eerste en de tweede 0-cel behorende bij eenzelfde 1-cel telkens een M thread-pointer" opgenomen. Zo'n thread-pointer wijst naar een verdere 1-cel welke 30 aansluit bij de 0-cel aan dewelke de thread-pointer is toegekend.

Bij een werkwijze volgens de uitvinding geschiedt het toekennen van een thread-pointer nu door de volgorde van de thread-pointers die de relatie tussen de 0-cellen en 1-cellen beschrijven zo te kiezen dat ze een rechtsomdraaiend stelsel vormen. Het zal duidelijk 35 zijn dat de draairichting net zo goed linksomdraaiend kan zijn en dat rechts- of linksomdraaiend een voorafbepaalde keuze vormt. In het beschreven uitvoeringsvoorbeeld zal een rechtsomdraaiende draairichting 8701738 PHN 12.197 7 worden gekozen.

In figuur 2 is een gedeelte van het netwerk uit figuur 1 overgenomen. Beschouw nu in figuur 2 de 1-cel b en daarbij behorende tweede 0-cel 3. De aan die tweede O-cel 3 toe te kennen thread-pointer 5 wordt nu verkregen door een punt P behorende tot 1-cel b en gelegen nabij 0-cel 3 rechtsom te laten draaien rond een as (in de figuur niet weergegeven) door 0-cel 3 en nagenoeg loodrecht op het vlak gevormd door het netwerk. Het punt P wordt nu zover rond die as gedraaid todat het samenvalt met een punt van een eerst volgende 1-cel. De toe te kennen 10 thread-pointer wijst nu naar de aldus verkregen 1-cel. De uitgevoerde rotatie levert nu een punt P' op, gelegen op 1-cel h en nabij 0-cel 3. De 1-cel h is dus de eerste 1-cel die wordt verkregen door het punt P behorende tot 1-cel b te laten draaien in de voorafbepaalde richting. De aan 0-cel 3 behorende bij 1-cel b toegekende thread-pointer wijst 15 bijgevolg 1-cel h aan. Dit resultaat is weergegeven in tabel I. Op analoge wijze wordt er nu aan 0-cel 3 behorende bij 1-cel h, een thread-pointer toegekend die 1-cel f aanwijst. Immers rotatie rechtsom van P' levert het punt P" behorende tot 1-cel f. Zodoende wordt er voor elke 1-cel telkens aan zijn bijbehorende eerste respektievelijk tweede 0-cel 20 een thread-pointer toegekend. Deze verschillende thread-pointers zijn in tabel I weergegeven.

Het belang om een voorafbepaalde draairichting vast te leggen zal aan de hand van het volgende voorbeeld worden duidelijk gemaakt. Kies nu 1-cel h, hiervan is 0-cel 4 het beginknooppunt, en dus 25 eerste 0-cel, aangezien dit het knooppunt met de kleinste X-waarde is.

De thread-pointer toegekend aan 0-cel 4 bij 1-cel h wijst door gebruik te maken van een rechtsomrotatie de 1-cel c aan. De tweede 0-cel behorende bij 1-cel h is 0-cel 3 en de daaraan toegekende thread-pointer wijst 1-cel f aan. Was er nu echter een linksomdraaiende rotatie gekozen 30 dan zou aan 0-cel 4 van diezelfde 1-cel h toegekende thread-pointer de 1-cel g aanwijzen en zou de thread-pointer toegekend 0-cel 3 de 1-cel b aanwijzen. Hieruit volgt dus dat bij keuze van een andere draairichting er duidelijk andere thread-pointers worden toegekend. Het is dus van belang om vooraf de draairichting vast te leggen bij het opstellen van 35 de geheugentabel zoals weergegeven in tabel I, ten einde één-éénduidig de keuze van de thread-pointers vast te leggen.

Tabel I bevat verder voor elke 1-cel de links en rechts Ö/01738 PHN 12.197 8 van die 1-cel gelegen 2-cel. Zo is bijvoorbeeld voor 1-cel d de 2-cel B links van die 1-cel gelegen en de 2-cel E is rechts gelegen van 1-cel d. De begrippen links en rechts worden verkregen door langs de betreffende 1-cel te gaan vertrekkende van het beginpunt en gaande naar 5 het eindpunt. Wanneer bij 1-cel d van beginpunt (0-cel 2) naar het eindpunt (0-cel 6) wordt gegaan dan bevindt zich 2-cel B langs de linkerzijde en 2-cel E zich langs de rechterzijde.

In deze tabel zijn nu de gegevens over het topologisch netwerk opgeslagen volgens en compacte en overzichtelijke manier.

10 Eveneens is er door het gebruik en de keuze van de thread-pointer een relatie tussen de verschillende cellen opgenomen.

Een bijzonderheid doet zich nu voor wanneer een 1-cel gevormd is door een gesloten lus. Hierbij vallen begin- en eindpunt samen en zijn zodoende de eerste en de tweede 0-cel identiek. Figuur 3 15 laat een voorbeeld zien van een topologisch netwerk dat een gesloten lus bevat. Bij de 1-cel r vallen begin- en eindpunt tezamen in 0-cel 12 die een junctie 0-cel vormt tussen de gesloten lus 3 en de 1-cel m van het netwerk. Wanneer nu dat netwerk uit figuur 3 digitaal in een geheugen wordt opgeslagen door gebruik te maken van de hiervoor beschreven 20 werkwijze, dan ontstaat er een 1-cellentabel zoals weergegeven in tabel (TAB II). Bij 1-cel r is nu de eerste 0-cel (12) gelijk aan de tweede 0-cel en wijst bovendien de thread-pointer toegekend aan de eerste 0-cel eveneens naar 1-cel r. Bij zoeken naar een 2-cel levert dit nu problemen op, zoals verderop zal worden beschreven.

25 Een alternatieve methode voor het opslaan van zo'n netwerk dat een gesloten lus bevat, bestaat hierin dat in de lus een virtuele 0-cel wordt opgenomen die de lus dan fiktief in twee delen verdeelt. In Figuur 3 is er in de 1-cel r een virtuele 0-cel 14 opgenomen die 1-cel r verdeelt in twee deel-1-cellen r^ en ^. De 1-cellentabel hiervoor 30 wordt weergegeven in tabel III (TAB III). Voor 1-cel r zijn er nu twee 1-cellen, namelijk r^ en ^ opgenomen die nu verschillende eerste en tweede 0-cellen bezitten. Zo is de eerste respektievelijk de tweede 0-cel van 1-cel r^, de 0-cel 12 respektievelijk 14 en zijn de 0-cellen 14 respektievelijk 12 de eerste respektievelijk tweede 0-cel van 1-cel 35 r2· Hierdoor is dus het probleem van gelijke eerste en tweede 0-cel van eenzelfde 1-cel opgelost. De gevolgen hiervan voor het opzoeken van een 2-cel omsloten door 1- en 0-cellen zullen verderop in de 8701738 * PHN 12.197 9 beschrijving worden behandeld.

Het opslaan van een topologisch netwerk in een geheugentabel volgens de hiervoor beschreven werkwijze heeft uiteraard consequenties voor het door middel van 0- en 1-cellen opzoeken van een 2-5 cel uit dat netwerk. Het opzoeken van zo'n 2-cel wordt bijvoorbeeld gebruikt bij een voertuignavigatiesysteem om na te gaan op welke weg uit het netwerk het voertuig zich bevindt.

Bij de werkwijze volgens de uitvinding wordt er nu een eerste stelsel gevormd door een eerste 1-cel en een daarbij behorende 0-10 cel te nemen, bijvoorbeeld het knooppunt (0-cel) en de daarop aangesloten weg ingeslagen door het voertuig in het geval van een navigatiesysteem. Kies nu bijvoorbeeld ter illustratie van de werkwijze volgens de uitvinding als eerste stelsel de 0-cel 3 en 1-cel h (h, 3).

Van dat eerste stelsel wordt nu een tweede stelsel gevormd door de 15 andere, bij die eerste 1-cel van het eerste stelsel behorende, 0-cel te kiezen alsmede de 1-cel aangewezen door de thread-pointer toegekend aan genoemde andere 0-cel. In het geval van het voorbeeld (h, 3) is 0-cél 4 de bij 1-cel h behorende andere (= van 0-cel 3 verschillende) 0-cel en wijst de aan die 0-cel 4 toegekende thread-pointer de 1-cel c aan zoals 20 af te lezen is uit tabel I. Het tweede stelsel wordt dus in het geval van het voorbeeld gevormd door (c, 4). Dat tweede stelsel wordt nu op zijn beurt gebruikt om een derde stelsel te vormen en wel door de in het tweede stelsel aangeven 1-cel te gebruiken als adres om de voor die 1-cel gebruikte geheugenplaats in de tabel te adresseren. Op die 25 geadresseerde geheugenplaats word nu, ten einde het derde stelsel te vormen, de andere 0-cel dan diegene aangegeven in het tweede stelsel opgehaald alsmede de aan die genoemde andere 0-cel toegekende thread-pointer. Bij het gebruikte voorbeeld, (tweede stelsel (c, 4)), houdt dit in dat geheugenplaats c wordt geadresseerd. Op deze geheugenplaats c, is 30 0-cel 1 genoemde andere 0-cel daar 0-cel 4 tot het tweede stelsel behoort. Aan deze 0-cel 1 is een thread-pointer die 1-cel a aanwijst, toegekend. Het derde stelsel wordt nu gevormd door (a, 1).

Na het vormen van het derde stelsel wordt er nu onderzocht of dit derde stelsel niet overeenkomt met het eerste stelsel 35 ten einde na te gaan of de contouren van de te vormen 2-cel nog niet bepaald zijn. Is dit niet het geval dan wordt het gevormde tweede stelsel gebufferd en wordt het tweede stelsel door het derde 8701738 PHN 12.197 10 stelsel gesubstitueerd. De hierboven beschreven operatie voor het tweede stelsel wordt dan herhaald met het gesubstitueerde tweede stelsel totdat een verder derde stelsel wordt verkregen dat overeenkomt met het eerste stelsel.

5 In bovengenoemde voorbeeld is het gevormde derde stelsel (a, 1) niet gelijk aan het eerste stelsel (hr 3), zodoende wordt het tweede stelsel (c, 4) gebufferd en wordt het derde stelsel (a, 1) door substitutie, tweede stelsel. Op basis van dat gesubstitueerde tweede stelsel (a, 1) wordt er nu een nieuw derde stelsel (b, 2) gevormd 10 (geheugenplaats a, 2 is andere 0-cel dan 1). Daar (b, 2) f (h, 3) wordt (a, 1) gebufferd. Het gesubstitueerd tweede stelsel (b, 2) levert vervolgens een derde stelsel (h, 3). Daar nu derde stelsel (h, 3) = (h, 3) eerste stelsel is de 2-cel gevormd. Onder gebruikmaking van de gebufferde tweede stelsels is er nu vastgesteld dat de 2-cel gevormd is 15 door de stelsels (h, 3), (c, 4), (a, 1) en (b, 2).

Nu de kontouren van de gezochte 2-cel gevonden zijn, kan er, door gebruik te maken van de in de geheugentabel (tabel I) opgeslagen informatie 2-cel links, 2-cel rechts eenvoudig worden nagegaan van welke 2-cel de contouren zijn gevonden. Immers zoals reeds 20 beschreven is, de informatie 2-cel links, 2-cel rechts, gekoppeld aan het begin- en eindpunt van de 1-cel bij dewelke die informatie is opgenomen. Het volstaat dus om, wanneer er een eerste stelsel wordt aangeboden, in de geheugentabel na te gaan of de in het eerste stelsel opgenomen 0-cel het begin- of het eindpunt van de in het eerste stelsel 25 aangegeven 1-cel is. Is die in het eerste stelsel opgenomen 0-cel het beginpunt, dan wordt de 2-cel links gevonden want de 2-cel wordt linksom gekontourneerd. Is daarentegen de opgenomen 0-cel het eindpunt dan wordt de 2-cel rechts gevonden. Bij het beschouwde voorbeeld (eerste stelsel (h, 3)) is 0-cel 3 het eindpunt van 1-cel h en dus wordt zoals blijkt 30 uit de figuur 1 en de tabel I de 2-cel rechts, zijnde 2-cel A gevonden.

Dezelfde methode als hiervoor beschreven kan eveneens gebruikt worden om de andere 2-cel te vinden die aan de 1-cel van het eerste stelsel grenst. Hiervoor volstaat het om de in het eerste stelsel aangegeven 0-cel te vervangen door de andere 0-cel behorende bij de 35 gegeven 1-cel en met het aldus verkregen nieuwe eerste stelsel de werkwijze te herhalen. In het geval van het voorbeeld met als eerste stelsel h,3 wordt dan 1-cel h geadresseerd. Op de geadresseerde 8701738 PHN 12.197 11 geheugenplaats is dan vermeld dat O-cel 4 de andere bij 1-cel h behorende O-cel is. Het nieuwe eerste stelsel is dan (h, 4). Eerste stelsel (hf 4) levert dan een tweede stelsel (f, 3) wat op zijn beurt een derde stelsel (g, 5) levert. Daar nu (g, 5) f (h, 4) wordt er op 5 basis van (g, 5} een verder derde stelsel (h, 4) gevonden. Daar (h, 4) = (hr 4) is de 2-cel C gevonden.

Beschouw nu opnieuw het netwerk weergegeven in figuur 3 met de bijbehorende 1-cellentabel weergegeven in tabel II. Veronderstel nu dat een 2-cel onder meer door 1-cel k begrensd, wordt gezocht. (k,10) 10 vormt in dit geval een eerste stelsel. Dat eerste stelsel levert dan een tweede stelsel (m,11), wat dan weer een derde stelsel (r,12} levert.

Daar nu {r,12) verschillend is van (k,10) moet er een verder derde stelsel worden gevormd uitgaande van het gesubstitueerde tweede stelsel (r,12). Hiervoor wordt nu geheugenplaats r geadresseerd en moet de 15 andere dan O-cel 12 behorende bij 1-cel r gekozen worden. Echter is deze andere O-cel eveneens 0- cel 12 want de eerste en de tweede O-cel van 1-cel r zijn beide identiek, namelijk O-cel 12. Dit heeft nu tot gevolg dat de keuze van genoemde andere O-cel niet éénduidig uitvoerbaar is, want zowel het stelsel (r,12) als (m,12) voldoen aan de eisen voor 20 de bepaling van het verdere derde stelsel. Echter de keuze van het stelsel (r,12) zou tot gevolg hebben dat er eindeloos in de lus r wordt gedraaid want het tweede stelsel (r,12) zou dan steeds een derde stelsel (r,12) leveren dat identiek is aan dat tweede stelsel. Op deze wijze zou de gezochte 2-cel, in dit geval 2-cel R, nooit worden gevonden.

25 Dit probleem kan echter eenvoudig worden opgelost door het invoeren van een verificatie-stap in de werkwijze voor het opzoeken van een 2-cel. Immers zulke gesloten lussen zijn, indien ze zijn opgeslagen volgens de tabel II eenvoudig herkenbaar aan het feit dat de eerste en de tweede O-cel, behorende bij zo'n 1-cel, die een lus 30 voorstelt, identiek zijn. Dat identiek zijn is eenvoudig te verifiëren, het volstaat hiervoor alleen om na het adresseren van de 1-cel, gegeven in een stelsel, te verifiëren of bij die geadresseerde 1-cel de eerste en de tweede O-cel identiek zijn. Zijn beide 0-cellen identiek, dan moet die kombinatie (O-cel, thread-35 pointer) als stelsel worden gekozen waarvan de thread-pointer een andere dan de geadresseerde 1-cel aanwijst.

Deze verificatiestap zal nu worden toegelicht aan de hand t: J I 7 3 8 PHN 12.197 12 van het gekozen voorbeeld (eerste stelsel (k,10). Bij het vormen van het derde stelsel levert de verificatiestap een negatief resultaat op want bij 1-cel m zijn de 0-cellen, 11, respektievelijk 12, verschillend van elkaar. Echter bij het vormen van het verdere derde stelsel, uitgaande 5 het gesubstitueerde tweede stelsel (r,12), wordt er na adressering van 1-cel r, bij de verificatie, vast gesteld dat eerste O-cel 12 gelijk is aan tweede O-cel 12. Deze gelijkheid heeft tot gevolg dat nu de combinatie (m,12) als verder derde stelsel dient te worden gekozen, aangezien 1-cel m, aangewezen door de thread-pointer toegekend aan de 10 tweede O-cel, verschillend is van de geadresseerde 1-cel r. Uitgaande van het gesubstitueerde tweede stelsel (m,12) wordt zodoende het verder derde stelsel (s,11) gevonden. Op deze wijze wordt er dus vermeden dat er eindeloos wordt rondgedraaid in een gesloten lus.

Het verifiëren of de eerste en de tweede O-cel behorende 15 bij eenzelfde 1-cel aan elkaar gelijk zijn, mag eveneens worden uitgevoerd bij het zoeken naar het tweede stelsel uitgaande van het eerste stelsel. Wanneer dan de in het eerste stelsel gegeven 1-cel wordt geadresseerd mag daarop volgend een verificatiestap plaats hebben. Dit is met name voordelig wanneer de op te zoeken 2-cel door een gesloten 20 lus is gevormd, zoals bijvoorbeeld de 2-cel Q omsloten door 1-cel r (figuur 3). Uitgaande van een eerste stelsel (r,12) volgt onmiddellijk uit de gegevens van 1-cel r, dat eerste en tweede nulpunt identiek zijn, zodanig dat onmiddellijk kan worden vastgesteld dat het hier om een gesloten lus gaat. Vorming van het tweede stelsel is dan niet meer 25 noodzakelijk wanneer naar 2-cel Q (2-cel rechts) wordt gezocht, aangezien de informatie direkt uit de tabel volgt.

Het gebruik van een verificatiestap is noodzakelijk indien een gesloten lus inderdaad als een 1-cel met identieke eerste en tweede aangesloten 0-cellen wordt opgeslagen. Wordt er echter een 30 virtuele O-cel in de lus aangebracht, dan ontstaat er een tabel als weergegeven in tabel III en is het probleem van identieke eerste en tweede O-cel verdwenen. Dit impliceert dan dat de verificatiestap overbodig geworden is indien virtuele 0-cellen worden gebruikt. Wanneer weer het voorbeeld met als eerste stelsel (k,10) wordt beschouwd, echter 35 nu door gebruik te maken van de tabel III, dan ontstaan de volgende tweede en derde stelsels (m, 11), (r ^, 12), (^14), (m, 12), (s,11), (v,13). Door de introduktie van de virtuele O-cel 14, die 1-cel r in de 8701738 PHN 12.197 13 deel-1-cellen en ^ verdeelt, treedt het probleem van ronddraaien in een gesloten lus bij het zoeken naar een 2-cel niet meer op, en is de verificatie overbodig geworden.

Zoals reeds vermeld zijn de hiervoor beschreven 5 werkwijzen uitermate geschikt voor gebruik in een voertuignavigatiesysteem. Enerzijds heeft de compacte wijze waarop de netwerkgegevens in het geheugen zijn opgeslagen tot gevolg dat de benodigde geheugenruimte beperkt kan blijven, wat op zijn beurt tot gevolg heeft dat leesoperatie slechs geringe tijd in beslag nemen. Dit 10 laatste is met name wanneer redelijk hoge snelheden met een voertuig worden gereden van groot belang. Anderzijds is een efficiënte methode om een 2-cel op te zoeken van wezenlijk belang bij het navigeren zelf.

Figuur 4 laat schematisch de hoofdbestanddelen van een voorbeeld van een land-voertuignavigatiesysteem zien. Het 15 land-voertuignavigatiesysteem bevat een bus 1 aan dewelke een dataverwerkende eenheid 2, bijvoorbeeld een microprocessor, is aangesloten alsook een werkgeheugen 3 en een opslaggeheugen 4. Dat opslaggeheugen is bijvoorbeeld gevormd door een optische schijf en een daarbij behorend leesorgaan. In dat opslaggeheugen zijn er 20 kaartgegevens, navigatiegegevens en andere stuurgegevens opgeslagen. Een geheugentabel zoals weergegeven in de tabellen I, II, of III is opgeslagen in geheugen 4. Aan de bus 1 zijn er verder een eerste (5) en een tweede (9) ingangs-uitgangsinterface verbonden. Aan het eerste interface 5 zijn bijvoorbeeld een elektromagnetisch kompas 6, 25 wielsensoren 7 en een kilometerteller 8 verbonden. Al deze elementen 6, 7, 8 dienen ertoe om gegevens op te nemen ten einde positiebepaling van het voertuig mogelijk te maken. Het bepalen van een voertuigpositie met behulp van een navigatiesysteem is bijvoorbeeld beschreven in het artikel "EVA-Ortnungs-und Navigationssystem für Landfahrzeuge" van 30 E.P. Neukirchner, 0. Pilsak en D. Schlögl en verschenen in

Nachrichtenzeitschrift Bd 36 (1983) Heft 4, pagina's 214-218. Daar de uitvinding geen betrekking heeft op het bepalen van de positiekoördinaten van het voertuig zal hierop verder niet in detail worden ingegaan.

35 Aan de tweede ingangs-uitgangsinterface zijn er verder een toetsenbord 10 en een weergave-element 11 aangesloten. Het toetsenbord 10 wordt onder meer gebruikt voor het opgeven van het vertrekpunt en een 8701738 PHN 12.197 14 bestemming aan het systeem. Het weergave-element 11 is bijvoorbeeld gevormd door een luidspreker en/of een televisiemonitor.

Wanneer het voertuignavigatiesysteem nu in werking is dan worden er op basis van de gegevens opgenomen door het kompas 6, de 5 wielsensoren 7 en de kilometerteller 8 en onder besturing van de microprocessor 2 telkens koördinaten bepaald die de positie van het voertuig weergegeven. Het navigatiesysteem moet nu op basis van deze positie koördinaten bepalen tot welke 0,1- of 2-cel deze positiekoördinaten behoren. Een werkwijze voor het bepalen tot welk 10 wegsegment, dus bij welke 0 of 1-cel, positie koördinaten behoren, is bijvoorbeeld beschreven in de PCT aanvrage nummer WO 86/00157. Door gebruik te maken van de aldaar beschreven werkwijze is het navigatiesysteem dus in staat om uitgaande van de positiekoördinaten een eerste stelsel te bepalen. Het navigatiesysteem is nu ook in staat 15 om, door gebruik te maken van een werkwijze volgens de uitvinding, na te gaan binnen welke 2-cel de positiekoördinaten zijn gelegen. Dit is bijvoorbeeld noodzakelijk te wanneer de positiekoördinaten te veel afwijken van een positie op de weg.

Wanneer het navigatiesysteem een door 0 en 1-cellen 20 begrensde 2-cel wenst dan zal het op basis van de positiekoördinaten een eerste stelsel leveren evenals, indien gewenst, een verzoek om zowel de 2-cel links als rechts van de in het eerste stelsel gegeven 1-cel op te zoeken.

Figuur 5 laat in de vorm van een stroomdiagram een 25 voorbeeld zien van een programma dat onder besturing van de dataverwerkende eenheid wordt uitgevoerd ten einde op basis van een aangeboden eerste stelsel een 2-cel op te zoeken uit het geheugen. De verschillende stappen van dat stroomdiagram zullen nu hieronder worden beschreven.

30 15 STRT: Dat is de start van het programma dat wordt geïnitieerd telkens wanneer een eerste stelsel worden aangeboden.

16 ST: Het eerste stelsel wordt op een voorafbepaalde plaats in het werkgeheugen opgeslagen.

17 BTH?: Hier wordt onderzocht of men beide (links en rechts) aan de 35 in het eerste stelsel aangegeven 1-cel grenzende 2-cellen wenst. Deze wens wordt door het navigatiesysteem zelf geformuleerd. Zo is het bijvoorbeeld mogelijk dat wanneer het voertuig zich in de bebouwde kom

870173S

PHN 12.197 15 bevindt altijd naar beide aangrenzende 2-cellen wordt gevraagd.

18 SFL: Voor het geval dat er naar beide aangrenzende 2-cellen wordt gevraagd, wordt er een vlag gezet in een daartoe bestemd register.

19 ADD 1C: De in het eerste stelsel gegeven 1-cel wordt nu in de 5 geheugentabel geadresseerd en de op de geadresseerde plaats opgeslagen gegevens worden opgehaald en in het werkgeheugen geschreven.

20. 26 EO 0C?; Hier wordt onderzocht of de geadresseerde 1-cel identieke eerste en tweede 0-cellen heeft. Het dient te worden vermeld dat deze stap alleen noodzakelijk is wanneer er geen gebruik 10 gemaakt wordt van virtuele 0-cellen, zoals hiervoor beschreven. In het geval dat er virtuele 0-cellen worden gebruikt vervalt deze stap evenals de hierna beschreven stappen 21 en 27.

21 RD 2C: De nieuwe 1-cel gegeven in het eerste stelsel heeft identieke eerste en tweede 0-cellen. De geadresseerde 1-cel is dus 15 een gesloten lus en de omsloten 2-cel is rechtstreeks uit de geadresseerde gegevens op te halen.

22 OPP OC: De andere 0-cel dan diegene aangegeven in het eerste stelsel en welke behoort bij de geadresseerde 1-cel, wordt geïdentificeerd.

20 23 THP; De aan genoemde andere 0-cel toegekende thread-pointer wordt opgehaald.

24 F 2ST: Het tweede stelsel wordt nu gevormd door de zojuist opgehaalde thread-pointer en door genoemde andere 0-cel.

25 ADD 2ST; De in het tweede stelsel gegeven 1-cel wordt nu in de 25 geheugentabel geadresseerd en de aldaar opgeslagen gegevens opgehaald en in het werkgeheugen geschreven.

27 TK OTH: De 1-cel gegeven in het tweede stelsel heeft identieke eerste en tweede 0-cellen. De 0-cel aan dewelke een thread-pointer is toegekend die een andere 1-cel aanwijst dan diegene gegeven in het 30 tweede stelsel wordt nu gekozen en het derde stelsel wordt gevormd door die gekozen 0-cel en de 1-cel aangewezen door de aan die gekozen 0-cel toegekende thread-pointer.

28 F 3ST: Op basis van de gegevens van het tweede stelsel wordt nu het derde stelsel gevormd.

35 29 1ST=3ST?: Dat is een test om na te gaan of het derde stelsel gelijk is aan het eerste stelsel.

30_ST_2ST: Het bij stap 24 gevormde tweede stelsel wordt in het 8701738 t PHN 12.197 16 werkgeheugen op een daarvoor gereserveerde plaats opgeslagen.

31 2ST:=3ST: Het bij stap 28 gevormde derde stelsel wordt nu tweede stelsel ten einde hiermee de stappen 25 tot 28 te herhalen.

32 F 2C: De 2-cel wordt nu gevormd op basis van de gevormde eerste, 5 tweede en derde stelsels.

33 FL?: Hier wordt er onderzocht of er bij stap 18 een vlag is gezet, welke aangeeft dat beide 2-cellen gevraagd zijn.

34 RS FL: In het geval dat de vlag gezet was, wordt deze nu teruggezet.

10 35 F CIST: Een komplementair eerste stelsel wordt er nu gevormd door, gebruik makend van de in het werkgeheugen opgeslagen gegevens van het eerste stelsel, de in het eerste stelsel aangegeven 1-cel en de andere dan de aangegeven 0-cel.

36 STP: Dat is het einde van het programma.

15 De aldus gevonden 2-cel kan nu onder besturing van de microprocessor, indien gewenst op het beeldscherm van het weergave-element worden afgebeeld. Het navigatiesysteem beschikt nu over de gegevens van de 2-cel voor het realiseren van zijn navigatietaak.

870173»

Claims

1. Werkwijze voor het digitaal opslaan van een twee dimensionaal topologisch, door middel van een verzameling 0-, 1- en 2-cellen weergegeven, netwerk in een geheugen, waarbij voor elke 1-cel ten minste één geheugenadres is voorzien waar voor die 1-cel, telkens 5 een eerste en een tweede bij die 1-cel aangesloten 0-cel wordt opgeslagen alsmede aan genoemde eerste respektievelijk tweede 0-cel een respektievelijke thread-pointer wordt toegekend die een 1-cel aanwijst welke aansluit aan de 0-cel aan dewelke hij is toegekend, met het kenmerk, dat een punt behorende tot de beschouwde 1-cel en gelegen nabij 10 de beschouwde 0-cel volgens een voorafbepaalde draairichting rond een as door de beschouwde 0-cel en nagenoeg loodrecht op het vlak van het netwerk wordt gedraaid totdat het genoemde punt samenvalt met een punt van een verdere 1-cel die aansluit aan de beschouwde 0-cel, en dat aan de beschouwde 0-cel die thread-pointer wordt toegekend die genoemde 15 verdere 1-cel aanwijst.

2. Werkwijze volgens conclusie 1, toegepast op een topologisch netwerk dat ten minste één 1-cel bevat die is gevormd door een gesloten lus, met het kenmerk, dat in een punt van een gesloten lus, welk punt verschillend is van een junctie 0-cel die de aansluiting 20 van die gesloten lus met een overige 1-cel van het netwerk aangeeft, een virtuele o-cel wordt aangebracht, en dat de gesloten lus als een eerste en een tweede deel-1-cel wordt opgeslagen waarbij de eerste respektievelijk de tweede 0-cel aangegeven bij de eerste deel-1-cel gevormd is door de junctie 0-cel respektievelijk de virtuele 0-cel en de 25 eerste respektievelijk de tweede 0-cel aangegeven bij de tweede deel-1-cel gevormd is door de virtuele 0-cel respectievelijk de junctie 0-cel.

3. Werkwijze voor het in een topologisch netwerk, in een geheugen opgeslagen volgens de werkwijze uit conclusie 2, opzoeken van de 1- en de 0-cellen die een 2-cel begrenzen, met het kenmerk, dat 30 uitgaande van een eerste stelsel gevormd door een eerste 1-cel uit het netwerk en één zijner aangesloten 0-cellen een tweede stelsel wordt gevormd door de andere 0-cel aangesloten aan genoemde eerste 1-cel te kiezen alsook de 1-cel aangewezen door de aan genoemde andere 0-cel toegekende thread-pointer, met welk tweede stelsel een derde stelsel 35 wordt gevormd door de 1-cel uit het tweede stelsel in het geheugen te adresseren en de bij die geadresseerde 1-cel aangesloten andere 0-cel dan diegene opgenomen in het tweede stelsel te nemen alsook de 1-cel 8701738 PHN 12.197 18 aangewezen door de thread-pointer toegekend aan laatstgenoemde andere 0-cel, welk derde stelsel vervolgens met het eerste stelsel wordt vergeleken en in geval van overeenkomst de gezochte 2-cel door het eerste, tweede en derde stelsel is begrensd, en in geval van niet-5 overeenkomst het tweede stelsel wordt gebufferd en vervolgens door het derde gesubstitueerd om, uitgaande van het gesubstitueerde tweede stelsel,een verder derde stelsel te vormen en dat deze operaties telkens worden herhaald totdat het eerste stelsel overeenkomt met een aldus gevormd derde stelsel.

4. Werkwijze voor het in een topologisch netwerk, in een geheugen opgeslagen volgens de werkwijze uit conclusie 1, opzoeken van de 1- en de 0-cellen die een 2-cel begrenzen, waarbij voor elke 1-cel van het netwerk de daarbij aangesloten eerste en tweede 0-cel verschillend van elkaar zijn, met het kenmerk, dat uitgaande van een 15 eerste stelsel gevormd door een eerste 1-cel uit het netwerk en één zijner aangesloten 0-cellen een tweede stelsel wordt gevormd door de andere 0-cel aangesloten aan genoemde eerste 1-cel te kiezen alsook de 1-cel aangewezen door de aan genoemde andere 0-cel toegekende threadpointer, met welk tweede stelsel een derde stelsel wordt gevormd 20 door de 1-cel uit het tweede stelsel in het geheugen te adresseren en de bij die geadresseerde 1-cel aangesloten andere 0-cel dan diegene opgenomen in het tweede stelsel te nemen alsook de 1-cel aangewezen door de thread-pointer toegekend aan laatstgenoemde andere 0-cel, welk derde stelsel vervolgens met het eerste stelsel wordt vergeleken en in geval 25 van overeenkomst de gezochte 2-cel door het eerste, tweede en derde stelsel is begrensd, en in geval van niet-overeenkomst het tweede stelsel wordt gebufferd en vervolgens door het derde gesubstitueerd om uitgaande van het gesubstitueerde tweede stelsel een verder derde stelsel te vormen en dat deze operaties telkens worden herhaald totdat 30 het eerste stelsel overeenkomt met een aldus gevormd derde stelsel.

5. Werkwijze voor het in een topologisch netwerk, in een geheugen opgeslagen volgens de werkwijze uit conclusie 1, opzoeken van de 1- en de 0-cellen die een 2-cel begrenzen, met het kenmerk, dat uitgaande van een eerste stelsel gevormd door een eerste 1-cel uit het 35 netwerk en één zijner aangesloten 0-cellen een tweede stelsel wordt gevormd door de andere 0-cel aangesloten aan genoemde eerste 1-cel te kiezen alsook de 1-cel aangewezen door de aan genoemde andere 0-cel 8701738 PHN 12.197 19 toègekende thread-pointer, en dat vervolgens de 1-cel uit het tweede stelsel in het geheugen wordt geadresseerd en uit de opgehaalde gegevens wordt onderzocht of de eerste en de tweede O-cel aangesloten bij die 1-cel identiek zijn en waarbij in het geval van identieke eerste en tweede 5 O-cel een derde stelsel wordt gevormd door de identieke O-cel te kiezen alsmede die 1-cel, aangewezen door de aan één van beide O-cellen toegekende thread-pointer, die verschillend is van de 1-cel uit het tweede stelsel, en waarbij in het geval van niet identieke eerste en tweede O-cellen het derde stelsel wordt gevormd door de bij die 10 geadresseerde 1-cel aangesloten andere O-cel dan diegene opgenomen in het tweede stelsel alsook de 1-cel aangewezen door de thread-pointer toegekend aan laatstgenoemde andere O-cel, welk derde stelsel vervolgens met het eerste stelsel wordt vergeleken en in geval van overeenkomst de gezochte 2-cel door het eerste, tweede en derde stelsel is begrensd, en 15 in geval van niet-overeenkomst het tweede stelsel wordt gebufferd en vervolgens door het derde gesubstitueerd om uitgaande van het gesubstitueerde tweede stelsel een verder derde stelsel te vormen en dat deze operaties telkens worden herhaald totdat het eerste stelsel overeenkomt met een aldus gevormd derde stelsel.

6. Werkwijze volgens conclusie 5, met het kenmerk, dat de eerste 1-cel uit het eerste stelsel in het geheugen wordt geadresseerd en dat uit de opgehaalde gegevens wordt onderzocht of de eerste en de tweede O-cel aangesloten bij de eerste 1-cel identiek zijn, en dat in het geval van identieke eerste en tweede O-cel de te zoeken 2-cel 25 diegene is die door de eerste 1-cel wordt ontsloten.

7. Werkwijze volgens een der conclusies 3, 4, 5 of 6, waarbij voor elke 1-cel telkens een aanduiding voor een eerste en een tweede 2-cel is opgenomen, met het kenmerk, dat wanneer de in het eerste stelsel aangegeven O-cel de eerste respektievelijk de tweede O-cel is 30 van de 1-cel opgenomen in het eerste stelsel, de te zoeken 2-cel door de eerste respektievelijk de tweede bij die 1-cel aangeduide 2-cel wordt weergegeven.

8. Inrichting voor het uitvoeren van de werkwijze volgens een der conclusies 3, 4, 5, 6 of 7, welke inrichting een dataverwerkende 35 eenheid en een geheugen bevat met het kenmerk, dat in het geheugen het topologisch netwerk is opgeslagen, en dat de inrichting een adresgenerator bevat voor het genereren van geheugenadressen voor het e 7 0 1 7 3 8 PHN 12.197 20 adresseren van de in de eerste en tweede stelsels aangegeven 1-cellen, en een vergelijkeenheid voor het uitvoeren van een vergelijkingsoperatie tussen genoemde eerste en derde stelsel.

9. Inrichting volgens conclusie 8, met het kenmerk, dat de 5 inrichting is opgenomen in een land-voertuignavigatiesysteem, dat voorzien is van een positiebepalingseenheid voor het bepalen van positiekoördinaten van het voertuig alsook van een omzeteenheid voor het omzetten van positiekoördinaten in een eerste stelsel. 8 7 01 7 ? β