Het regulier polytoop
Een robuuste representatie van geometrische objecten
Bij de representatie van geometrische objecten en het manipuleren van deze beschrijvingen
in de eindige digitale computer wordt veelvuldig gebruik gemaakt van reële getallen en
bijbehorende formules uit de wiskunde. De computer is echter eindig en kan dus niet
direct deze op reële getallen gebaseerde geometrie representeren. Gehele getallen binnen
een beperkt bereik, van minimum tot maximum waarde, zijn wel exact weer te geven.
Daarom kan er worden afgerond naar gehele getallen (of drijvende-kommarepresentaties),
maar getallen als 1/3, V2 of jc kunnen hierbinnen niet exact gerepresenteerd worden.
Dit probleem is al lang bekend maar tot op de dag van
vandaag is er nooit een echt goede oplossing gevonden.
Dit heeft nog regelmatig 'onverwachte' nadelige gevolgen
(paragraaf 1 gaat hier verder op in) zoals onduidelijkheid
over de gelijkheid van twee objecten, problemen met het
snijpunt van twee lijnen en het niet associatief zijn van ope
raties als doorsnede en vereniging. Daarom wordt in para
graaf 2 op basis van axioma's die direct uitgaan van de ein
dige (digitale) representaties, de ontwikkelde representatie
onderbouwd: het regulier polytoop. Dit is een representatie
die geen onderscheid maakt tussen de rand (begrenzing) en
binnenkant van een object. Bovendien is het een represen
tatie die ook in hogere dimensies kan worden gebruikt, al
zal dit artikel zich tot 2D- en 3D-toepassingen beperken. Het
regulier polytoop maakt gebruik van domein-beperkte ratio
nele getallen die wel goed in een computer te representeren
zijn. Vervolgens wordt aangetoond dat het regulier polytoop
niet alleen maar mooie wiskundige theorie is maar ook im-
plementeerbaar is (in een set Java-klassen). Een sterk punt
van de regulier polytoop-representatie is dat deze moeite
loos kan omgaan met een omgeving waarin zowel 2D- als
3D-beschrijvingen voorkomen. Dit wordt geïllustreerd aan
de hand van het modelleren van een 2D/3D-kadaster (para
graaf 3). Vervolgens worden de huidige problemen met het
uitwisselen van geometrie binnen de Geografische Informa
tie Infrastructuur (Gil) geanalyseerd en kunnen deze gro
tendeels worden herleid tot gebrekkige standaardisatie van
een robuuste representatie (paragraaf 4). Hiervoor biedt het
regulier polytoop ook de oplossing. Het artikel sluit af met
de belangrijkste conclusies en een aantal onderwerpen voor
vervolgonderzoek.
1. Problemen met de huidige representatie van
geometrie in de computer
De definitie van 'is gelijk' (equals() in ISO 19107) is gebaseerd
op een tolerantie waarbinnen twee objecten moeten liggen.
Het kan dus zo zijn dat hoewel a benb c,er toch niet geldt
dat a c (fig.l). Computeralgoritmen die hier wel van uitgaan
kunnen hierdoor mislopen. De ISO 19107-definitie is dan ook
niet in overeenstemming met de wiskundige definitie van
een gelijkheidsrelatie, daar deze dus niet transitief is.
fftJ Thompson, B S€.,DfpLComputéf,$c.r
'fj fpêlé'joóÏTechnical
apartment of l^tural
Resources and Water, Queens land
I Qavefpméntrpftprof.dfM P4M, van
Oaster&ty, CtSt G^ïuDetftfr
Fig. 1. Binnen de
tolerantie geldt
a=b, en ook b=c,
maar niet a=c!
Als twee lijnsegmenten, die beide ge
definieerd zijn door twee eindpunten
met geheeltallige coördinaten, elkaar
snijden, dan is de kans groot dat het
snijpunt niet met geheeltallige coör
dinaten kan worden beschreven. Bij
afronding naar de best beschikbare
beschrijving zal het snijpunt dus niet
meer exact op de beide lijnen liggen
maar links of rechts hiervan. De kans
dat op door twee willekeurige geheel
tallige coördinaten gespecificeerd lijn-
stulc geen enkel (geheeltallig represen-
CEO-INFO 2007-12