V
V
Simulating Line Segments
In de presentatie Speeding Up the Dougtas-Peucker
Line-Simplification Algorithm", gegeven door Jack
Snoeyink (University of British Columbia, Canada) werd
een methode beschreven om „worst case" performance
van het standaard-algoritme 0(n*n) terug te brengen
naar 0(n log n). Dit geschiedt door tijdens de berekening
een „convex huil", een structuur uit de computational
geometry, bij te houden. Het is interessant om te zien dat
een belangrijk, veel gebruikt en al twintig jaar oud algo
ritme nog steeds kan worden verbeterd. Wel was Jack
Snoeyink zo eerlijk om toe te geven dat in veel praktijk
gevallen het standaard-algoritme een factor 2 a 3 sneller
werkt. Maar doordat het nieuwe algoritme ook in „slech
te" gevallen goed werkt (factor 150 sneller bij 10 000
punten), is het geschikt voor interactieve toepassingen.
Image
Classified image
Map
"classification"
"generalisation"
"photo-interpretation"
Max Egenhofer (NCGIA, University of Maine) gaf een
presentatie over .Topological Consistency". Op basis
van de wiskundige point-set theorie worden de volgende
topologische relaties tussen twee vlakken exact gedefi
nieerd: disjoint, meet, equal, inside, contains, covers,
coveredBy en overlap. Verder wordt een methode ge
geven om te evalueren of een gegeven aantal topolo
gische relaties tussen objecten nog wel mogelijk is. Zo
kan bijvoorbeeld de volgende SQL-achtige query:
SELECT lake.name
FROM state, county, lake
WHERE stategeometry CONTAINS county.geometry
AND county.geometry CONTAINS lake.geo
metry AND (stategeometry DISJOINT lake,
geometry OR stategeometry MEET lake.geo
metry)
gelijk worden verworpen, omdat de voorwaarde in de
WHERE-clause inconsistent is. Er is dus helemaal geen
zoekwerk in de gegevensbank meer nodig!
Dat het soms ook heel lang kan duren voordat systeem
concepten worden gepresenteerd, bleek uit de presenta
tie van Nick Chrisman (University of Washington) met de
titelLessons for the Design of Polygon Overlay Proces
sing from the ODYSSEY WHIRLPOOL Algorithm". Dit
programma werd halverwege de jaren zeventig bij het
beroemde „Harvard Lab for Computer Graphics" ont
wikkeld en maakte gebruik van een techniek die later in
de literatuur bekend werd onder de naam „sweep line".
Details over het „WHIRLPOOL Algorithm" konden nog
nooit eerder worden gepresenteerd vanwege „institutio
nal reasons". Volgens Chrisman kan WHIRLPOOL zowel
op het gebied van functionaliteit als op het gebied van
efficiëntie nog steeds goed worden vergeleken met wat
tegenwoordig te koop is in de vorm van de bekende GIS-
pakketten.
Het symposium werd afgesloten met een aantal panel
discussies met een „zelf reflecterend" karakter.
Het eerste panel werd gevormd door een aantal vooraan
staande wetenschappers van universiteiten en onder
zoeksinstellingen. De centrale vraag was: kan niet-
commercieel onderzoek nog wel op tegen de commer
ciële „cutting edge"-ontwikkelingen in dit veld. De indruk
bestond dat dit in het algemeen nog zeker het geval is,
ondanks enkele negatieve trends: geldgebrek (onder
andere voor apparatuur) en in het bijzonder het weghalen
van goede werknemers door de industrie.
Het tweede panel bestond uit een aantal vertegenwoor
digers van de industrie (Genasys, Intergraph, ESRI, Com-
putervision, IBM) en hield zich bezig met de vraag: is dit
symposium nog wel relevant voor de industrie (is de in
dustrie al niet verder en zijn we niet bezig het wiel
opnieuw uit te vinden)? De zeer duidelijke conclusie van
het panel was, dat het symposium zeker relevant was. Dit
werd onderbouwd door het noemen van een aantal
presentaties met ideeën die op korte termijn zouden kun
nen worden overgenomen, onder andere op het gebied
van „parallel processing", „extensible database/GIS",
„computational geometry" en „topology". De vraag is in
hoeverre de industrie hier niet gewoon uit eigen belang
spreekt, omdat alle open literatuur natuurlijk meege
nomen is.
De volgende Spatial Data Handling zal over twee jaar
worden gehouden in Edinburgh, Schotland. Gezien de
kwaliteit van dit symposium kan daar al met genoegen
naar worden uitgekeken. Bovendien beloofde het organi
satiecomité als „social event" het proeven van echte
Schotse whisky, hetgeen bij de huidige deelnemers wel in
de smaak leek te vallen.
When line segments are generated by connecting
uncertain endpoints, the most reliable portion
of the segment is near its midpoint!
a: Endpoints are drawn
from circular normal
distributions
b: Random endpoints
are connected to
c: Standard deviation
is less at midpoint
d: Probability contours
may be abstracted
532
NGT GEODESIA 92 - 12
