Eliminatie van details in een topografische kaart. Herman Haverkort

Eliminatie van details in een topografische kaart

Herman Haverkort

INF/SCR-99-11 oktober 1999

Voorwoord

Geografische informatiesystemen kunnen geografische data tonen op verschillende schalen. Schaalverkleining zonder meer leidt echter niet tot een goede kaart. Objecten, of details daarvan, kunnen te klein worden om goed te worden waargenomen. Een druk en onduidelijk kaartbeeld zou het gevolg zijn. Om dit te voorkomen zal de weergave van de data moeten worden vereenvoudigd. Onbelangrijke details zullen moeten worden weggelaten, zodat ruimte ontstaat om de grote lijnen en belangrijke details duidelijk te maken. Sommige objecten zullen naar verhouding groter moeten worden getoond dan ze in werkelijkheid zijn. Dergelijke vereenvoudigingen van het kaartbeeld worden gevat onder de noemer: kaartgeneralisatie. Het doel van mijn afstudeerproject over dit onderwerp was ideeën te ontwikkelen voor een algoritme om vlakverdelingen op kaarten te generaliseren, meer in het bijzonder de vlakverdeling van de top-bestanden van de Topografische Dienst Nederland (tdn). Daarbij zou een implementatie worden gemaakt om de ontwikkelde algoritmen te testen. Deze implemenatie is echter niet tot stand gekomen. De te overwinnen technische en algoritmische problemen bleken meer tijd te vergen dan binnen het kader van dit project beschikbaar was. Het verslag beperkt zich daarom noodgedwongen tot een inleiding in de problematiek en de ideeën voor modellering en algoritmen die in de loop van dit project zijn verzameld en ontwikkeld. Het project waarover in dit werk verslag wordt gedaan, vond plaats ter afronding van mijn studie informatica aan de Universiteit Utrecht. Het project werd begeleid door Marc van Kreveld, docent/onderzoeker aan de Universiteit Utrecht, groep Toegepaste Algoritmen in het Informatica-Instituut. De probleemstelling werd ontleend aan het dagelijks werk van de Topografische Dienst Nederland (tdn). Paul van Asperen en Nico Bakker hebben mij bij de tdn rondgeleid, mij ge¨ınformeerd over de aard van het probleem, en gereageerd op de door mij voorgestelde oplossingen. Voor één van de algoritmische problemen die in dit project moesten worden opgelost, heb ik de hulp gezocht van Hans Bodlaender, docent/onderzoeker bij de groep Algoritmisch Ontwerpen van het bovengenoemde instituut. Hieruit is een gezamenlijk artikel van Hans Bodlaender en mij voortgekomen. Dit artikel is in augustus 1999 door René van Oostrum1 gepresenteerd op de Canadian Conference on Computational Geometry in Vancouver. Dank gaat uit naar alle hierboven genoemde personen voor hun bijdragen in raad en daad aan dit project.

1.

Post-doc aan de informatica-faculteit van de Hong Kong University of Science and Technology

Opzet van de scriptie

Deze scriptie bestaat uit twee delen. Het eerste deel, in het Nederlands, beschrijft het cartografische probleem in detail, inclusief een formalisatie van de aan de kaart te stellen eisen, en geeft een aantal ideeën voor (heuristische) oplosmethoden. In hoeverre deze ideeën in de praktijk van waarde zouden kunnen zijn, is echter niet goed vast te stellen zo lang geen tests hebben plaatsgevonden. In het tweede deel, in het Engels, wordt gepoogd exact te definiëren hoe smalle gedeelten in polygonen kunnen worden opgespoord, met daarbij een algoritme voor de afbakening van smalle stukken en een algoritme om polygonen geheel of gedeeltelijk op te delen onder buurvlakken. In het eerste deel ligt het accent dus op de modellering van een cartografisch probleem; in het tweede deel ligt het accent op de nauwkeurige definitie van geometrische problemen met bijbehorende algoritmen.

Eerste deel

Modellering van een cartografisch probleem

Inhoudsopgave

1 1.1 1.2 1.3 1.4 2 2.1 2.2 2.3 2.4 2.5 2.5.1 2.6 2.7 2.8 3 3.1 3.2 3.2.1 3.2.2 3.2.3 3.3 4 4.1 4.2 4.3 4.4 4.5 5

Probleemstelling en aanpak 3 Eigenschappen van de gegeven data 3 Eigenschappen van de gewenste data 3 Resultaten van eerder werk 5 Aanpak in dit project 5 Formalisatie van eisen 7 Metrieke criteria 8 Het skelet van een veelhoek 8 Minimale oppervlakte 9 Minimale lengte 10 Minimale breedte 11 Detectie van smalheid 11 Minimale tussenruimte in bebouwd gebied 12 Topologische criteria 13 Behoud van oppervlakteverhoudingen 14 Operatoren 15 Overwogen operatoren 15 Eliminatie van veelhoeken 16 Theoretische criteria 16 Benadering met een Steiner-boom 17 Behandeling van eilanden 18 Eliminatie van delen van veelhoeken 18 Toepassing van de criteria en operatoren 19 Inlezen en integratie van data in NEN-formaat 19 Provisorische eliminatie van lijnen en wegen 19 Volgorde van verwerking van details, balancering 20 Terminatie-garantie 22 Kwaliteits-garantie? 23 Conclusies 25

modellering van een cartografisch probleem

1

INHOUDSOPGAVE

2


Hoofdstuk 1 Probleemstelling en aanpak

In dit hoofdstuk wordt beschreven waardoor de te generaliseren data worden gekenmerkt, wat we globaal verwachten van het resultaat van de generalisatie, en welke beperkingen van eerder werk wij hopen te overwinnen.

1.1

Eigenschappen van de gegeven data

Uitgangspunt is in principe een verzameling punten (b.v. telefooncellen), lijnen (wegen enz.), vlakverdelingen en contourlijnen, allen gevat in een datastructuur waarin geometrie, topologie en tot op zekere hoogte semantiek zijn geregistreerd. Merk op dat meerdere vlakverdelingen tegelijkertijd op een kaart kunnen worden getoond, bijvoorbeeld door kleur, arcering en/of symbolen te combineren. In dit project richten we ons echter uitsluitend op het generaliseren van één vlakverdeling. Daarbij zouden we er rekening mee moeten houden dat er beperkingen kunnen worden opgelegd door topologische en semantische relaties met punten, lijnen en gegevens in andere vlakverdelingen. In de praktijk zou het te ver voeren om binnen het beperkte kader van een afstudeerproject met al deze relaties rekening te houden. In dit project wordt dan ook uitsluitend naar een vlakverdeling gekeken. In concreto hebben we geprobeerd een algoritme uit te werken dat kon worden getest op delen van de vlakverdeling die is gedefinieerd in de top-vectorbestanden van de Topografische Dienst. In deze bestanden wordt een verzameling lijnen en veelhoeken gedefinieerd die zijn geclassificeerd door middel van vijfcijferige codes. In de topbestanden is het eerste cijfer per definitie 0. Het laatste cijfer dient niet ter bepaling van de klasse, maar om aan te geven bij welk object de betreffende klasse-aanduiding hoort. Dit cijfer zal in de rest van dit verslag worden genegeerd. In dit verslag zullen groepen klassen worden aangeduid door zoveel cijfers van de code te geven als nodig is om de klasse te onderscheiden. Met “03” worden dus de klassen 0300 t/m 0399 bedoeld; het vijfde cijfer wordt buiten beschouwing gelaten.

1.2

Eigenschappen van de gewenste data

Dit project was in eerste instantie vooral gericht op een zodanige generalisatie dat men een goede kaart op schaal 1:50.000 kan maken, uitgaande van een bestand dat oorspronkelijk was gemaakt voor kaarten op 1:10.000. Uitgangspunt is dat alle modellering van een cartografisch probleem

3

HOOFDSTUK 1. PROBLEEMSTELLING EN AANPAK

informatie die in de oorspronkelijke vlakverdeling aanwezig is moet worden getoond, voor zover het lukt om desondanks een goed kaartbeeld te krijgen. Er wordt dus aangenomen dat eventuele selectie/vereenvoudiging van gegevens, gericht op een bepaald doel van de kaart, reeds heeft plaatsgevonden. In dit project wordt er ook geen rekening meegehouden dat het grondgebruik op de kaarten met schaal 1:50.000 anders in klassen wordt ingedeeld. Ons uitgangspunt is “slechts” dat van de in top beschikbare gegevens zo veel mogelijk op een goede manier op een bepaalde, kleinere schaal moet worden getoond. De uitvoer dient in zijn meest elementaire vorm een vlakverdeling te zijn die zo veel mogelijk voldoet aan een aantal eisen (zie ook [13]). 1.

2.

3.

4.

5.

Metrieke eisen, zoals minimumbreedte, minimumafmetingen van details, handhaven van nabijheidsrelaties tussen vlakken, plaatsvastheid van sommige soorten data. Behoud van topologische relaties, zoals het feit dat een bepaald vlak een bepaald punt bevat, dat bepaalde vlakken aan elkaar grenzen of juist niet, dat bepaalde omtrekken samenvallen met bepaalde lijnen. Behoud van semantische relaties via afleiding van metrieke eisen, topologische relaties en het al dan niet toestaan van bepaalde soorten operaties. Denk hierbij onder meer aan de oriëntatiewaarde van bepaalde objecten in het landschap, de barrière- of doorgangsfunctie die sommige gebieden kunnen hebben enz. Behoud van voorkomen: behoud van hoekig/rond karakter, behoud van orthogonaal/diagonaal karakter, behoud van oppervlakteverhoudingen tussen verschillende soorten vlakken, behoud van patronen. Monotoonheid: objecten die op een kaart met kleine schaal worden getoond, moeten ook worden weergegeven op elke grotere schaal.

Gezien de beperkte omvang van het project zullen we slechts een (zeer) beperkt aantal generalisatie-operatoren kunnen uitwerken, waarmee zeker niet aan alle eisen zal worden voldaan. Harde garanties kunnen hoe dan ook moeilijk worden gegeven, omdat er voor elke structuur een schaal zal bestaan waarop deze niet meer duidelijk kan worden gegeven, zodat topologie, metriek, semantiek en/of voorkomen min of meer ingrijpend moeten worden veranderd. Om de algoritmen bruikbaar te kunnen maken voor interactieve toepassingen, zouden ze aan minstens een van de volgende eisen moeten voldoen. 1.

2.

Uit praktijktesten en theoretische analyse blijkt dat het algoritme snel werkt; bij voorkeur kan het algoritme meer of minder kwaliteit leveren naar gelang de beschikbare hoeveelheid tijd. De uitvoer bestaat uit een (hiërarchische) datastructuur van beperkte omvang die kan worden gebruikt om in interactieve toepassingen real-time in en uit te zoomen op een deelgebied van de kaart.

In dit project hebben we ons echter vooral gericht op de kwaliteit van de uitvoer, in beperkte mate op snelheid, en niet op structuur. De manier waarop we in dit project de aan de kaart te stellen eisen hebben geformaliseerd, en de operatoren die we hebben ontwikkeld om de kaart meer met deze eisen in overeenstemming te brengen, zullen wellicht ook (deels) bruikbaar zijn in interactieve toepassingen. De manier waarop wij bepalen wanneer er wordt getoetst en wanneer een operator wordt toegepast, lijkt daarover echter ongeschikt. 4


1.3. RESULTATEN VAN EERDER WERK

1.3

Resultaten van eerder werk

In het kader van een afstudeerproject als dit, is het helaas moeilijk om de tijd te nemen om echt grondig kennis te nemen van hetgeen eerder op dit gebied is gedaan. Zouden we daar wel de tijd voor hebben genomen, dan zou het project vanwege de beperkte tijd tot een literatuurstudie beperkt hebben moeten blijven. Niettemin hebben we van diverse overzichten en onderzoeken kennis genomen, o.a. [1, 2, 7, 8, 12, 13]. In het algemeen valt op dat men zich concentreert op hetzij een algemeen raamwerk om generalisatie-operatoren in te plaatsen, hetzij de ontwikkeling van algoritmen om de kaart zeer plaatselijk te bewerken. Met alleen een raamwerk komt men er niet, met het over de hele kaart toepassen van één soort plaatselijke bewerking evenmin. Op het gebied van de operatoren valt nog heel veel te onderzoeken. Bij gebrek aan een goede modellering van het probleem, is echter ook niet geheel duidelijk welke operatoren nodig zijn. Onderzoek naar een geschikt raamwerk blijft in zekere zin giswerk, zo lang raamwerken niet goed kunnen worden getest bij gebrek aan goede operatoren. Daarbij komt dat niet al het onderzoek dat in het buitenland wordt gedaan, voor de Nederlandse situatie relevant en bruikbaar is. De tradities met betrekking tot het “stileren” van een kaart verschillen immers van land tot land. Het is onmogelijk om deze problemen binnen een afstudeerproject volledig te analyseren en integraal aan te pakken. De invalshoek van dit project was dan ook om een beperkt aantal operatoren uit te proberen, zodat we zouden kunnen beoordelen in hoeverre daarmee al een redelijk resultaat kan worden behaald en in welke situaties toch meer operatoren nodig zijn. Het afstudeerwerk van Judith van Putten [9], ook bij het informatica-instituut van de Universiteit Utrecht, diende daarbij in zekere zin als vergelijkingsmateriaal. Zij heeft experimenten gedaan waarin te kleine vlakjes op de kaart in hun geheel aan buurvlakken werden toegevoegd. Beperkingen van deze experimenten bleken de volgende. • •

Er is geen “oog voor detail”: te kleine details aan grote vlakken blijven bestaan; Het resultaat is erg afhankelijk van de manier waarop de vlakken voor aanvang van de generalisatie zijn opgedeeld. Dit is nog verdedigbaar, waar de initiële opdeling een zekere betekenis heeft. Het is al moeilijker verdedigbaar, als die betekenis op schaal 1:50.000 niet relevant is, en eigenlijk niet verdedigbaar, wanneer de initiële opdeling slechts om technische redenen plaatsvond (bijvoorbeeld beperking van het aantal hoeken per vlakje, of eilandverbinders).

Daarnaast zien we in de resultaten dat goede tuning kennelijk niet echt is gelukt, maar het is niet duidelijk of dat inherent is aan de gekozen aanpak.

1.4

Aanpak in dit project

In dit project hebben we geprobeerd om een en ander in ieder geval zo aan te pakken, dat de kwaliteit van het resultaat niet wordt beperkt door de initiële opdeling waar de grenslijnen in die opdeling geen betekenis hebben op schaal 1:50.000. Verder modellering van een cartografisch probleem

5

HOOFDSTUK 1. PROBLEEMSTELLING EN AANPAK

Figuur 1.1: Wanneer je de oorspronkelijke opdeling van vlakken handhaaft, kunnen bij de generalisatie rare uitsteeksels ontstaan die de verdere generalisatie verstoren. wilden we ook details aan grote vlakken beschouwen, ook als die in het oorspronkelijke bestand niet als apart vlak zijn afgebakend. Afbakening van deze details was in dit project dus een van de belangrijkste onderzoeks-onderwerpen. Allereerst hebben we geprobeerd een indruk te krijgen van de metrieke, topologische en andere eisen waaraan de generalisatie moet voldoen. Deze eisen zijn geformaliseerd zoals in het volgende hoofdstuk wordt beschreven. Ten tweede werden enkele operatoren ontworpen waarmee kan worden geprobeerd de kaart meer in overeenstemming met de geformuleerde eisen te brengen. Daarbij hoort een procedure om vast te stellen waar en wanneer de operatoren moeten worden toegepast. We hadden gehoopt tenslotte een implementatie te kunnen maken om de ontwikkelde formalisaties en algoritmen te kunnen testen. Dit is helaas niet gelukt, doordat sommige technische problemen bij de implementatie zo veel tijd vergden, dat het niet haalbaar bleek om binnen dit project een werkende implementatie te krijgen. Deze scriptie beperkt zich dus noodzakelijkerwijs tot een beschrijving van de ontwikkelde ideeën voor formele criteria en algoritmen.

6


Hoofdstuk 2 Formalisatie van eisen

Om tot de formulering van concrete metrieke en topologische criteria voor een goede generalisatie te komen, heb ik wetenschappelijke literatuur over generalisatie, handboeken van de Topografische Dienst Nederland en van buitenlandse diensten (zie literatuurlijst) en medewerkers van de tdn geraadpleegd. Hierbij viel onder meer op, dat de wijze van generalisatie voor een deel wordt bepaald door tradities die van land tot land verschillen. De tdn legde uit, dat de traditie deels ook wordt bepaald door de technische mogelijkheden waarmee men het tot nu moet doen. Een andere wijze van generalisatie hoeft niet verkeerd te zijn. Anderzijds is het toch wenselijk dat automatisch gegeneraliseerde kaarten aansluiten bij de traditie, zodat gebruikers van de kaarten weten hoe ze die moeten interpreteren. Een verschil in traditie betreft in ieder geval het gebruik van typering. In sommige buitenlandse tradities is het gebruikelijk om bijvoorbeeld bebouwing tot op tamelijke kleine schalen als losse gebouwen te blijven weergeven. Op deze kleine schalen is het niet meer mogelijk om elk gebouw weer te geven. Er wordt dan een patroon van gebouwen weergegeven dat min of meer hetzelfde karakter als het werkelijke patroon heeft. Zo wordt een straat met vier huizen op gelijke afstand bijvoorbeeld vervangen door een straat met drie huizen op gelijke afstand. Het gevolg van deze wijze van generaliseren is, dat soms dingen worden weergegeven op plaatsen waar ze in werkelijkheid niet staan. In het hierboven genoemde voorbeeld, staat het middelste van de drie huizen op een plaats die in werkelijkheid tussen het tweede en het derde van de vier huizen valt. Bij de tdn geeft men er de voorkeur aan, dit soort situaties op een andere manier op te lossen, bijvoorbeeld door twee van de vier huizen weer te geven op hun werkelijke locatie en de andere twee weg te laten, of door er een huizenrijtje van te maken. Met andere woorden: alles wat op de kaart staat moet in werkelijkheid op exact die plaats aanwezig zijn, tenzij opschuiven onvermijdelijk is (zoals langs wegen). Voor de algoritmisch ontwerper is dit in zoverre prettig, dat niet al te “fuzzy” operatoren mogen en moeten worden gebruikt, en dat de noodzakelijke veranderingen op de kaart vrij locaal kunnen worden bepaald. De juiste weergave van bijvoorbeeld een huis hangt nog wel af van de directe buren, maar wordt niet of nauwelijks be¨ınvloed door structuren die zich op de kaart enkele millimeters verderop bevinden. modellering van een cartografisch probleem

7

HOOFDSTUK 2. FORMALISATIE VAN EISEN

Figuur 2.1: Voorbeeld van typering. Vier huizen op gelijke afstand worden bij schaalverkleining vervangen door drie huizen. Hierbij staat het middelste van de drie huizen op de kaart op een plaats die in werkelijkheid tussen twee huizen in valt.

2.1

Metrieke criteria

Aan de hand van het generalisatie-handboek van de tdn, is besloten dat veelhoeken op de kaart moeten worden getoetst op minimium-lengte, minimum-breedte en minimum-oppervlakte. Veelhoeken die niet voldoen aan criteria voor minimumlengte of -oppervlakte, zullen in hun geheel als “te klein” worden aangemerkt en dus moeten worden geschrapt of verduidelijkt. De breedte van een veelhoek kan echter variëren naar gelang de plaats waar wordt gemeten. Binnen een veelhoek die niet aan minimumbreedte-criteria voldoet, zullen alleen de te smalle gedeelten als “te klein” worden aangemerkt, terwijl de gedeelten die breed genoeg zijn, in principe ongewijzigd kunnen blijven. Voor de bepaling van lengte en breedte wordt gebruik gemaakt van het “skelet” van de veelhoek.

2.2

Het skelet van een veelhoek

Als skelet van een veelhoek wordt een variant van de medial axis gebruikt. Deze kan worden gedefinieerd als het Voronoi-diagram van de randen en hoekpunten van de veelhoek, voorzover dat binnen de veelhoek ligt. Dit skelet bestaat uit (zie fig. 2.2): • • • •

8

lijnstukken die midden tussen twee lijnstukken of twee hoekpunten van de omtrek van het vlak liggen (rood); vanuit elke convexe hoek van de omtrek: een bisector (groen); vanuit elke concave hoek op de omtrek: loodlijnen op de lijnstukken die elkaar in die hoek ontmoeten (geel); paraboolstukken die midden tussen een lijnstuk en een hoekpunt van de omtrek van het vlak liggen (blauw). modellering van een cartografisch probleem

2.3. MINIMALE OPPERVLAKTE

Figuur 2.2: Voorbeeld van een vlakje met skelet.

Figuur 2.3: Een concaaf hoekpunt omgewerkt tot twee hoekpunten, zodat de in de hoek samenkomende edges van de medial axis van elkaar worden gescheiden. De loodlijnen vanuit een concave hoeken, worden geacht elkaar niet te raken. Dit wordt in algoritmen en datastructuren gerealiseerd door het concave hoekpunt v tussen randen (u, v) en (v, w) te vervangen door twee hoekpunten vu en vw en een rand (vu , vw ) met lengte 0. Daarbij wordt de rand (u, v) vervangen door (u, vu ), de loodlijn (v, u′ ) ⊥ (v, u) door (vu , u′ ), de rand (v, w) door (vw , w) en de loodlijn (v, w′ ) ⊥ (v, w) door (vw , w′ ). Het skelet van een veelhoek zonder gaten is nu een boom, zoals uitgelegd in afdeling 6.1 van het tweede deel van de scriptie. Als de veelhoek n hoekpunten heeft, dan heeft het skelet eveneens O(n) knopen en randen, en de veelhoek met skelet ook. De medial axis heeft immers complexiteit O(n), en er worden niet meer dan O(n) knopen en lijnen toegevoegd in de concave hoeken. Het skelet kan voor veelhoeken zonder gaten worden berekend in O(n) tijd met het algoritme van Chin, Snoeyink en Wang [3]. Voor veelhoeken met gaten zou een aangepaste versie van Fortunes sweepline-algoritme voor Voronoi-diagrammen kunnen worden gebruikt [4].

2.3

Minimale oppervlakte

Bepaling van miminum-oppervlakte kan volgens standaard-algoritmen geschieden. Aan de hand van het generalisatiehandboek zijn de volgende minimum-oppervlakten modellering van een cartografisch probleem

9


Figuur 2.4: De lengte van een vlakje volgens de skelet-methode. voor diverse klassen objecten vastgesteld. minimumoppervlaktes klasse omschrijving 0 (verstekwaarde) 01 bebouwing 02 hoofdwegen 03 overige wegen 0390 parkeerterrein 06 water 0651 aanlegsteiger > 2m

mm2 2,0 0,1 0,0 0,0 2,0 1,0 0,1

Omdat generalisatie van wegennetwerken buiten dit project valt, wordt voor wegen een minimum-oppervlakte van 0 aangehouden, zodat ze feitelijk niet op minimumoppervlakte worden getoetst.

2.4

Minimale lengte

In vergelijking met de criteria voor minimumoppervlakte en minimumbreedte, lijkt de minimumlengte relatief onbelangrijk. In het generalisatie-handboek vond ik alleen voor klasse 0651 (aanlegsteigers > 2m) een minimumlengte (1mm op de kaart). Voor de overige klassen lijkt een minimumlengte van 0,4mm redelijk. minimumlengtes klasse omschrijving 0 (verstekwaarde) 02 hoofdwegen 03 overige wegen 0390 parkeerterrein 0651 aanlegsteiger > 2m

mm 0,4 0,0 0,0 0,4 1,0

Implementatie van een minimumlengte-criterium vereist een formele definitie. Een mogelijke definitie die ook makkelijk te implementeren is, is deze: de lengte van een vlakje is de grootst mogelijke afstand tussen twee “uiterste” punten op het skelet van de veelhoek, waarbij afstand is gedefinieerd als het korste pad in het skelet dat beide punten verbindt (zie fig. 2.4). Bij een veelhoek zonder gaten, is het skelet een boom, en zijn de uiterste punten altijd bladeren van die boom (d.w.z. hoekpunten van de veelhoek). De afstand tussen de uiterste punten is dan de diameter van een gewogen graaf in boomvorm, en kan in O(n) tijd worden gevonden (n het aantal knopen van de omtrek). Een manier 10


2.5. MINIMALE BREEDTE

om dit te implementeren, is voor alle edges van de medial axis de beide medial axis depths te berekenen zoals in afdeling 4.2 van het tweede deel van de scriptie, per edge de gevonden medial axis depths en de lengte van de betreffende edge bij elkaar te tellen, en de grootste gevonden waarde te rapporteren. Bij een veelhoek met gaten kunnen de uiterste punten ook midden op een lijnstuk of paraboolstuk van het skelet liggen. Bij een veelhoek met gaten blijkt echter ook een zwakte in deze definitie van lengte: de lengte van een veelhoek kan volgens deze definitie veranderen door het toevoegen van een punt op de rand van de veelhoek, waarbij de geometrie niet verandert. Met andere woorden: de lengte hangt niet uitsluitend af van de vorm van de veelhoek. Een mogelijke definitie die dit bezwaar niet kent is de geodesische diameter, ofwel de lengte van de kortste route binnen de veelhoek tussen twee punten in de veelhoek die zover mogelijk van elkaar vandaan liggen. Deze diameter is echter lastiger te berekenen dan de lengte over de medial axis, doordat de kortste route mogelijk om concave hoeken of gaten heen moet buigen. Als we geen rekening houden met punten die midden op een lijnstuk of parabooldeel van het skelet liggen, dan kan de lengte van een veelhoek volgens de skeletmethode worden bepaald, door de korste paden tussen alle knopen van het skelet te berekenen, en de lengte van het langste gevonden pad te rapporteren. Aangezien het aantal knopen in het skelet O(n) is (zie afdeling 2.2), kan dit bijvoorbeeld met behulp van Dijkstra’s algoritme in tijd O(n2 log n), maar een snellere oplossing is voor zover ons bekend niet uitgesloten.

2.5

Minimale breedte

Het belangrijkste geometrische criterium in het kader van dit project is breedte. Waar een veelhoek niet breed genoeg is, liggen de randen zo dicht bij elkaar dat ze moeilijk te onderscheiden zijn. Uit het generalisatie-handboek van de tdn kunnen voor diverse klassen gebieden diverse minimumbreedte-eisen worden afgeleid, soms afhankelijk van de klassen van buurgebieden. Om veelhoeken aan deze criteria te kunnen toetsen, moeten we een manier vinden om vast te stellen of, en zo ja waar, een veelhoek te smal is. We moeten hierbij aantekenen, dat het voorstel dat in dit project is ontwikkeld, beslist niet “definitief” is. Je zou je onder meer kunnen afvragen, of niet op zijn minst in sommige omstandigheden de mate waarin de omtreklijn, getekend met een bepaalde dikte, met zichzelf samenvalt, een belangrijker criterium is dan de breedte van de veelhoek. Voor ideeën daarover verwijzen we naar [6]. 2.5.1 Detectie van smalheid Om smalheid vast te stellen, hebben we ten eerste een exacte definitie van smalheid nodig, en ten tweede een algoritme waarmee we kunnen vaststellen waar in een veelhoek van smalheid sprake is en we deze gedeelten kunnen afbakenen. Vanwege het zeer technische karakter hiervan, heb ik de exacte definitie en het algoritme uitgewerkt in het tweede, Engelstalige deel van deze scriptie. Globaal stellen we ons voor, dat we cirkels met een doorsnede van maximaal een bepaalde minimum-breedte door de veelhoek laten rollen. Waar zulke cirkels raken modellering van een cartografisch probleem

11


aan twee punten op de omtrek, is het te smal, tenzij de cirkel vastzit in een relatief stompe hoek. Dat laatste is het geval als de lengte van de diepste tak van het skelet, die vanaf het middelpunt van de cirkel tussen de twee raakpunten doorgaat, korter is dan de cirkeldiameter (eventueel vermenigvuldigd met een constante factor). De minimummaten hangen af van de klasse van de veelhoek zelf en van de klasse van de in de raakpunten aangrenzende vlakken. De te gebruiken minimummaten zijn: minimumbreedtes klasse omschrijving 0 (verstekwaarde) 0 (verstekwaarde) 01 bebouwing 02 hoofdwegen 03 overige wegen 0390 parkeerterrein 06 water

aangrenzende vlakken 01, 02, 03 04, 05, 06, 07, 08 0 (alle) 0 (alle) 0 (alle) 0 (alle) 0520, 0521, 0524, 0525, 0621

mm 0,2 0,4 0,3 0,0 0,0 0,4 0,3

Tussen 01, 02 en 03 komt neer op: tussen bebouwing en wegen. Tussen 04, 05, 06, 07, 08 komt neer op: in alle overige gevallen. Tussen 0520, 0521, 0524, 0525 en 0621 komt neer op: in open terrein.

2.6

Minimale tussenruimte in bebouwd gebied

Het is twijfelachtig of bebouwd gebied, zoals de tdn dat pleegt aan te geven, vanzelf tot stand komt door het verwijderen van te klein groen enz. tussen bebouwing. Het is niet gebruikelijk om op kaarten met een kleine schaal tuinen aan te geven die vanaf de openbare weg niet of nauwelijks zichtbaar zijn. Daarom zou de volgende bebouwd-gebied-analyse kunnen worden geprobeerd. Als een gebied deels wordt begrensd door bebouwing, wordt er een graaf gebouwd waarin de knooppunten staan voor: • • •

als smal ge¨ıdentificeerde delen in het vlak (gearceerd in fig. 2.5); bebouwing om of in het vlak (0100 huizen en 0101 bebouwd gebied) (oranje); delen van de omtrek waar de afstand tussen bebouwing langs de rand van het vlak kleiner is dan de minimumbreedte tussen bebouwing (lijnen met stip erop).

Knooppunten worden met elkaar verbonden als de bijbehorende gebieds- of omtrekdelen aan elkaar grenzen. Alle gesloten kringen in deze graaf vertegenwoordigen delen van het vlak die vrijwel volledig zijn omsloten door bebouwing. Elk omsloten deel worden onderzocht: als het nergens breder is dan het bebouwdgebied-criterium (bijvoorbeeld 0,8mm), dan wordt het als te klein aangemerkt. Of de maximumbreedte hooguit 0,8mm is, wordt getest door het skelet van het gebied te bepalen, en na te gaan of een van de knooppunten van het skelet meer dan de halve maximumbreedte van de rand ligt. Of deze aanpak werkelijk zinvol is, zou uit praktijktesten moeten blijken. 12


2.7. TOPOLOGISCHE CRITERIA

Figuur 2.5: Een bebouwd-gebied-analyse voor het groene vlak. Oranje blokken stellen bebouwing voor. Gearceerde stukken zijn als te smal aangemerkt. De delen van de omtrek waar een stip op staat, geven aan waar bebouwing langs de rand dicht bij elkaar ligt. De gele lijnen geven een gesloten kring in de graaf aan. Deze kring vertegenwoordigd het geel gearceerde stuk. Als dat nergens breder is dan 0,8mm, zal het als te smal worden aangemerkt.

2.7

Topologische criteria

In het algemeen geldt dat topologische relaties tussen verschillende objecten op de kaart ongewijzigd moeten blijven. Met andere woorden: gebieden die aan elkaar grenzen, moeten aan elkaar blijven grenzen; gebieden die in elkaar liggen, moeten in elkaar blijven liggen, enz. In de praktijk worden de topologische relaties tussen objecten op de kaart vaak gerealiseerd door vormen die op kleinere schalen niet meer aan de metrieke criteria voldoen. Objecten worden bijvoorbeeld van elkaar gescheiden door te smalle tussenruimten, of grenzen aan elkaar dankzij te kleine uitsteeksels. In dergelijke gevallen moet een keuze worden gemaakt tussen enerzijds het verduidelijken van de relatie door de tussenruimten of verbindingen te verbreden, en anderzijds het schrappen van te kleine details met als gevolg een verandering van de topologie. Wat de voorkeur heeft, hangt af van de betekenis van de tussenruimte of verbinding. Wanneer deze een verbindingsfunctie of een barrièrefunctie heeft, verdient verduidelijking de voorkeur. Het vaststellen of een gebied een verbindings- of barrièrefunctie heeft die moet worden gehandhaafd, vereist het vermogen om een netwerk te generaliseren. Dat valt echter buiten het bestek van dit project. Daarom zouden we er in dit project voor kiezen om wegen te handhaven of te verwijderen op basis van hun classificatie in de tdn-data. Een andere reden om details en tussenruimten te handhaven en te verduidelijken, kan liggen in de oriëntatiewaarde van een object. Deze is in ieder geval hoog voor objecten die uniek zijn in hun omgeving, en voor objecten langs wegen en andere lijnen in het landschap. modellering van een cartografisch probleem

13


2.8

Behoud van oppervlakteverhoudingen

Om het karakter van een gebied zo veel mogelijk te behouden, verdient het aanbeveling te zorgen dat de oppervlakteverhoudingen tussen verschillende soorten grondgebruik in een bepaald gebied zo weinig mogelijk worden aangetast. Hoe dit zou kunnen, wordt aangegeven in afdeling 4.3.

14


Hoofdstuk 3 Operatoren

Om te zorgen dat een kaart na verkleining van de schaal zo veel mogelijk voldoet aan de eisen die in het vorige hoofdstuk zijn geformuleerd, moeten bewerkingen ofwel operatoren op de kaart worden toegepast. Dit kunnen operatoren zijn die de gehele kaart in één keer aanpakken (globale operatoren), of operatoren die één object en zijn directe omgeving aanpassen (locale operatoren). Aangezien de eerste soort moeilijk te definiëren is en de complexiteit ervan moeilijk in de hand kan worden gehouden, beperken we ons tot locale operatoren.

3.1

Overwogen operatoren

We hebben overwogen om de volgende operatoren uit te werken: • • •

• •

het plaatselijk of geheel vergroten van vlakken (leidend tot het verplaatsen en plaatselijk verkleinen van andere); het verwijderen van vlakken, d.w.z. het samenvoegen met andersoortige buurvlakken of opdelen onder buurvlakken; het breken van vlakken waar ze te smal zijn: dit komt feitelijk neer op opdelen in drie of meer stukken, waarvan minstens twee grote die blijven bestaan, en minstens één kleine ertussenin, die wordt verwijderd; samenvoegen van aan elkaar grenzende vlakken met dezelfde classificatie; het tegen elkaar schuiven van dicht bij elkaar liggen vlakken met dezelfde classificatie, leidend tot het verwijderen van de tussenruimte en het plaatselijk vergroten van omliggende vlakken.

De eerste operatie is veruit de meest complexe. Het plaatselijk of geheel vergroten van een vlak, heeft consequenties voor omliggende vlakken. Deze consequenties hoeven niet beperkt te blijven tot de directe buren, maar kunnen ook doorwerken in “overburen”, eilanden binnen buren enz. Onze inschatting was, dat dit probleem te complex zou zijn om naast het andere werk in dit project aan te kunnen pakken; deze operator is daarom niet uitgewerkt. De tweede en de derde zijn wel uitgewerkt en worden in de rest van dit hoofdstuk verder behandeld. De vierde is een bijzonder geval. Wanneer de vlakken in de vlakverdeling in principe worden weergegeven zonder de omtrek te accentueren, dan heeft het samenvoegen van soortgelijke, aan elkaar grenzende vlakken geen enkele invloed op het kaartbeeld. modellering van een cartografisch probleem

15

HOOFDSTUK 3. OPERATOREN

Het is dan eigenlijk een non-operator. In de Nederlandse topografische kaarten is dit doorgaans het geval. Omtrekken worden geaccentueerd tussen vlakken van verschillende klassen, en wanneer de grenslijn een eigen betekenis heeft, bijvoorbeeld als hek of sloot. In het laatste geval is de grenslijn echter met haar eigen betekenis opgenomen in het bestand en kan zij in zeker opzicht beter worden gezien als onderdeel van een lijnenpatroon, dan als vlakgrens. Generalisatie van lijnenpatronen valt buiten het bestek van dit project. Dat betekent dat aan elkaar grenzende vlakken van dezelfde klasse in dit project als één geheel kunnen worden beschouwd, behalve wanneer zij worden gescheiden door een grenslijn die vanwege haar betekenis op de kleinere schaal behouden moet blijven. Omdat generalisatie van deze lijnen buiten het bestek van dit project valt, zal een vuistregel worden gebruikt om de te behouden grenslijnen te selecteren op basis van hun classificatie. De vijfde operator, het tegen elkaar schuiven van vlakken, is ook niet uitgewerkt, om soortgelijke redenen als de eerste. Het verwijderen van tussenruimte zonder de omliggende vlakken te verschuiven, is echter een speciaal geval van de tweede of derde operator, en is daarmee wel uitgewerkt.

3.2

Eliminatie van veelhoeken

3.2.1 Theoretische criteria Wanneer we een gebiedje uit de kaart verwijderen, moet de vrijkomende oppervlakte aan buurgebieden worden toegevoegd. Anders zou er een gat in de kaart ontstaan. Het doel van de verwijdering is in zekere zin het plaatselijk reduceren van de mate van detail, opdat het kaartbeeld duidelijker wordt. In dit project is geen onderzoek gedaan naar een goede maat voor detail, of “kaartdrukte”, maar men zou bijvoorbeeld kunnen overwegen de totale lengte van de grenslijnen binnen een of andere eenheidscirkel als maat voor detail te nemen. Op grond van deze overweging, zouden we bij het verwijderen van een veelhoek de opdeling onder buurvlakken het liefst zo doen, dat de totale lengte van de nieuwe grenzen zo klein mogelijk is. Dit zou een zekere garantie geven dat verwijdering van de veelhoek inderdaad tot vereenvoudiging van het kaartbeeld leidt, en niet tot de introductie van merkwaardig gevormde uitsteeksels aan de buurvlakken. Enige beperkingen zijn wel wenselijk: zo zal men wil liever willen vermijden dat land aan water wordt toegevoegd, of andersom. Liever wordt het vlak opgedeeld onder buurvlakken die toch min of meer soortgelijk zijn. Per klasse zou men eerst moeten zoeken naar buren die min of meer soortgelijk zijn, dan naar buren die iets minder verwant zijn, en tenslotte naar andere buren. Voor de hand liggende voorkeuren zouden de volgende kunnen zijn: 16


3.2. ELIMINATIE VAN VEELHOEKEN

Aggregatievoorkeuren klasse 1e keus 2e keus 01 01 05

3e keus 06

4e keus 02 03

5e keus

0340 0343 0347 0360 0390

0520 0521 0524 0525 02 03

050

050

052 053 06

052 053 06

0

0520 0521 0524 0525 05

05

01

06

01

06

05

01

06

02 03 02 03

05

01

02 03

In woorden: • bebouwing bij bebouwing; als dat niet kan, bij vegetatie; als dat niet kan, bij water; als dat niet kan, bij wegen; • wegen van lage klasse bij open ruimte; anders bij ander grondgebruik; • parkeerterrein bij wegen; open ruimte; vegetatie; bebouwing; water; • bos bij bos; vegetatie; bebouwing; water; wegen; • overige vegetatie bij overige vegatie; bos; bebouwing; water; wegen; • water bij water; vegetatie; bebouwing; wegen. NB Generalisatie van wegennetwerken valt buiten het bestek van dit project. In het kader van dit project is verwijdering van wegen (klasse 02 en 03) alleen aan de orde als provisorische voorbereiding van de invoer. 0390 staat voor parkeerterreinen. Bij het opdelen van gebieden, mogen geen delen worden toegevoegd aan vlakken die aan de andere kant van een belangrijke lijn in het landschap liggen, bijvoorbeeld een spoorlijn. Voor het opdelingsalgoritme betekent een en ander in feite, dat sommige van de oorspronkelijke grenzen in de nieuwe grenzen behouden moeten blijven. 3.2.2 Benadering met een Steiner-boom Omdat de hierboven bedoelde “minimale sneden” moeilijk te berekenen zijn (en voor zover bekend ook niet in polynomiale tijd), stellen we voor om eerst te experimenteren met de volgende beperking: de nieuwe grenzen moeten op de plaats van de omtrek en het skelet van het op te delen vlakje liggen. Het skelet wordt voor dit doel uitgebreid met extra lijnen die loodrecht aansluiten op de middens van de zijden en met extra lijnen (bisectoren) vanuit concave hoeken in de omtrek (zie figuur 6.2 in het tweede deel van de scriptie). We zoeken dan de opdeling van het vlakje onder buurvlakken, met de eigenschap dat de nieuwe grenzen een deelverzameling zijn van dit netwerk van omtrek en skelet, en binnen dat kader een zo kort mogelijke totale lengte hebben. Met deze beperking weten we hoe we voor vlakken zonder eilanden de nieuwe grenzen kunnen vinden met een - vermoedelijk - snel algoritme, in ieder geval één die, gegeven het skelet, draait in O(n) tijd (n is het aantal hoekpunten van de veelhoek). Dit algoritme wordt uitgelegd in het tweede deel van de scriptie. modellering van een cartografisch probleem

17

HOOFDSTUK 3. OPERATOREN

Figuur 3.1: Stel dat het grijze vlak moet worden verwijderd. Bij wijze van voorlopige aanpak wordt het vlak dan eerst opgedeeld volgens de rode stippellijnen. Vervolgens worden de vier delen van het vlak een voor een verwijderd. Uit tests zou moeten blijken, of deze manier van opdelen werkelijk tot bruikbare resultaten leidt. De hoop is dat het skelet met de toegevoegde lijnen voldoende vrijheid biedt om het vlak op zo’n manier op te delen, dat geen merkwaardige artefacten ontstaan. Wellicht zorgt de beperking tot dit skelet er zelfs voor, dat op zo’n manier wordt gesneden dat het karakter van de plaatselijke vlakverdeling in zekere zin behouden blijft. Zonder testresultaten kunnen we echter slechts gissen. 3.2.3 Behandeling van eilanden Als het op te delen vlakje eilanden bevat, weten we nog geen efficiënt algoritme. Bij wijze van voorlopige oplossing stellen we het volgende voor. Voor elk eiland zoeken we het meest linkse en het meest rechtse punt. Vanuit deze punten trekken we een horizontale lijn naar het volgende eiland c.q. naar de buitenrand van het op te delen gebied. De op deze manier getrokken horizontale lijnen delen het op te delen gebied op in stukken zonder eilanden, die we vervolgens elk afzonderlijk behandelen. Bij de behandeling van een deelgebied, mogen geen stukken worden toegevoegd aan andere deelgebieden.

3.3

Eliminatie van delen van veelhoeken

Wanneer een gebiedje plaatselijk te smal is, worden de te smalle gedeelten afgebakend en opgedeeld onder buurvlakken. De behandeling van een afgebakend smal stuk hoeft in wezen niet anders te geschieden dan eliminatie van complete veelhoeken, behalve dat de extra eis moet worden gesteld dat geen delen mogen worden toegevoegd aan buurvlakken met dezelfde klasse: hiervan worden ze immers juist losgemaakt.

18


Hoofdstuk 4 Toepassing van de criteria en operatoren

4.1

Inlezen en integratie van data in NEN-formaat

De tdn levert de kaartgegevens aan in de vorm van diverse bestanden in diverse formaten. Een daarvan is het nen-formaat, dat goed te verwerken is. Het nenformaat is echter niet topologisch gestructureerd in de zin dat de onderlinge relaties van alle vlakken, lijnen en hoekpunten worden gegeven. Deze relaties moeten bij het inlezen uit de coördinaten worden afgeleid. Enige voorzichtigheid blijkt geboden, omdat lijnen elkaar in het beschikbaar gestelde bestand een enkele keer wel snijden, vermoedelijk door onnauwkeurigheden in de coördinaten. Voor ons zijn van belang het basisbestand en het huizenbestand. Het basisbestand bevat alle omtreklijnen op de kaart met per lijn de classificatie van de lijn zelf en de classificaties van de aangrenzende vlakken. Hieruit kan in principe een volledige vlakverdeling worden opgebouwd. De vlakken worden ook gegeven in het vlakkenbestand, maar omdat we de kenmerken van de lijnen zelf ook nodig hebben, kunnen we ze even goed uit het basisbestand lezen. Het basisbestand bevat niet de locatie van bebouwing: deze wordt apart gegeven in het huizenbestand. Voor aanvang van een test, zouden beide bestanden moeten worden ge¨ıntegreerd.

4.2

Provisorische eliminatie van lijnen en wegen

Zoals aangegeven in afdeling 3.1, zouden vlakken met hetzelfde grondgebruik voor aanvang van de generalisatie moeten worden samengevoegd als hun grenslijn op schaal 1:50.000 geen betekenis meer heeft. Omdat de generalisatie van lijnen buiten het kader van dit project valt, zou de selectie van lijnen provisorisch op basis van classificatie kunnen geschieden. In dat geval, lijken de onderstaande grenslijnen zinvol, de andere zouden kunnen worden geschrapt. modellering van een cartografisch probleem

19

HOOFDSTUK 4. TOEPASSING VAN DE CRITERIA EN OPERATOREN

betekenisvolle grenslijnen 04000 enkelspoor (SP1) 04020 enkelspoor in aanleg 04040 dubbelspoor (SP2) 04060 dubbelspoor in aanleg 04100 driespoor (SP3) 04120 driespoor in aanleg 04140 vierspoor (SP4) 04160 vierspoor in aanleg 04250 smalspoor 04260 metro bovengronds 04280 metro in aanleg 06020 sloot tussen 3 en 6 meter 07100 dijk > 2,5 meter 07110 dijk 1–2,5 meter 07140 boezemkade 07150 wal Merk op dat wegen niet worden genoemd, omdat wegen van voldoende belang altijd zo breed zijn dat ze in de top-bestanden niet als lijnen, maar als vlakken zijn opgenomen. Onder te schrappen grenslijnen vallen ook zogenaamde eilandverbinders, die slechts om technische redenen in de tdn-bestanden aanwezig zijn. In deze scriptie wordt steeds uitgegaan van veelhoeken die eilanden kunnen bevatten. In de top-bestanden zijn ook wegen aanwezig, soms als lijnen zonder dikte, maar als ze breed genoeg zijn - en dat zijn de meeste op schaal 1:10.000 - als vlakken. Bij generalisatie ten behoeve van een kaart met schaal 1:50.000 of kleiner, zullen sommige van deze wegen moeten worden verwijderd, d.w.z. opgedeeld onder buurvlakken. Wanneer generalisatie van een wegennetwerk buiten het kader van het project valt, zou men dat provisorisch kunnen doen op basis van de classificatie. Zouden we de wegen niet verwijderen, dan zouden ze de generalisatie van de omliggende vlakken onnodig beperken. Naar voorstel van de tdn, zouden wegen met classificatie 0340 (“overige” weg), 0343 (onverharde weg) 0347 (voetgangersgebied) en 0360 (fietspad breder dan twee meter) voor verwijdering in aanmerking komen. Wegen met een “geringere” classificatie worden in top reeds als lijnen voorgesteld.

4.3

Volgorde van verwerking van details, balancering

Elk vlakje in de kaart kan worden getoetst aan de hand van de criteria voor minimumoppervlakte, -lengte en -breedte. Het resultaat is een verzameling van vlakjes en delen van vlakjes die als “te klein” zijn aangemerkt en behandeld moeten worden. Het kan voorkomen dat, na afbakening van te smalle gedeelten in een vlak, de resterende delen ook te smal of te klein zijn geworden. In dergelijke gevallen zouden ook deze bij de te behandelen details moeten worden gevoegd. De volgorde waarin de gevonden details worden behandeld kan heel belangrijk zijn: behandeling van het ene detail kan behandeling van een ander overbodig maken of juist nodig maken. Een aanpak waarin alle details tegelijk in onderlinge samenhang behandeld worden zou in theorie ideaal zijn, maar veel te complex. Uit theoretisch 20


4.3. VOLGORDE VAN VERWERKING VAN DETAILS, BALANCERING

oogpunt, omdat geen maten bekend zijn aan de hand waarvan de kwaliteit van een complete kaart kan worden vastgesteld, en dus ook geen algoritmen waarvan duidelijk is dat ze die kwaliteit verbeteren. Uit praktisch oogpunt, omdat zo’n aanpak waarschijnlijk veel te veel implementatie- en rekentijd zou vergen. Een mogelijke aanpak is de te behandelen details te sorteren in volgorde van toenemend verstorend effect. Met verstorend effect bedoelen we de mate waarin de verwijdering van een detail plaatselijk de oppervlakteverhoudingen tussen de verschillende soorten grondgebruik verstoort. Het idee van de ordening naar toenemend verstorend effect is dat op deze manier de meest ingrijpende operaties tot het laatst worden uitgesteld, zodat er nog kans is dat ze in de loop van het proces overbodig worden gemaakt door andere operaties ter plaatse. Andere, kleinere details die verwijderd worden, kunnen dan eerst aan het grotere worden toegevoegd, waardoor het misschien groot genoeg wordt om behouden te kunnen blijven. Een concrete, werkbare definitie van het “verstorend effect” zou de volgende kunnen zijn. Telkens als een stuk wordt opgedeeld worden “onzichtbare aantekeningen” op de kaart geplaatst: •

•

op de plaats van het zwaartepunt van het opgedeelde stuk, wordt een aantekening geplaatst dat de betreffende klasse de oppervlakte van het detail heeft “verloren”; op de plaats van het zwaartepunt van elk deel dat aan een buurvlak is toegevoegd, wordt een aantekening geplaatst dat de klasse van de buur de oppervlakte van het toegevoegde stuk heeft “gewonnen”.

Het verstorend effect van het verwijderen van een detail wordt nu als volgt bepaald: 1. vind alle aantekeningen voor de klasse van het op te delen detail, die binnen een bepaalde afstand van het detail liggen (voor implementatiegemak: binnen een bepaalde afstand van bounding box); een voorstel voor deze afstand zou kunnen zijn: 3mm. 2. tel de waarde van deze aantekeningen op; het resultaat is een winst-/verliessaldo B dat aangeeft hoe de oppervlakte van gebieden van de betreffende klasse in de omgeving al is veranderd door het toepassen van generalisatieoperatoren; 3. bepaal de oppervlakte A van het op te delen stuk; 4. zoek de correctiefactor voor oriëntatiewaarde s op (zie onder); 5. het verstorend effect is nu: • bij B ≤ 0: sA; • bij 0 < B < A: s(A − 2B); • bij B ≥ A: −sA. Een negatief verstorend effect, ofwel een herstellend effect, kan zich voordoen als in de omgeving het een en ander is toegevoegd aan gebied van de betreffende klasse. Het verwijderen van een detail van dezelfde klasse, kan het evenwicht weer een beetje herstellen. Merk op dat het verstorend effect volgens deze definitie afhangt van hetgeen eerder in de omgeving is gebeurd. Dat betekent dat na toepassing van een generalisatieoperator het verstorend effect van de behandeling van gebieden in de buurt opnieuw moet worden berekend. Bovenstaande berekening bepaalt alleen een verstorend effect voor het verwijderen van een detail, niet voor het toevoegen van delen van de vrijgekomen oppervlakte modellering van een cartografisch probleem

21


aan buurgebieden. In theorie zou men dat misschien ook mee willen nemen in de berekening; in de praktijk zou dit zeer omslachtig zijn. Een voorstel voor de correctiefactoren voor oriëntatiewaarde is als volgt: correctiefactoren voor ori¨ entatiewaarde 01 bebouwing mits minimaal 30 m2 in het terrein 01 bebouwing kleinere bebouwing (schuren?) 050 bos 06 water 0 (overig grondgebruik)

3,0 0,5 2,0 1,5 1,0

Op deze manier zullen huizen en grotere gebouwen in rommelig terrein gemakkelijker behouden blijven. Merk op dat losstaande bebouwing op grote afstand van elkaar in open terrein toch verloren zal gaan als men alleen de operatoren gebruikt die in dit verslag zijn uitgewerkt. In uniform open terrein kunnen immers geen details worden onderscheiden die aan de bebouwing kunnen worden toegevoegd om die een minimumgrootte te kunnen geven. De gedachtengang achter het onderscheid tussen grotere en kleinere bebouwing is de volgende. Het generalisatiehandboek meldt verschillende behandelwijzen voor schuren, laagbouw, lage flats en hoogbouw. De eerste drie klassen zijn op grond van het top-bestand niet van elkaar te onderscheiden, zodat we ze allen gelijk zullen moeten behandelen. We hebben dus eigenlijk geen mogelijkheden om schuren te laten vervallen in plaats van ze met elkaar of andere bebouwing samen te voegen, terwijl we woningen juist wel willen samenvoegen om ze te kunnen behouden. Door op kleine bebouwing een andere correctie voor orientatiewaarde toe te passen dan op grotere bebouwing, kunnen we toch proberen enig onderscheid te maken. Rond hoogbouw en rond vrijstaande openbare gebouwen moet volgens het handboek de open ruimte behouden blijven. Ook deze categorieën zijn niet of nauwelijks te onderscheiden aan de hand van alleen de top-gegevens. De verwachting (hoop) is echter dat de open ruimte rond hoogbouw en openbare gebouwen in het algemeen zo groot is dat deze vanzelf behouden blijft. Men hoeft dan geen bijzondere regels voor deze gebouwen te implementeren. Deze aanpak doet ook recht aan het feit dat naarmate de schaal kleiner wordt en de hoogbouw dichter bij elkaar staat, hoogbouw uiteindelijk toch in het bebouwd gebied zal moeten worden opgenomen. Of deze aanpak met aantekeningen voor verstorend effect daadwerkelijk tot een betere generalisatie leidt, zou getest moeten worden.

4.4

Terminatie-garantie

Het is moeilijk criteria en operatoren zo te definiëren dat toepassing ervan gegarandeerd in een eindig aantal stappen leidt tot een resultaat, dat aan de gestelde eisen voldoet. Daartoe is in dit project ook niet werkelijk een poging ondernomen. Om te garanderen dat het generalisatieproces ooit ophoudt, zal het proces moeten worden gecontroleerd door andere criteria dan in hoofdstuk 2 zijn geformuleerd. Men zou een “maat van kaartdrukte” kunnen definiëren, en generalisatie-operatoren blijven toepassen zo lang er gebieden zijn die niet aan de gestelde eisen voldoen en minimaal een bepaalde absolute reductie in kaartdrukte wordt gerealiseerd. We 22


4.5. KWALITEITS-GARANTIE?

Figuur 4.1: Voorbeeld van een smal gedeelte, waarvan opdeling onder de buurvlakken een averechts effect op de kwaliteit van de kaart zou hebben. beschikken echter nog niet over zo’n maat, in ieder geval niet over een die gemakkelijk te berekenen of op andere wijze te gebruiken is. Een van de eenvoudigste oplossingen is waarschijnlijk deze. Telkens als een detail is behandeld, worden alle gewijzigde buren opnieuw geanalyseerd. Het kan bijvoorbeeld zijn dat buren die eerst te klein waren, dat nu niet meer zijn. Het kan ook zo zijn dat nieuwe problemen (smalle stukken enz.) zijn ontstaan. In het laatste geval worden de nieuwe problemen alleen behandeld als het er minder zijn dan zojuist zijn opgelost. Zijn er meer, dan worden de minst ernstige geschrapt. Hiervoor zou van schendingen van minimummaten een mate van ernst moeten worden vastgesteld: hiervoor kan men op diverse wijzen functies van vereiste maat, werkelijke maat en oppervlakte gebruiken. Op deze manier wordt gegarandeerd dat het generalisatieproces niet eindeloos doorgaat.

4.5

Kwaliteits-garantie?

Kwaliteitsgaranties worden op bovenstaande wijze uiteraard niet gegeven. De behandeling van een detail kan er zelfs toe leiden dat meer problemen worden veroorzaakt dan worden opgelost. Afhankelijk van de implementatie, zou men hiermee om kunnen omgaan door in zulke gevallen de behandeling van het detail terug te draaien, of door het in ieder geval niet te behandelen als je de verslechtering “kunt zien aankomen”. Dat laatste is niet eenvoudig, maar het volgende zou een aanwijzing kunnen zijn. Als een detail een zodanige vorm heeft, dat er punten zijn waarvoor de dichtsbijzijnde punten op de omtrek op twee verschillende snijlijnen liggen (lijnen waarlangs het detail is losgesneden), dan is dat een aanwijzing dat het detail zo kort is, dat behandeling meer problemen veroorzaakt dan het oplost (zie figuur 4.1). Of dit het geval is, kan worden vastgesteld aan de hand van het skelet van het detail. Verbreding van het detail zou in dergelijke gevallen een meer voor de hand liggende operatie zijn, maar die is in dit project niet uitgewerkt.


23


24


Hoofdstuk 5 Conclusies

Het is moeilijk om aan dit project conclusies te verbinden, omdat het niet is gelukt om de ontwikkelde ideeën te implementeren en te testen. Met name de volgende zaken maakten dat implementatie meer tijd zou hebben gekost dan beschikbaar was: • Gebreken van de C++-compiler en -linker. Bij intensief gebruik van zogenaamde templates worden fouten soms niet gerapporteerd, of de compiler crasht. In dergelijke gevallen is het moeilijk zoeken naar de oorzaak, zeker wanneer men hier nog geen ervaring mee heeft. • Gebrekkige robuustheid van de combinatie cgal (de gebruikte bibliotheek met geometrische bewerkingen) en leda (een bibliotheek met onder meer rekenkundige bewerkingen en beperkte grafische mogelijkheden). Pas naar veel puzzelen was een en ander goed op elkaar afgestemd, in de zin dat het foutloos leek te werken. Het laatste probleem dat werd geconstateerd voordat we de implementatie moesten afgelasten, was de functie om lijnstukken in een kaart te splitsen: dit duurde soms vele seconden per operatie, hetgeen testen nagenoeg onmogelijk maakte. Dit probleem is niet meer nader onderzocht. Om een oordeel te vellen over in dit verslag gegeven ideeën, zijn tests noodzakelijk. Verder onderzoek is vooral nodig naar maten om kwaliteit van een kaart plaatselijk te meten, zodat het mogelijk wordt om algoritmen beter theoretisch te toetsen, te analyseren in welke gevallen de tot nu toe ontwikkelde algoritmen tekort schieten enz. Met het algoritme om smalheid te detecteren, hebben we misschien een stap gezet die tot een iets beter begrip van veelhoeken in een kaart leidt. Gezien de complexiteit van het probleem, is het twijfelachtig of het probleem zich er wel voor leent om in individuele afstudeerprojecten te worden aangepakt. Een beter gecoördineerde aanpak zou vruchtbaarder kunnen zijn.


25

HOOFDSTUK 5. CONCLUSIES

26


Bibliografie

[1] M. Bader en R. Weibel. Detecting and resolving size and proximity conflicts in the generalization of polygonal maps. In Proc. 18th Int. Cartographic Conference, Stockholm, 1997. [2] B.P. Buttenfield en R.B. McMaster, redacteurs. Map Generalization: Making Rules for Knowledge Representation. Longman, London, 1991. [3] F. Chin, J. Snoeyink en C.-A. Wang. Finding the medial axis of a simple polygon in linear time. In Proceedings 6th Annual International Symposium on Algorithms and Computation, ISAAC ’95, blz. 382–391, Berlin, 1995. Springer Verlag, Lecture Notes in Computer Science, nr. 1004. [4] S.J. Fortune. A Sweepline Algorithm for Voronoi Diagrams. Algorithmica, 2:153–174, 1987. [5] F.N. Jongerius. Van TOP10 naar TOP50 – een schaalloos bestand. Afstudeerverslag TU Delft, Faculteit der Geodesie, 1997. [6] M.J. van Kreveld. Twelve Computational Geometry Problems from Cartographic Generalization. Draft paper for the Dagstuhl Seminar on Computational Geometry, March 1999, http://www.geo.unizh.ch/ICA/Documents/Workshop99/twelveproblems.pdf [7] J.-C. M¨ uller, J.-P. Lagrange en R. Weibel, redacteurs. GIS and Generalization – Methodology and Practice, nr. 1 van GISDATA. Taylor & Francis, London, 1995. [8] W. Peng. Automated Generalization in GIS. (Proefschrift Landbouwuniversiteit Wageningen) ITC publ. nr. 50, Enschede, 1997. [9] J. van Putten. Experiences with the GAP-tree. Technical Report INF-SCR97-30, Informatica-Instituut Universiteit Utrecht, 1997. [10] Handboek Generalisatie (concept). Topografische Dienst Nederland, 1998. [11] Productbeschrijving TOP10vector (concept). Topografische Dienst Nederland, 1998. [12] R. Weibel. Generalization of Spatial Data: Principles and Selected Algorithms. In Algorithmic Foundations of Geographic Information Systems, Lecture Notes in Computer Science (tutorials) nr. 1340, blz. 99–152. Springer-Verlag, Berlin, 1997. [13] R. Weibel. A typology of constraints to line simplification. In M.J. Kraak en M. Molenaar, redacteurs, Proc. 7th Int. Symp. on Spatial Data Handling, blz. 533–546, Taylor & Francis, London, 1997.


27

Eliminatie van details in een topografische kaart. Herman Haverkort

Recommend Documents