zichzelf of met andere ringen), zo
lang maar elk punt in het binnengebied
of op de rand van de polygoon maar elk
ander punt (in het binnengebied of op de
rand van de polygoon) kan bereiken via
een pad geheel door het binnengebied van
de polygoonoftewel, hij definieert een
verbonden gebied. Hierbij vereisen
sommige van de genoemde uitspra
ken (zoals 'ring raakt andere ring')
een tolerantiewaarde in de evaluatie
en daarom is deze tolerantie ook ex
pliciet onderdeel van deze definitie.
Het is mogelijk te overwegen om de
tolerantiewaarde niet te gebruiken en
alleen te kijken naar de digitale repre-
sentatiewaarde van de coördinaten en
de rechte lijnsegmenten die hierdoor
zijn gedefinieerd. Stel een situatie
voor dat een punt van een binnenring
heel dicht bij een buitenring komt
(middendeel van lijnsegment). De situ
atie in de werkelijkheid is zo dat dit
punt eigenlijk exact op de buitenring
zou moeten liggen. Echter door de ein
dige hoeveelheid beschikbare getallen
in een computer, is het niet altijd mo
gelijk om de exacte locatie te represen
teren [4][5], maar zal een nabijgelegen
locatie gekozen worden (op basis van
'integer' of 'floating point' in plaats
van reële getallen). In dergelijke geval
len is het willekeurig of het punt op
het lijnsegment, dan wel links of
rechts hiervan zal liggen. Indien er dus
geen tolerantie wordt meegenomen,
zou het kunnen zijn dat deze situatie
wordt geclassificeerd als kruisende
ringen (niet toegestaan) of twee di
sjuncte ringen (niet het geval want rin
gen zouden elkaar eigenlijk moeten
raken). In ieder geval wordt de poly
goon-situatieanalyse (ringen en geldig
heid) niet goed uitgevoerd. Dit is één
van de redenen waarom vele systemen
met één of andere tolerantiewaarde
werken. Het probleem is nu echter hoe
te specificeren wat er precies met de
tolerantie moet gebeuren bij het vali
deren van polygonen (dit deel ont
breekt nog in onze definitie). Een an
der voorbeeld dat dit probleem il
lustreert, is testpolygoon 30: een optie
om aan de tolerantie-eis te voldoen is
het verwijderen van de 'naar binnen
stekende uitsteeksels' en het resultaat
zou nu een geldige polygoon zijn. Ech
ter, een andere aanpak zou kunnen
zijn het vergroten van de opening tus
sen de twee eindpunten; het resultaat
is nu een niet-geldige polygoon omdat
het 'naar binnen stekende uitsteeksel'
nu kruist met één van de andere zijden. Dit voorbeeld toont
aan dat het moeilijk is om een niet-ambigue wijze van het
werken met een epsilontolerantie voor te schrijven gedu
rende het validatieproces van een polygoon.
Een onverwacht aspect van onze definitie van geldige poly
gonen is dat een 'uitsteeksel naar buiten' (testpolygoon 11)
resulteert in een ongeldige polygoon, omdat het niet moge
lijk is om van het midden van het uitsteeksel naar elke an
der punt van de polygoon te gaan via het binnenste van de
polygoon. Terwijl aan de andere kant een polygoon met
'uitsteeksel naar binnen' (testpolygoon 12) wel een geldige
polygoon is omdat het nu mogelijk om vanuit elk punt (ook
het midden van het uitsteeksel) elk ander punt van de poly
goon te bereiken via het binnenste. Iets soortgelijk als met
'uitsteeksels' doet zich ook voor met 'bruggetjes': terwijl
bruggen naar binnen resulteren in geldige polygonen (test
polygonen 7 en 8), resulteren bruggen naar buiten (testpo
lygonen 15 en 16) in ongeldige polygonen. Zowel in het ge
val van 'uitsteeksels' als 'bruggetjes' is er een verschil tus
sen de binnen- en de buitenkant (wat men wellicht asym
metrisch zou kunnen vinden).
Geldige en schone polygoon
Het validatieproces (volgens onze definitie van geldige poly
gonen) zou een stuk eenvoudiger worden als kon worden
aangenomen dat geen enkel punt binnen de epsilon-tolerantie
van een ander punt of zijde ligt (die het zelf niet mede defini
eert); dit zal een (geldige schone polygoon worden genoemd.
In testpolygoon 4 (en oolc in testpolygonen 31 en 32) houdt
dit in dat het segment waarop het punt van de andere ring
geacht wordt te liggen, in tweeën wordt gesplitst. Door deze
manier van modelleren kan de polygoonvalidatie worden
uitgevoerd zonder toleranties. Een ander voordeel van scho
ne polygonen is dat deze ook geen 'uitsteeksel' (naar
binnen of naar buiten) meer hebben, omdat de twee eind
punten te dicht bij elkaar liggen (of zelfs gelijk zijn). Op
vergelijkbare wijze worden zowel interne als externe 'brug
getjes' verwijderd. Ook worden herhalende punten verwij
derd. Alvorens polygonen te versturen, moet het verzenden
de systeem eerst de epsilon-tolerantie-verwerking uitvoe
ren. Daarna kan de verzender er zeker van zijn dat het ont
vangende systeem ook geldige polygonen zal ontvangen (er
van uitgaande dat de coördinaten niet meer dan epsilon
worden veranderd tijdens de overdracht).
De grootste afstand waarover een coördinaat kan worden
verplaatst terwijl de polygoon nog steeds geldig blijft wordt
de robuustheid van een polygoonrepresentatie genoemd door
Thompson [6]. In testpolygoon 4 (zonder extra punt in bui
tenring), is de robuustheid nul, want een oneindig kleine
verplaatsing (naar buiten) van het punt op de binnenring
zorgt ervoor dat de polygoon ongeldig wordt. Echter het toe
voegen van een expliciet (gedeeld) punt in de buiten- en
binnenring zorgt ervoor dat de robuustheid van de repre
sentatie (van dezelfde polygoon) toeneemt tot ten minste de
waarde epsilon. De robuustheid is zelfs nog groter, want het
is mogelijk om de (gedeelde) punten meer dan epsilon te ver
plaatsen (de omvang van epsilon is zichtbaar de vorm van de
open cirkel in de figuren van testpolygonen 31 en 31). De ro
buustheid van een polygoon kan worden berekend door de
GEO-INFO 2004-3
