A graphical system for geographical data processing in a minicomputer environment

Signal Processing 3 (1981) 253-257 North-Holland Publishing Company

A G R A P H I C A L SYSTEM F O R G E O G R A P H I C A L D A T A P R O C E S S I N G IN A M I N I C O M P U T E R E N V I R O N M E N T L. D E F L O R I A N I ,

G. D E T ' F O R I ,

B. F A L C I D I E N O ,

C. P I E N O V I

Istituto per la Matematica Applicata del C.N.R., Genova, Italy

V. G I A N U Z Z I Istituto di Matematica dell' Universit& di Genova, Italy

Received 24 October 1980

Abstract. In this paper a minicomputer system for geographical data processing for computer cartography applications is described. The main features of the system are: capability of processing irregularly distributed data points; interactive facility during the editing and map refinement steps; modular organization; use of minicomputer systems with standard display devices. At present the system is used to produce isarithmic maps for nautical applications.

Zusammenfassung. In diesem Artikel wird ein Minicomputersystem beschrieben, das geographische Daten fiJr die kartographic verarbeitet. Die wesentlichen Eigenschaften des Systems sind: es ist in der Lage, unregelm~iJ]igverteilte Datenpunte zu verarbeiten; interaktiver Zugang w~ihrend der Phase der Eingabe und Korrektur der Karte; modulare Organisation; Gebrauch von Minicomputersystemen mit Standardger~iten zur graphischen Ausgabe. Zum gegenw/irtigen Zeitpunkt wird das System dazu benutzt, Spezialkarten fiJr nautische Anwendungen zu erstellen. R6sum6. On d6crit dans cet article un syst~me de miniordinateur pour le traitement des donn6es g6ographiques avec application ~t la cartographie par ordinateur. Les caract6ristiques principales du syst~me sont: aptitude ~ traiter des points irr6guli~rement distribu6s; possibilit6 d'interaction pendant l'6dition et le raffinement de la carte; organisation modulaire; utilisation de syst~mes de miniordinateurs avec des atfichages standards. A pr6sent, le syst~me est utilis6 pour produire des cartes isarithmiques pour des applications nautiques. Keywords. Geographic data processing, automated cartography, graphic systems, contour mapping, interactive editors.

1. Introduction For several years many sophisticated computer m a p p i n g Systems, i n t e r a c t i v e o r n o n - i n t e r a c t i v e , h a v e b e e n in use. M o s t of t h e m r e q u i r e large c o m p u t a t i o n a l r e s o u r c e s a n d t h e r e f o r e can b e u s e d o n l y with big c o m p u t e r s . In m o s t cases it s e e m s to b e difficult to t r a n s f e r t h e s e p a c k a g e s to s m a l l e r m a c h i n e s , a n d this o p e r a t i o n gives rise to a c o n s i d e r a b l e r e d u c t i o n of t h e a m o u n t of d a t a which can b e p r o c e s s e d . O n t h e o t h e r h a n d , t h e use of m i n i - c o m p u t e r s , s u i t a b l y e q u i p p e d with g r a p h i c a l d i s p l a y devices, in a u t o m a t e d c a r t o g r a p h y a p p l i c a t i o n s has b e c o m e m o r e a n d m o r e diffuse. 0165-1684/81/0000-0000/$02.50

In this p a p e r w e p r e s e n t a g r a p h i c a l s y s t e m for m a p d a t a p r o c e s s i n g , d e v e l o p e d for use with m i n i c o m p u t e r s . O n e of t h e m a i n f e a t u r e s of t h e s y s t e m is t h e p r o d u c t i o n of high q u a l i t y t o p o graphic maps, indistinguishable from those obtained by hand. T h e e n t i r e p r o c e s s of d a t a analysis up to t h e final m a p d r a w i n g is d o n e a c c o r d i n g to t h e following two steps: - - g e n e r a t i o n of a d a t a s t r u c t u r e to s t o r e i n f o r m a t i o n c o n c e r n i n g t h e given d a t a p o i n t s a n d s u r f a c e r e p r e s e n t a t i o n b y m e a n s of c o n t o u r m a p s ; --interactive h a n d l i n g of c o m p u t e r r e p r e s e n t a t i o n of t h e g e n e r a t e d c o n t o u r s a n d g r a p h i c a l p r e s e n t a t i o n of t h e final result.

O North-Holland Publishing Company

254

L. De Floriani. et al. / Graphical system for geographical data

The first step cannot be performed interactively on a minicomputer because it requires considerable numerical computations and the use of mass storage. On the contrary, during the second phase, the user interacts with the system through a CRT display- in order to mark the desired changes on the isolines previously generated by the contour mapping algorithms. The system seems to be particularly advantageous due to its modular organization: any system section can be easily substituted without changing the entire system. At present the system is used at the Institute for Applied Mathematics of the National Research Council and at the Navy Hydrographic Institute of Genoa to produce nautical contour maps. It has also been used for generating input data for computer models of sea-wave motion simulation.

Automat i c

Manual

data

digitizing

acquisition

\

/ processing

1

Contour mapping J

I

Maps

\

,

'T . . . . I k

2. System description As shown in Fig. 1, the complete process of data handling up to the final map representation is performed through the various steps described below. 2.1. Data capture In our applications the depth values are obtained with two standard methods: -digitalization of already existent nautical maps; -measurements done by specially equipped boats. In both cases we obtain data values given at irregularly distributed data points especially when measurements done at different times or near the coast are merged together.

Interective session

4)

Plotting

I

Fig. 1. Processof constructionof a contour map.

2.2. Data structure generation In view of further numerical processing the system generates a list structure resident on disk, in which points and adjacency relationships are stored. Signal Processing

The structure is created by an algorithm which performs a Delaunay triangulation of the set of given data points [2]. In particular it can deal with areas of complex geometrical shape, including

L. De Floriani. et al. / Graphical system for geographical data

multiply connected regions and reentrant boundaries. The triangulation module can process up to 800 data points keeping the entire structure in core. In order to deal with larger quantities of data we have developed another triangulation processor which works on disk and requires greater computation times. 2.3. Contour mapping and gridding

On the triangulation the system can perform two kinds of processing: - contour mapping; -generation of a rectangular grid by using a simple linear interpolation scheme. Contours can be produced either by a contour map algorithm, which works directly on the triangular grid [2] or by a gridding process [3], followed by the application of a contour map algorithm for data on a rectangular grid [10]. The latter can also be used when the original data are already gridded. Both methods compute contours by linear interpolation; smoothed contour lines are produced after the graphical editing session. The direct method performs better in terms of computation times and numerical accuracy in the results. The gridding process is particularly useful when rectangular grid output is required, e.g. production of input data for wave propagation models [4]. 2.4. Interactive editing

An interactive editing of the previously produced contours can be done by the user either to correct errors, which can occur during digitalization and data processing, or to insert new graphical information into the map [7]. In this phase the user directly checks the map, verifying the line drawings on a CRT display. During the editing session the system allows, by means of a series of simple commands and through the use of input devices: - insertion and deletion of points or lines; - joining and disjoining of contour lines;

255

-display of information about the map (lists of points, of lines etc.). The line editor provides not only the means to detect and correct drawing errors, but it can also be used to check the various parts of a map and to merge separately processed maps into one map. Core requirements of this module are independent from the amount of information processed, since line points are stored into a working file and only a small part of them needs to remain resident in core.

2.5. Final refinement of the map

As the graphical editing step has been completed the contour lines are conveniently smoothed to produce fair and natural curves and the map is equipped with those graphical attributes, which improve comprehension and graphical presentation of the results. First, on user request, a selection of the main points of the contour lines can be accomplished for instance when the map reproduction scale is smaller than the original one or when the distance between two consecutive points is less than the resolution of the graphical device [5]. The smoothed contours are then obtained by using curves with tension generated by a completely local interpolation method [6]. This feature allows the arc length between two points to be interactively changed, for example to remove possible line crossings, without modifying the entire curve. Finally the user can insert interactively alphanumeric strings and explanatory symbols or require information about the data processing done to be displayed in selected positions on the curves.

3.

Conclusion

To increase system portability, we have tried to reduce as much as possible nonportable and environment-dependent system procedures. For Vol. 3, No. 3, July 1981

256

L . D e Floriani. et al. /

Graphical system for geographical data

this purpose the system has been organized into a modular structure. It has been written entirely in F O R T R A N s t a n d a r d - a n d verified by the PFORT Verifier [ 9 ] - and, furthermore, it makes use of a basic graphic package conforming to the recent proposal for graphical software standardization. The system has been implemented on a PDP 1 1 / 4 0 with 128 K bytes of core and uses a CRT display Tektronix 4012 and a plotter Calcomp 563 for input - output graphical operations.

Finally we present a complete example of the various steps of system operation on a set of about three hundred data points, as shown by Figs. 2-8. To give an estimate of the computation times involved during the processing phase, we can say that the generation of the triangular grid on eight hundred points requires about five minutes and fifty seconds, and the contour map production for ten levels about one minute and twenty five seconds.

+

4444- 44- 4-4- 444444- 4-4- 4-4- 44-4-444- 444-4-444444- 4-44-44-44444- 4- 447, 44-++. 4- 444- 4- 4- 4-4444- 4+444- 4444- 4- + 4 - 4 - 4+44- 4-44- 4-4- 4+

4-"

4- 4-4~ .4+ 4-

4- 44-4-

t .4-.

4-44-

4-4- 4- 4- ~-4-~-~'~'Z 4-4--

4-

4-4- 4- ~,.4-4-44- 4-44-

~ +4-4-4-'4-*_'~_4-? % ~

:

4-~4-

4-4-44-4-

4-

4-+ +

4-4-4-

4-

4- 4-4- 4-

4-

*,

4-4- 4- *4-

4-

4-

4-

4-4- 4-4- 4- 4-~ 4-4 t4- ÷4-4-44-4- 4- 4 - t D 4 - 4 - 4 4-* 4-

44-

44-

4-4- 4- 44.~-444- 4- 4-444"++++4"4" 4-4-

4- 4-4-

44-

4-

4-

4-

~. ~

4-

4-

4- 4- 444444444-444- 4444-

F i g . 2. A set of randomly distributed data points.

F i g . 4. Contour map produced directly on the triangular grid.

Signal Processing

Fig. 3. Delaunay triangulation.

F i g . 5. The map of Fig. 4 after the interactive editing.

L. De Floriani. et al. / Graphical system for geographical data

Fig. 6. The map after the automatic point selection (the contour lines have been reduced from 496 to 304 points).

257

Fig. 7. Smoothed contour lines.

Fig. 8. Final map.

References

[1] J.C. Davis, M.J. McCullagh, Display and Analysis of Spatial Data, Wiley - Interscience, London, 1975. [2] L. De Floriani, B. Falcidieno, C. Pienovi, Un metodo di triangolazione di regioni piane non convesse, Ouaderni IAC, serie III, No. 107, Roma, 1980. [3] L. De Floriani, G. Dettori, B. Falcidieno, C. Pienovi, Processi di elaborazione per rilevamenti e dati sperimentali, X X V I I Congresso per l'elettronica, Roma, 1980. [4] L. De Floriani, An interactive graphic system for computer analysis of wave refraction models, 2nd Intern. Congr. Numerical Methods for Engineering, Paris, 1980.

[5] G. Dettori, B. Falcidieno, Un algoritmo per la caricatura della linea di costa, Quaderni Istituto Idrografico della Marina, F.C. 1102, Genova, 1980. [6] G. Dettori, Interpolation for CAD using curves with tension (to appear). [7] V. Gianuzzi, I1 sistema ESAC: un editore grafico intervattivo per l'edizione di mappe di curve di livello, Atti del 69 ° Congresso della Societdt Geologica Italiana, Perugia, 1978. [8] G. Nagy, S. Wagle, Geographical data processing, Computing Surveys, Vol. 11, No. 2, 1979. [9] B.G. Ryder, The PFORT Verifier, Software Practice and Experience, Vol. 4 , 1974. [10] W.V. Snyder, Algorithm 531 - c o n t o u r plotting, A.C.M., Trans. Mathematical Software, Vol. 4, No. 3, 1978. Vol. 3, No. 3, July 1981