2. Een alternatieve en robuuste
representatie: het regulier
polytoop
teerbaar) tussenpunt ligt, is ongeveer
60%! [Thompson, 2007]. Daarom wordt
ook bij de berekening van een snijpunt
met een tolerantie gewerkt. Omge
keerd is het zo dat wanneer er met een
tolerantie wordt gewerkt er nu meer
dere punten op beide lijnen kunnen
liggen (d.w.z. binnen de tolerantie) en
dat de doorsnijding van twee niet pa
rallelle lijnen uit meer dan één punt
zou bestaan, wat normaal niet de be
doeling is (fig. 2).
Het laatste voorbeeld laat zien dat
in een eindige representatie de ver
eniging- en doorsnede-operaties niet
meer associatief zijn; d.w.z. Au(Bw C)
(A B) u C. In de berekening van de
vereniging worden snijpunten bepaald
tussen de randen van de objecten. Een
snijpunt moet worden afgerond naar
een representeerbaar punt, waardoor
de grens licht zal verschuiven. Deze
verschuivingen kunnen vervolgstap
pen beïnvloeden. Figuur 3 laat zien
dat (AuB)uCresulteert in twee losse
delen (door het verenigen van objec
ten A en B komt lijnstuk pq verder van
object C te liggen, waardoor deze niet
meer zal worden verenigd) terwijl A cj
(B u C) wél resulteert in een aaneenge
sloten object.
In het recente promotieonderzoek van
[Thompson, 2007] wordt een wiskun
dige basis gekozen voor representatie
van ruimtelijke objecten in een com
puter. In het proefschrift wordt een
aantal aannames (axioma's) gedaan
en gebruikt om een keten van argu
menten samen te stellen die bewijzen
dat een correcte werking van algorit
men kan worden gegarandeerd als
computers aan deze axioma's voldoen.
Deze bewijslceten is gebaseerd op een
nieuwe representatievorm: het regu
lier polytoop. Deze reguliere polytopen
kunnen wel exact worden opgeslagen
in een computer waarmee deze weer
gave geen benadering meer is van een
geïdealiseerd wiskundig model.
Een regulier polytoop-representatie
van ruimtelijke objecten is gedefini
eerd als de vereniging van een eindige
verzameling van (mogelijk overlap
pende) convexe polytopen die op hun
beurt weer zijn gedefinieerd als de
doorsnede van een eindige verzame-
Fig. 2. Snijpunt
berekening met
tolerantie kan ertoe
leiden dat meerdere
punten als snijpunt
kunnen worden
aangemerkt.
Fig. 3. Linksboven: de drie polygonen A, B en C; rechtsboven: de vereniging (AuB)uC resulteert
in twee losse objecten, omdat C te ver van lijnstuk pq komt te liggen; linksonder: vereniging
BrjC; rechtsonder: de vereniging AufBcX) leidt tot één object omdat C oorspronkelijk wél
binnen de tolerantie lag van B.
ling van halfruimten. Een halfruimte kan gezien worden
als de ruimte die aan een bepaalde kant van een vlak in
een ruimte ligt. Deze halfruimten zijn gedefinieerd door
getalrepresentaties met eindige nauwkeurigheid. De term
'regulier polytoop' heeft hier niet de betekenis als n-dimen-
sionale generalisatie van een regelmatig polyhedron (d.w.z.
één met gelijke kanten, zijden en hoeken), maar het is een
combinatie van het topologische begrip 'regulier' (verzame
ling die gelijk is het binnenste van zijn afsluiting, 'equal to
the interior of its closure') met de gangbare geometrische
betekenis van 'polyhedron' (de n-dimensionale veralgeme
nisering).
In 3D is een halfruimte H(A,B,C,D) gedefinieerd door een
viertal gehele getallen waarvoor geldt dat -M A, B, C M,
- 3M2 D 3M2. De verzameling punten (x, y en z.) die hierbij
hoort wordt gedefinieerd door:
(((A0x B0y) C0z) D) 0 of
\(((A0x B<8>y) C0z) 0 Dj 0 en A 0] of
p(8)y C0z) D) 0 en A 0 en B 0] of
{(C0z D) 0 en A 0, B 0 0 en C 0],
waarbij het half-open interval [-M, M) de toegestane waar
den bevat voor de ordinaten en de symbolen en zijn
gebruikt om de resultaten van optellen, vermenigvuldigen
en de gelijkheidstest in computerhardware aan te duiden.
De expressie A©B A+B moet worden geïnterpreteerd als
de uitspraak dat de optelling in de computer het correcte
(wiskundige) resultaat geeft. Dit is waar voor berekeningen
met gehele getallen binnen het domein maar over het alge
meen niet voor drijvende-kommaberekeningen. De boven-
GEO-INFO 2007-12
