SPECIAL
2014-2 I Geo-Info
11
Techniek i: optimalisatie
via Voronoi-cellen
In de eerste methode wordt voor elk paar
hoekpunten van het polygoon een kromme
berekend die het tussenliggende stuk van het
polygoon zou kunnen vervangen. De kwaliteit
van een kromme bepaalt hoe geschikt deze
is om een gedeelte van het polygoon te
vervangen. Door middel van dynamisch
programmeren (een optimalisatietechniek)
kan de beste selectie van benaderende krom
men worden gemaakt die samen het hele
polygoon vervangen. Een zo klein mogelijk
aantal krommen bij een gegeven minimale
kwaliteit, of een zo hoog mogelijke kwaliteit bij
een gegeven aantal krommen. Er wordt alleen
gebruik gemaakt van krommen die binnen de
Voronoi-cel blijven, d.w.z. de kromme bestaat
enkel uit punten waarvoor het dichtstbijzijnde
punt langs het polygoon onderdeel is van het
stuk polygoon dat wordt vervangen (Figuur 1).
Hierdoor snijden de krommen die verschil
lende delen van het oorspronkelijke polygoon
vervangen elkaar niet. Verschillende krommen
en kwaliteitsmaten kunnen worden gebruikt;
twee varianten van deze methode worden
hieronder besproken.
De eerste variant werkt met kubische Bézier-
krommen. Om de kwaliteit van een kromme te
berekenen, worden punten met een constante
tussenafstand geplaatst langs zowel de
kromme als het bijbehorende polygoondeel.
Deze punten worden paarsgewijs met elkaar
verbonden; elk paar heeft een onderlinge
afstand. De afstand tussen de kromme en
het polygoondeel wordt gedefinieerd als
een gewogen gemiddelde van de onder
linge afstanden, waarbij paren dicht bij de
eindpunten een hoger gewicht krijgen. Een
lage afstand duidt een hoge kwaliteit aan.
Via numerieke benadering wordt voor een
polygoondeel een kromme met een hoge
kwaliteit berekend. De weging zorgt ervoor
dat de berekende kromme rond de eindpun
ten min of meer in de goede richting loopt.
Dit voorkomt scherpe hoeken in het resultaat
die niet in het polygoon zaten. De scherpe
hoeken die wel in de schematisering te zien
zijn komen dan ook overeen met een duidelijk
zichtbare scherpe hoek in het polygoon.
De tweede variant werkt met cirkelbogen.
Deze worden zo gekozen dat de oppervlakte
van het polygoon niet verandert wanneer een
gedeelte door een cirkelboog wordt vervan
gen. De kwaliteit van een cirkelboog wordt nu
berekend als de zogenaamde Fréchet-afstand
tussen de boog en het vervangen gedeelte
van het polygoon. Deze afstand kan gezien
worden als de minimale maximum afstand
tussen de boog en het polygoondeel als beide
lijnen van begin tot eind getraceerd worden.
Ook hier geldt dat een hoge afstand een lage
kwaliteit aangeeft.
Techniek 2: stapsgewijs vervangen
De tweede methode voor schematisering
gaat uit van het oorspronkelijke polygoon
en beschouwt elke zijde daarvan als een
cirkelboog met een oneindig grote straal.
Vervolgens wordt het polygoon steeds
verder geschematiseerd door telkens twee
of drie opeenvolgende cirkelbogen door
Figuur 2 - Het vervangen van cirkelbogen.
respectievelijk één dan wel twee cirkelbogen
te vervangen (zie Figuur 2). Daarbij wordt
wederom gegarandeerd dat de oorspronke
lijke oppervlakte behouden blijft en cirkel
bogen elkaar niet snijden. In het geval dat drie
cirkelbogen door twee cirkelbogen worden
vervangen wordt een heuristiek gebruikt
om een goed punt te vinden waar de twee
cirkelbogen op elkaar aansluiten; dit punt
hoeft geen hoekpunt van het oorspronkelijke
polygoon te zijn. In elke stap van het algoritme
zijn er meerdere opties om cirkelbogen te
vervangen. De gekozen optie heeft de beste
gelijkenis tussen de vervangende cirkelbogen
en het originele polygoondeel dat deze bogen
representeren. Om de gelijkenis te bepalen
wordt het "symmetrische verschil" gebruikt:
dit is de oppervlakte van het origineel dat niet
wordt bedekt door het polygoon met de ver
vangende cirkelbogen en vice versa. De staps
gewijze methode ondersteunt verschillende
tekenstijlen door het symmetrisch verschil
te wegen met andere geometrische eigen
schappen van de vervangende cirkelbogen.
Drie stijlen worden beschouwd: licht gebogen,
sterk gebogen, of gecombineerd. Voor de licht
gebogen stijl wordt een voorkeur gegeven
aan cirkelbogen met een hoge straal; voor de
sterk gebogen stijl wordt juist een voorkeur
gegeven aan een kleine straal. De gecombi
neerde stijl gebruikt geen voorkeur: de keuze
van een stap gebeurt enkel aan de hand van
het symmetrisch verschil.
Voorbeeldresultaten
Het gebruik van verschillende krommen en
kwaliteitsmaten kan leiden tot zeer ver
schillende resultaten. Bézier-krommen, die
complexe vormen kunnen representeren, zijn
in staat om zelfs bij zeer simpele schematise-
Figuur 3 - Resultaten van de eerste techniek: Vietnam met cirkelbogen (boven) en Afrika met Bézier-
krommen (onder). Van links naar rechts worden steeds minder krommen gebruikt om een sterkere
schematisering te bereiken.
