I
i i:
220
richting punten die dicht bij elkaar liggen, ook in het com
puterbestand dicht bij elkaar zijn terug te vinden. Bij een
eigen uitwerking van deze methode is niet gebleken dat
deze methode betere resultaten zou geven dan de zelf
ontwikkelde werkwijze die hierna wordt aangegeven.
Voor de hier bedoelde toepassing, waarbij het in eerste
instantie alleen van belang is de juiste coördinaten van
knikpunten te vinden aan de hand van benaderde waar
den, is een snelle werkwijze ontwikkeld. Daarbij wordt in
twee fasen gewerkt. Bij de eerste fase, die voor een kaart-
blad slechts één keer behoeft te worden toegepast, wor
den de coördinaten van de punten gesorteerd op de X-
waarde ervan en wordt een nieuw bestand vervaardigd
van deze coördinaten. Hoewel na het starten van het be
treffende onderdeel van het programma de aanwezigheid
van de operateur niet van belang is, is het toch gunstig
voor dit sorteren ook een snelle werkwijze toe te passen.
Dit wordt mede veroorzaakt door het feit dat bij de sorte
ring veelal een groot aantal coördinaten wordt betrokken.
Bij eenvoudige sorteerroutines neemt de rekentijd toe
met het kwadraat van de toename van het aantal te sorte
ren waarden. Is het aantal punten bijvoorbeeld 100 keer
zo groot als daarvoor, dan wordt in die situatie de reken
tijd 10 000 keer zo groot.
Reeds jaren wordt op verschillende plaatsen aandacht
geschonken aan het zoeken van een snelle sorteerrou-
tine. Toch zijn slechts twee methoden het meest interes
sant. De eerste methode, door Shell [1959] ontwikkeld,
vraagt in het geheel geen extra geheugenruimte voor het
opslaan van tussenresultaten en is bij de schrijver favo
riet door het feit dat de lengte van het eigenlijke sorteer-
gedeelte van een programma, waarin deze werkwijze is
verwerkt, zo gering is. Zie hiervoor ook de fig. 2 en 3. De
tweede methode, die bekend staat onder de naam
„Quicksort", is ontwikkeld door Hoare [1962] en is veelal
iets, doch niet spectaculair, sneller dan de eerste. Deze
methode wordt op verschillende wijzen gebruikt. Hierbij
kan „recursief" programmeren worden toegepast, waar
bij een routine dezelfde routine weer aanroept. Ten einde
ook weer de stappen terug te kunnen maken, wordt op de
zogenaamde „stack" in de computer een lijst bijgehou
den. Een taal als FORTRAN kent de mogelijkheid van
recursief programmeren niet. De „stack" wordt dan ver
vangen door een lijst waarin enkele waarden tijdelijk wor
den opgeslagen. De lengte van deze lijst is echter be
perkt, zodat daarvoor slechts een klein gedeelte van de
geheugenruimte van de computer behoeft te worden ge
reserveerd. Zowel bij de methode van Shell als van Hoare
neemt de rekentijd toe met ongeveer het aantal te sorte
ren waarden vermenigvuldigd met de logaritme van dit
aantal. Is het aantal waarden, zoals in bovenstaand voor
beeld, 100 keer zo groot als daarvoor, dan is de rekentijd
slechts ongeveer 200 keer zo groot.
Het is goed bij het sorteren van de coördinaten op de X-
waarde bij gelijke X-waarde te sorteren op de Y-waarde.
Na het sorteren kunnen dan gemakkelijk de meervoudig
vastgelegde waarden van een punt worden vervangen
door één enkele opslag ervan. Voor het terugvinden van
de juiste coördinaten van een punt is het immers niet
nodig te weten dat een punt in meerdere lijnen voorkomt.
Digitaliseren in een gescand kaartbeeld
Voor de verdere bewerkingen wordt nu beschikt over
twee bestanden. Het eerste bestand is uit de scanning
ontstaan, het tweede bestand is het bestand met punten
die gesorteerd zijn op de X-coördinaat. Dit kan ook een
bestand zijn waarin geen coördinaten staan, doch waarin
is aangegeven hoe een punt in het eerst genoemde be
stand is terug te vinden! Bij het afbeelden van de figuratie
op het beelscherm worden beide bestanden ingelezen.
Het eerste wordt gebruikt om de verbindingen tussen de
punten te visualiseren, het tweede om de punten te
markeren en om in te zoeken.
Nadat een punt waarvan de „juiste" coördinaten in het
tweede bestand dienen te worden gevonden, bij benade
ring op het beeldscherm is aangewezen, dient de compu
ter in dat bestand naar de juiste coördinaten van het punt
te zoeken. Bij dit zoeken in een gesorteerde reeks getal
len wordt gebruik gemaakt van een techniek die wordt
aangeduid met de term „binair" zoeken. Recent heeft
Van der Schans [1989] deze methode ook aangeduid. De
methode van werken is zeer logisch. Eerst wordt van de
op het scherm na transformatie van de coördinaten
naar RD-coördinaten gemeten coördinaat een waarde
afgetrokken, die verband heeft met de tolerans waar
binnen wordt gezocht. Een transformatie die nodig is om
dat het beeld met een zekere schaalfactor en met een
zekere verschuiving is gerealiseerd. Stel dat het bestand
uit 25 000 punten bestaat. De eerste stap is daarna om te
kijken wat de X-waarde van de coördinaat is van het punt
#include (stdio.h)
Sorteren van coördinaten op X-coördinaat
en bij gelijke X-waarde op Y-coördinaat
Versie in C. *1
main
typedef struct
long x;
long y;
coord;
coord h,xy[40];
int i,j,l,m,nm;
static int n=40;
FILE *fp;
fp-fopen("datin","r");
for (i=0;i(n;i
fscanf(fp,"%ld",&xy[i].x);
fscanf(f p,%ld ,&xy[i j .y);
fclose(fp);
Sorteren:
m-1;
do m»2*m; while (m<=n);
do
m (m-1)/2;
nm n m;
for (i-0;i(nm;l
18: l=j m;
if (xy[l].x)xy[j].x)continue;
if (xy[l).x- »xy[j].x)
Gelijke X-waarde aangetroffen.
if (xy[l].y)xy[j].y)continue;
h-xyü);
xyül-xyjl];
xyjl] h;
j=j~m;
if (j}=0)goto 18;
while (m)l);
Het resultaat:
for (i=0;Kn;i+ +)printf("%91d%9ld\n",xy[i].x,xy[ij.y);
exit(0);
Fig. 3. Uitlijsting van het sorteren van veertig coördinaten met de
sorteerroutine SHELL in C. Het eerste element van de array heeft,
zoals bij de programmeertaal C gebruikelijk, het volgnummer 0.
NGT GEODESIA 90 - 5
