UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Gids : a geographical information system Yan, Joel Zachary 1973

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1973_A6_7 Y35.pdf [ 9.08MB ]
Metadata
JSON: 831-1.0052000.json
JSON-LD: 831-1.0052000-ld.json
RDF/XML (Pretty): 831-1.0052000-rdf.xml
RDF/JSON: 831-1.0052000-rdf.json
Turtle: 831-1.0052000-turtle.txt
N-Triples: 831-1.0052000-rdf-ntriples.txt
Original Record: 831-1.0052000-source.json
Full Text
831-1.0052000-fulltext.txt
Citation
831-1.0052000.ris

Full Text

GIDS - A GEOGRAPHICAL INFORMATION SYSTEM by Joel Zachary Yen B.Sc, University of Toronto, 1970. A Thesis Submitted i n P a r t i a l Fulfilment of the Requirements f o r the Degree of Master of Science i n the Department of Computer Science We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA September, 1973. In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree a t the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and study. I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y purposes may be g r a n t e d by the Head o f my Department or by h i s r e p r e s e n t a t i v e s . I t i s understood t h a t c o p y i n g or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a llowed w ithout my w r i t t e n p e r m i s s i o n . Department o f Computer Science The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada Date October 8, 1973 i ABSTRACT A system f o r the Input, r e t r i e v a l , display, and overlay of 2-dimensional geographical data sets has been developed. The Geographical Information and Display System (GIDS) has been designed according to the following c r i t e r i a * the system should be easy to use, easy to evolve, problem-independent, i n t e r a c t i v e , and graphic-oriented. Thematic map data are encoded by l o c a t l o n a l data elements (points, l i n e s , or poly-gons) over which some at t r i b u t e i s homogeneous. Both the at t r i b u t e and l o c a t l o n a l data are then input to GIDS and stored i n sequential f i l e structures, from which they can be s e l e c t i v e l y r e t r i e v e d , displayed, and manipulated at user request. A l l user requests to the system may be expressed i n t e r a c t i v e l y v i a an E n g l i s h - l i k e command language. Each command, corresponding to one operation such as input, display or overlay, i s interpreted and executed by an independent module which accesses the data through a common input/output framework. GIDS has proved useful to planners and researchers because of Its a b i l i t y to display and rel a t e data from d i f f e r e n t maps. 1 1 TABLE OP CONTENTS CHAPTER PAGE INTRODUCTION AND OPENING REMARKS 1 1 TUTORIAL ON GEOGRAPHICAL INFORMATION SYSTEMS . . 4 1.1 THE PROBLEM IN GENERAL 4 1.1.1 What are Geographical Information Systems 4 1.1.2 Motivation f o r Geographical Information Systems 5 1.1.3 Types of Geographical Information Systems 7 1.2 THE PROBLEM IN MORE DETAIL -POLYGON PLANNING SYSTEMS . . 10 1.2.1 An Example 11 1.2.2 Functional Requirements of the System 15 1.2.3 Data Ac q u i s i t i o n 15 1.2.4 Data Encoding 17 1.2.5 Conversion of Coordinate System . . 19 1.2.6 Display 19 1.2.7 Computation 20 1.3 THE GRID VERSUS THE POLYGON APPROACH . . 22 1.4 SYSTEMS OF AUTOMATED CARTOGRAPHY . . . . 29 1.5 STATE OF THE ART 30 1.6 EXAMPLES OF EXISTING SYSTEMS 32 1.6.1 Grid Systems 32 1.6.2 Polygon Systems 3^ 1.6.3* Comparison of GIDS to Other Polygon Systems 3& i l l CHAPTER PAGE 2 INTRODUCTION TO GIDS 38 2.1 DESIGN CRITERIA 39 2.2 GIDS TREATMENT OF GEOGRAPHICAL DATA . . . 42 2.2.1 The Two Components of Geographical Data 42 2.2.2 Points, Lines, and Polygons 44 2.2.3 Encoding Schemes 44 2.3 FUNCTIONS OF THE SYSTEM 46 2.4 INTRODUCTION TO THE IMPLEMENTATION . . . 47 2 .4.1 Basic Method of Operation 47 2.4.2 Sequential F i l e Processing 47 2 . 4 . 3 Program Structure of GIDS 49 2 .4.4 Memory Structure of a GIDS run . . . 50 2 .4.5 Implementation Language $2 2.5 INTRODUCTION TO THE COMMAND LANGUAGE . . 5^ 2.6 SAMPLE OF SYSTEM USE 5^ 3 FOUNDATIONS OF THE SYSTEM 58 3.1 FINAL FILE STRUCTURES 58 3.1.1 Introduction 58 3.1.2 Logical Data Structure f o r 1 Polygon. 59 3.1.3 Physical Data Structure of 1 Polygon. 63 3.1.4 S p l i t and Merged F i l e s 65 3.1.5 Relative Advantages of S p l i t and Merged F i l e s 66 3.1.6 Detailed Record Formats* 70 3.1.7 Headers* 71 3.1.8 How Headers are Constructed at Execution Time* 74 CHAPTER PAGE 3 3.2 SELECTION AND THE COMMAND LANGUAGE STRUCTURE 75 3.2.1 Introduction 75 3.2.2 Selection vs. Retrieval 75 3.2.3 Three Types of Selection 76 3.2.4 GIDS Filenames and Qualified F i l e s . 77 3.2.5 Fieldnames 79 3.2.6 Syntax of Numerio Selection . . . . 80 3.2.7 Implementation of Numeric Selection. 82 3.2.8 Command Processing 83 3.3 INPUT/OUTPUT STRUCTURES FOR THE PROGRAMMER* . 84 3.3.1 Introduction* 84 3.3.2 F i l e Numbers* 84 3.3.3 F i l e Tables* 86 3.3.4 F i l e Opening Routine—TABSEL* . . . 86 3.3.5 Sequential Read Route-TREAD* . . . . 88 3.3.6 Sequential Write Routine-TWRITE* . . 90 3.4 HOW TO PROGRAM A COMMAND USING FOUNDATION ELEMENTS OF GIDS" 92 4 OTHER PARTS OF THE SYSTEM 94 4.1 THE INPUT SUBSYSTEM 94 4.1.1 Introduction 94 4.1.2 GIDS Approach to Data Input . . . . 94 4.1.3 A Quick Survey of Four D i g i t i z i n g Systems 95 4.1.4 GIDS D i g i t i z i n g Procedure . . . . . 98 4.1.5 Input Procedure 99 4.1.6 Experience with the Input System . . 103 V CHAPTER PAGE 4 4.2 THE GRAPHICS SUBSYSTEM 104 4 .2.1 GIDS Approach 104 4 .2.2 Graphics Functions . 104 4 .2 .3 Graphics Commands 105 4.2.4 Shading and Geometric Symbolism . . . 110 4 .2.5 Graphics Devices Available 115 4 .2.6 Device-Independent Graphics and Other Concepts 118 4 . 2 . 7 The O r i g i n a l Graphics Design 119 4.2.8 Implementation of Device Independence 121 4 . 3 THE INTERSECTION SUBSYSTEM 125 4 .3.1 Motivation—Regional Base Transformation 125 4 .3.2 Intersecting Two Polygons 127 4 .3.3 Intersecting Two Sets of Polygons . . 136 4.3.4 S t r i p Sort i n More D e t a i l 141 4 .3 .5 The Current State of the Intersection Subsystem 148 5 CRITIQUE OF GIDS 149 5.1 STRONG FEATURES OF DESIGN 150 5.2 WEAKNESSES OF DESIGN 151 5.3 COST TO USE GIDS 152 5.4 REAL USEFULNESS SO FAR 15^ v i CHAPTER PAGE 6 FUTURE DEVELOPMENTS OF GIDS 156 6.1 INTRODUCTION 156 6.2 NEW USES FOR GIDS , 156 6.2.1 With Census and Address Data 156 6.2.2 As A Graphical Tool for Regional Simulations 157 6.3 EXTENSION-ABBREVIATED COMMANDS 159 6.4 GEOGRAPHICAL SELECTION 1§1 6.4.1 Theory 161 6.4.2 Implementation 161 6.5 SUMMARY 165 BIBLIOGRAPHY 166 APPENDIX 170 A. SUMMARY OF THE COMMAND LANGUAGE 170 B. FIELDNAMES FOR LOCATIONAL FILES 173 C. SAMPLE RUNS WITH GRAPHICAL OUTPUT 174 D. LEGEND OF LAND USE CODES 183 E. LISTING OF THE COPY COMMAND ROUTINE 183 v i i LIST OF TABLES TABLE PAGE I. A COMPARISON BETWEEN GRID AND POLYGON SYSTEMS . . 24 II . THE NUMBER OF POINTS REQUIRED TO ENCODE A SQUARE ON ITS SIDE TO AN ACCURACY OF d BY THE GRID AND POLYGON METHODS . 2 7 I I I . THE DIMENSIONING ITEMS AND THEIR USES FOR POINTS, LINES AND POLYGONS 62 IV. A COMPARISON BETWEEN SPLIT AND MERGED FILES IN VARIOUS PROCESSING SITUATIONS 69 V. THE VALUES OF FILE NUMBERS FOR DIFFERENT TYPES OF FILES UNDER GIDS 85 VI. A COMPARISON OF FOUR SYSTEMS FOR DIGITIZING POLYGONAL MAPS 98 VII. METHOD OF SHADING ON DIFFERENT DEVICES I l l VIII. THE EFFECT OF MAP SIZE AND THE TYPE OF SHADING ON THE COST OF DRAWING ON THE PLOTTER 114 IX. THE RESPONSE TIME AND CPU TIME TO READ SPLIT FILES OF VARIOUS SIZES AND LIST TWO RECORDS . .153 v l i i LIST OF FIGURES :GURE PAGE 1.1 Location I d e n t i f i e r s for Geographical Information Systems 8 1.2 Geographical Data Available f o r a Typical Town. . 12 1.3 Two Typ i c a l Requests to a Polygon Planning System 14 1.4 Two Methods of Encoding a Polygon 18 1.5 Two Different Projections of the Same Polygon . . 19 1.6 Two Coverages and the Resulting Overlay Coverage. 21 1.7 The Grid and Polygon Approach to Decomposing Several Liquids 23 1.8 A Set of Polygons and the Resulting Adjacency Graph 26 1.9 The Approximation of a Square by Grid and Polygon Methods 28 1.10 The Level of Development of Various Phases of Geographical Information Systems 33 2.1 The Two Components of Geographical Data 43 2.2 The Boundary Encoded Representation of a Point, Line and Polygon 45 2.3 Structure of a GIDS Run 48 2.4 Block Diagram of GIDS .„ 51 2.5 A Map of Core Memory During a GIDS Run 53 2.6 Sample Plot of a Map with Land Use Codes . . . . 57a 3.0 The Two Types of Records in a GIDS F i l e 59 3.1 The Logical Data Structure of a Polygon 60 3.2 The Minimal Bounding Rectangle of a Line and Polygon 61 ix FIGURE PAGE 3.3 Physical Data Structure of One Polygon 65 3.4 A Land Use Map, the Corresponding S p l i t F i l e s and Merged F i l e 67 3.5 Three Types of Selection 78 3.6 F i l e Tables 87 3.7 The Operation of TREAD When Both a Locatlonal and a Descriptive F i l e are Being Read . . . . 89 3.8 A View of the Data as stored on the F i l e and as Presented to Processing Programs 91 4.1 A Polygonal Map as D i g i t i z e d by the Map/Model System 96 4.2 The D i g i t i z e r Configuration used by GIDS . . . . 100 4.3 The GIDS Input Procedure 101 4.4 A Map of 3 M u n i c i p a l i t i e s Symbolized i n Various Ways 106 4.5 Sample Output Produced by a DRAW Command Followed by a SUPERIMPOSE Command 109 4.6 a An Example of P a r a l l e l Line Shading on the Calcomp 112 b An Example of Cross-Hatchlng on the Calcomp 113 4.7 A Plot of Vancouver on the Dot Printer 117 4.8 A Plot of Three M u n i c i p a l i t i e s on the Line Printer 117 4.9 The Ori g i n a l Design of the Graphics Subsystem . 120 4.10 Device Independent Graphics 122 4.11 The Switch Method of Device Independence . . . . 123 4.12 The Sandwich Method of Device Independence . . . 124 4.13 Regional Base Transformation . . . . 126 4.14 The Line Extension Method for Point i n Polygon Determination 128 X FIGURE PAGE 4.15 The Smallest Rectangle Method f o r Point i n Polygon Determination . 129 4.16 The Three Stages in Intersecting Polygons A & B . 131 4.17 The Structure of the Intersection Routines Showing the Extendible Design 132 4.18 Intersection of the Minimal Rectangles Can Often Avoid Intersection of the Polygons 133 4.19 Testing i f the Bounding Rectangle of Polygon A i s Contained in Polygon B 134 4.20 Reducing the Polygons Before Intersection . . . . 135 4.21 Using an Overlaid Grid as an Index to the Polygons 137 4.22 Polygons from the Same Map Ordered i n Several Ways in Sequential F i l e s 139 4.23 Sequencing Polygons in a Sequential F i l e as Expressed i n a Problem Solving Context . . . . 143 4.24 Intersecting Polygons with the S t r i p , and then Intersecting Two Strips of Polygons 145 4.25 The Method Used by the INTSL Routine to Intersect a Polygon P with a S t r i p of Polygons Stored in the B-List 146 4.26 Two S t r i p Sorted Maps, and a Typical A - L i s t . . . 147 6.1 Possible Extensions to GIDS 156 6.2 Inputlng Census or Address Data to GIDS 158 6.3 GIDS as a Graphical Tool for Regional Simulations 159 6.4 Regions Selected from a Data F i l e by Different Selection C r i t e r i a . . . . . 162 7.1 A Plot of a Land Use Map for the Vancouver Area . 180 7.2 Residential Land Shaded by Density 181 7.3 A Map of Recreational Land (enclosed i n t r i a n g l e s ) , with Residential Land Superimposed on i t . . 182 *«#*#** x i ACKNOWLEDGEMENTS The GIDS project has received f i n a n c i a l support from the Department of Computer Science at UBC, the Greater Vancouver Regional D i s t r i c t Planning Department, the Depart-ment of Forestry at UBC, the I n t e r - I n s t i t u t i o n a l Policy Simulator (HPS) project, and the National Research Council of Canada. The GIDS system has been developed over the past two years by computer science students under the guidance of James L. Parker and myself. I would l i k e to thank Jean Jervis for her excellent job on the I/O routines (Section 3*3), Dale Troyer for his good work on the intersection system (Section 4.3) and device independent graphics,Sum Mock for his Job -on the f l e x i b l e graphics system (Section 4 . 2 ) , Marvin Avery for his enthusiasm and e f f o r t s on the input system (Section 4.1), and Dr. Parker for his help in c l a r i f y i n g f i l e struc-tures and s e l e c t i o n . I would also l i k e to thank Wing Lau and Vincent Manis for the selection routines, Tom Mathews f o r the shading routine, and a l l the students i n the aggregate group and the Group of Twelve for t h e i r programming assistance. I t has been a pleasure to work with a l l of them. My own contribution has involved many aspects of the system design as well as coordination of the implementation. Some of the aspects I have worked on i n d e t a i l are the super-v i s o r routine, the header structures, f i l e creation, emptying, and copying routines, and in less d e t a i l on the s e l e c t i o n , input, graphics, and aggregation of data. I would also l i k e to thank Darlene Belford and Andrew Clement for h e l p f u l suggestions i n the preparation of this thesis, and Dr. Doug Seeley f o r his constructive c r i t i c i s m . I wish to acknowledge my supervisor, Dr. Parker, f o r his d i r e c t i o n , and Peter George of the Gmeater Vancouver Regional D i s t r i c t for his support and e f f o r t s in making the system useful. F i n a l l y , I want to express my h e a r t f e l t thanks to my wife, Toby, for the advice, encouragement and understanding she has given me. JOEL Z. YAN 1 INTRODUCTION AND OPENING REMARKS With Increasing concern in urban and environmental studies, there has been a correspondingly rapid development of information systems to process environmental data. Most of these geographical information systems have been designed for one p a r t i c u l a r study, and even then have often not been used up to t h e i r potential because of the d i f f i c u l t y i n using them. According to experts at the recent UNESCO/IGU conference, the l e v e l of system use i s far behind the l e v e l of hardware and software technology (Tomlinson, 1972, Intro-duction). At the University of B r i t i s h Columbia we have developed the Geographical Information and Display System (GIDSt), a system that can be applied to any 2-dimensional data and the associated a t t r i b u t e s . Compared to oMiea? systems GIDS is powerful not so much in the functions i t performs as in i t s ease of use and easy e x t e n d i b i l i t y . GIDS can be used by a non-computer expert either i n t e r a c t i v e l y or in batch v i a a command language that he can learn within an hour. Some of i t s other good features are i t s v e r s a t i l e device-independent graphics and powerful access methods. The prime weakness i s i n data input. The description of GIDS presented in thi s thesis has two p r i n c i p a l thrusts. The f i r s t i s to provide docamehfcatfcon of the system for those who would extend i t , and the second 2 Is to c a l l p a r t i c u l a r attention to those aspects of the design which are of more general interest. To serve the f i r s t end, i t has been necessary to include quite detailed descriptions in some places. These sections have been marked with an aste r i s k . In serving the second goal, the following sections are the most noteworthy! section 3.1 ( f i l e structures); section 3.2 (selection); section 4.2 (device independent graphics), and section 4.3 ( s t r i p s o r t i n g ) . In the author's opinion i t i s more informative to describe the evolution of a system than to present, de facto, i t s f i n a l design. Therefore, throughout this t h esis, and e s p e c i a l l y in Chapter 4, the system w i l l be described in terms of the i n i t i a l v i s u a l i z a t i o n , problems encountered with this design, and the reworked design that ameliorates these problems. Chapter 1 serves as a t u t o r i a l on geographical i n f o r -mation systems f o r the u n i n i t i a t e d . It describes the general problems and reviews current work. Chapter 2 then introduces the geographical information system that we have developed at the University of B r i t i s h Columbia. Chapters 3 and 4 describe the system implementation in some d e t a i l . The former chapter i s concerned with the foundation elements and the l a t t e r with the other parts of the system. 3 Chapter 5 presents an evaluation of the system and Its r e a l usefulness to date. F i n a l l y , Chapter 6 I l l u s t r a t e s possible extensions of GIDS and summarizes the work. *#«***« 4 CHAPTER 1 A TUTORIAL ON GEOGRAPHICAL INFORMATION SYSTEMS The purpose of t h i s chapter Is to Introduce the unin i t i a t e d reader to the realm of geographical Information systems by describing the problems and the state of the a r t . The discussion w i l l begin at a low l e v e l since i t assumes no previous f a m i l i a r i t y with the f i e l d . More detailed reviews have been written elsewhere (Tomlinson, 1970, 1972; Dueker, 1966). 1.1. THE PROBLEM IN GENERAL 1.1.1 What are Geographical  Information Systems? A geographical Information system may be defined as an information system which Is concerned with the storage, r e t r i e v a l , analysis or display of geographical data. The necessary c h a r a c t e r i s t i c f o r data to be geographical i s that i t have a location i d e n t i f i e r as part of the data element. For instance, census data i s geographical i n the sense that i t Is associated with a l o c a t i o n a l unit such as a census t r a c t , but a table of logarithms i s non-geographical as i t i s not related to any p a r t i c u l a r l o c a t i o n . Observa-tions of a l t i t u d e , temperature, and s o i l type are further examples of geographical data. Geographical information systems d i f f e r from other information systems in that the data i s manipulated and 5 r e t r i e v e d by geographic c r i t e r i a and the output i s generally graphical. The l o c a t l o n a l data i d e n t i f i e r s can be treated l i k e any other data items for some processing operations such as summarizing; however, the operations of data capture, i n i t i a l encoding, display and r e l a t i n g of geographical variables are s u b s t a n t i a l l y more complicated for the location i d e n t i f i e r , often req u i r i n g specialized equipment and software. Geographical data processing has been defined not as a f i e l d i n i t s e l f but as the common ground between information processing and the many f i e l d s u t i l i z i n g s p a t i a l analysis techniques (Tomlinson, 1972, Intro.). It i s an i n t e r - d i s c i p l i n a r y area that has importance i n f i e l d s as diverse as computer science, geography, planning, sociology, and cartography. It i s an exciting expanding area which w i l l be of increasing importance in the future. 1.1.2 Motivation f o r  Geographical  Information Systems Interest i n geographical information systems has been motivated by an increasing concern with better management of our urban and natural environments. Experience with ecolo-g i c a l systems has influenced us to examine the interactions between components of a system as well as looking at the in d i v i d u a l components themselves. Often the most important feature of environmental data i s not the presence or absence 6 of sets of c h a r a c t e r i s t i c s but the relationships between these c h a r a c t e r i s t i c s in space. To study these r e l a t i o n -ships decision-makers require ample information on a l l aspects of the problem area and convenient tools for r e l a t i n g t h i s information together. T r a d i t i o n a l l y , t h i s data i s obtained from various sources and i s hence found i n several forms—as maps at various scales, projections and resolutions, and as tables of a l l sorts. Under these circumstances geographical systems are h e l p f u l to manage the large volumes of data, to r e l a t e d i f f e r e n t data sets, and to analyze i n d i v i d u a l data sets. They can use known techniques 1 for converting the map data to a common projection and then perform functions such as superimposing maps which help r e l a t e this data. Geographical systems can also perform many useful computations cheaper or faster than man. For example, Tobler points out that there e x i s t programs which can calculate and plot a 17 by 22 inch map of the world on some obscure projection for about #20 t o t a l cost, whereas no draftsman would do the same for less than #100 (Tomlinson, 1970, p. 13^). Many of these programs are available through the Geographical Program Exchange (Wittick, 1972). 7 1.1.3 Types of Geographical  Information Systems Within the broad framework of geographical i n f o r -mation systems there i s a wide spectrum of systems. Two convenient bases for c l a s s i f y i n g these systems are the type of l o c a t l o n a l i d e n t i f i e r used and the most important functions performed. 1.1.3.1 Types of Location  I d e n t i f i e r Used One important feature of a geographical information system i s the type of location I d e n t i f i e r i t uses. In the introduction to Geographical Data Handling (Tomlinson, 1972), there was an i l l u s t r a t i o n of four types of location iden-t i f i e r (see F i g . 1.1)t 1) external index; 2) coordinate reference; 3) a r b i t r a r y g r i d ; 4) e x p l i c i t boundary. The type of location i d e n t i f i e r employed to a large extent determines the functions a system can perform, and the techniques i t must apply to perform these functions. The external index serves to i d e n t i f y each data element as belonging to a p a r t i c u l a r geographical area such as a census t r a c t or municipality, but does not convey r e l a t i v e l o cation without the use of some external cross-index. The external index can be used for s t a t i s t i c a l 8 (The figure below was taken from Geographical Data Handling. (Tomlinson, 1972)). Census T r . Pop 101 2368 102 172 103 4532 104 1628 10S 723 • • 101 102 105 104 103 EXTERNAL IN0EX COORDINATE REFERENCE ARBITRARY GRID EXPLICIT BOUNDARY Figure 1.1 Location I d e n t i f i e r s systems. f o r geographical information 9 grouping of data, but not f o r p l o t t i n g or most other geographical manipulations. In the coordinate reference a single point i s i d e n t i f i e d f o r each region. This type of l o c a t l o n a l i d e n t i f i e r permits p l o t t i n g and grouping into a r b i t r a r y areas defined by polygons. Both the a r b i t r a r y g r i d and e x p l i c i t boundary loc a t i o n i d e n t i f i e r s provide a more detailed view of the v a r i a t i o n in the observable over space. In the g r i d case, the data i s recorded for each square i n a g r i d . This represents an abstraction of the data in order to simplify computer processing. In the e x p l i c i t boundary case, the boundaries of the regions themselves, (defined a r b i t r a r i l y , administratively, or by data values) are recorded. The boundary i s almost always approximated by a series of straight l i n e s , hence turning an a r b i t r a r y region into a polygon. Both the g r i d and polygon i d e n t i f i e r s permit extensive display and manipulation c a p a b i l i t i e s such as outline maps, overlay and area calculations. Later in this chapter the g r i d and polygon approach w i l l be compared i n d e t a i l , and examples of each type of system w i l l be given. 1.1.3.2 Types of Systems  by Their Use Within the broad c l a s s i f i c a t i o n of geographical information systems (as defined in the previous section) there are several quite d i f f e r e n t types of systems. Some systems deal mainly with networks (Witiuk, 1973; Rapp et a l , 1971) and related problems such as finding minimal paths. 10 Automatic cartography systems are concerned with auto-mating map production and hence are oriented towards 2 accurate and sophisticated display. F i n a l l y , there are geographical systems for mapping and manipulating 2-dimensional areal data for use ln planning or research. This l a s t class of system w i l l be the focus for the r e s t of the chapter. 1.2 THE PROBLEM IN MORE DETAIL POLYGON PLANNING SYSTEMS In Section 1.1 some of the elements common to a l l geographical information systems were introduced. Now the p a r t i c u l a r problem area to be tackled by t h i s work i s described; namely, polygon systems primarily for planning applications. GIDS i s one member of t h i s class of geo-graphical information systems. Polygon systems derive t h e i r name from the fact that they encode area! data by polygonal l o c a t i o n a l Iden-t i f i e r s . The polygonal data handled i s usually ln the form of coverages. A coverage i s defined as a set of non-overlapping polygons which are homogeneous in some charac-t e r i s t i c and cover the study area. For instance, the i n t e r i o r of each polygon in a land use coverage has a A more detailed overview of automatic cartography i s given in Section 1 . 4 . 11 uniform land use. This requirement that data be homogeneous within each polygon in the coverage i s fundamental to the polygon approach. We w i l l lead off the discussion with an example of a s i t u a t i o n where a polygon planning system would be useful and then describe various functions required of such a system. 1.2.1 An Example It i s i l l u s t r a t i v e to consider a simple example of a polygonal system. Consider the f i c t i o n a l case of Boomtown, B r i t i s h Columbia. The following geographical data i s available to the l o c a l planning department! a zoning map, land use map, s o i l type map, and a map showing both the major streets and the locations of the l o c a l sawmills (see Fig . 1.2). As the figure shows, these maps are not a l l at the same scale or accuracy, perhaps because they have been prepared by d i f f e r e n t agencies. These maps i l l u s t r a t e some of the d i f f e r e n t types of l o c a t l o n a l data. The f i r s t three maps consist of polygonal data, and constitute three coverages for Boomtown. The 3 sawmills are point data and the streets ©re l i n e data. In each case the i m p l i c i t assumption i s that data i s homogeneous over each l o c a t l o n a l data element. 3 l f one were interested in observed t r a f f i c flows over these streets, one would have to treat these streets as a network rather than a c o l l e c t i o n of independent l i n e s . Figure 1.2 ^Geographical data available for a t y p i c a l town. 13 This homogeneity i s not always straightforward. The boundaries of the zoning regions are determined administra-t i v e l y v i a the town zoning regulations. However, the land use regions are not s t r i c t l y homogeneous; land use boundaries are not determined u n t i l a f t e r a decision on the r e s o l u t i o n , many observations i n the f i e l d , and some subjective judgement. Given t h i s data, two t y p i c a l requests from the Boomtown planners are described below. Then the output i s shown (Pig. 1.3) and the required system c a p a b i l i t i e s are outlined. Request #1» Plot a l l land that i s zoned for i n d u s t r i a l purposes. Superimpose on top of that the street network (to give an indication of the r e l a t i v e geography) and a l l the sawmills. This output could be used to check that a l l the sawmills are located within the i n d u s t r i a l l y zoned land. Request #2t Calculate and p r i n t the area of each s o i l type on the land shown to have a use of vacant. Also plot the s o i l s map with vacant land shown on top. This output could be used to plan the future zoning of the vacant l a n d — f o r agriculture or houses depending on the type of s o i l . The f i r s t step before answering these requests i s to encode a l l the data and store l t in computer memory in some common scale, and coordinate system. 14 To service the f i r s t request requires the c a p a b i l i t y to select polygons on the basis of the i r attributes and to draw maps on top of each other with some graphical output device. P l o t t i n g requires having a boundary representation of the polygons. To answer the second request requires the a b i l i t y to f i n d the intersection of the vacant land use polygons and the s o i l polygons. This procedure, known as overlay, i s described in Section 1.2.7. Request #l i Plot the i n d u s t r i a l zoned land, the streets and the sawmills. (Note that sawmills 1 and 2 are outside the indus-t r i a l l y zoned land) In d u s t r i a l Request #2t Plot the s o l i type on the vacant land, and calculate the areas. Area=2.0 Area=5.1 Area=10.5 Land use vacant sand 12.5 vacant peat S o i l Type Area 5.1 Figure 1.3 Two t y p i c a l requests to a polygon planning system. 15 1.2.2 Functional Requirements  of the System We now state s p e c i f i c a l l y the major functions required of the polygon planning systems we w i l l be con-sidering. These systems must perform the following operations i n a f a i r l y convenient and economical fashion: 1) data input including data encoding, conversion to a common coordinate system, and f i l e storage; 2) r e t r i e v a l and updating of selected records; 3) v e r s a t i l e data display; 4) various computations including the Intersection of two coverages. 1.2.3 Data Acquisition The f i r s t stage in data input i s data a c q u i s i t i o n . There i s a great range of types of data and of sources of data. Areal c o l l e c t i o n units can be points, l i n e s , polygons or g r i d s , and there can be a temporal framework as w e l l . Data may come from maps, a e r i a l photographs, surveys, 4 censuses, tables of observations, or remote sensing. For instance, the SKYLAB space laboratory w i l l conduct a regular photography program of the earth. In the c o l l e c t i o n of a data base l t i s of paramount importance to follow a few simple rules to enable a l l the 4See Section 1 of Tomlinson (1972) for a very thorough report on remote sensing techniques. 16 data to be re l a t a b l e at a l a t e r time. Parker (1971 a) has described some of these r u l e s . Other rules that hold for a l l geographical systems, not only polygon systems, are given below. Rule 1* Decide on the type of location I d e n t i f i e r according to the functions wanted from the system. As described e a r l i e r (Section 1.1.3) there are four types of location I d e n t i f i e r , each with d i f f e r e n t c a p a b i l i t i e s and overhead costs. The type with the minimum overhead that performs the required functions should be chosen. Rule 2: Decide on a coordinate system which i s appropriate for the study area and then ensure that a l l data is observed in thi s coordinate system or can be converted to i t . If the study area i s only a few miles across, then even though i t Is on a spherical earth i t i s very nearly planar and a rectangular coordinate system w i l l s u f f i c e . However, i f the study area covers a few hundred miles and there i s a concern with accuracy of areas, maps of area-preserving projection should :jbe chosen. The Universal Transverse Mercator (UTM) preserves areas reasonably well for Canada. The Mercator projection, however, does not. It projects points from the sphere onto a v e r t i c a l cylinder tangent at the equator and hence enlarges the areas near the poles. Rule 3« Decide on the s p a t i a l resolution and s p a t i a l frequency of the data,based on the requirements of the study and ensure that a l l data used passes these l i m i t s . The s p a t i a l resolution i s defined as the size of areal unit over which data i s to be collected and the s p a t i a l frequency i s defined as the density of observations. 17 It i s important to be very careful in i d e n t i f y i n g a resolution because i f t h i s resolution i s too f i n e one w i l l be burdened with the overhead of too much data, and i f the resolution i s too coarse some required information w i l l just not be av a i l a b l e . For most studies the s p a t i a l resolution i s obvious. Regional planners are s a t i s f i e d with a r e s o l u t i o n of a c i t y block, but neighbourhood planners may require d e t a i l to the l o t l e v e l . In a l l cases, the resolution should be keyed to the f i n e s t l e v e l of information that i s wanted. Then, once the resolution has been agreed upon, i t should be implemented. If the available data i s much too f i n e i t should be aggregated and i f i t i s too coarse, one should think twice about using l t . If data i s to be obtained by a d i r e c t survey, the size of c o l l e c t i o n unit should be of the order of the s p a t i a l r e s o l u t i o n . The s p a t i a l frequency i s another important consi-deration in conducting a survey. For data such as land use, there i s some ar b i t r a r i n e s s in exactly where the polygon boundaries are drawn, depending on those points at which the data i s observed. In such cases the number of observations made over an area of the s p a t i a l reso-l u t i o n should be large. 1.2.4 Data Encoding There are two hardware approaches to encoding maps; namely, l i n e following and scanning (see Fig. 1 .4). In the former case a cursor i s moved automatically or manually along a l i n e and points on the l i n e are recorded on tape or cards. In the l a t t e r case, the whole surface of the map i s scanned automatically and the darkness of each point i n a g r i d i s recorded. Then software i s used to locate l i n e s from the scanned data. Ray Boyle has written a good discussion of the equipment available for data input in Section II of Geo-graphical Data Handling (Tomlinson, 1972). 18 Line following (produces a l i s t of coordinates) Scanning (produoes a b i t array) Figure 1.4 Two methods of encoding a polygon. Scanning requires a much larger i n i t i a l expense for both hardware and software, but once the system i s set up, i t may encode a map f o r less than a l i n e following system. Scanning has been used by the Canadian Geographical Information System (CGIS)(Tomlinson, 196?), but most other applications have used l i n e following. CGIS has a system whereby the polygon outlines are scribed onto a sp e c i a l material which i s then automatically scanned. The system saves l i t t l e i n comparison with d i g i t i z i n g since the s c r i b i n g step i s almost as time-consuming as manual d i g i -t i z a t i o n . 19 1.2.5 Conversion of Coordinate System A description of the d i f f e r e n t coordinate systems i n use can be found in any cartography text.-* Parker (1971 b) notes that with any of these projection systems there exist (at least l o c a l l y ) l i n e a r transformations from one system to another, i . e . , there e x i s t constants a, b, c, d, e and f , such that Figure 1.5 Two d i f f e r e n t projections of the same polygon. Several d i f f e r e n t types of transformations are described in the l i t e r a t u r e (Wittick, 1972; Tomlinson, 1972, P. 737), and b u i l t i n to some geographical systems (Schmidt, 1969). 1.2.6 Display Display i s the obvious method for presentation of geographic data. Systems must have the c a p a b i l i t y to display ax+by+c dx+ey+f ^See for example Chapters 2, 9 and 10 of Robinson and Sale (1969). 20 point, l i n e and polygon data and to superimpose data sets one on top of the other. This superposition enables the user to r e l a t e data from d i f f e r e n t sources. Techniques from cartography can be applied to produce a e s t h e t i c a l l y pleasing maps which communicate well. Display hardware ranges from simple printers to very precise pen-plotters to in t e r a c t i v e CRT graphics terminals. Goodchild (1972, p. 18) has described situations i n which each type of hardware i s the most appropriate. A compre-hensive report on graphics hardware and software systems showing samples of output i s given i n Section IV of Geographical Data Handling (Tomlinson, 1972). 1.2.7 Computation There are several useful computations on polygons which a polygon-oriented system should provide. Simple algorithms exist for c a l c u l a t i n g the area of a polygon and i t s centroid (Dangermond, 1971, Appendix G). The most d i f f i c u l t and useful computation i s overlay. Overlay i s defined as a method of combining two or more maps coverages by placing the coverages one on top of another to create a composite which contains a l l the information available i n each of the coverages. Figure 1.6 shows an example of two coverages for the same region and the r e s u l t i n g overlay coverage. The polygons in the overlay coverage are found by intersecting 21 the two sets of polygons i n the o r i g i n a l coverages. Since each of the o r i g i n a l polygons was homogeneous in either a s o i l type or a zoning a t t r i b u t e , each of the polygons i n the overlay coverage w i l l be homogeneous i n both a s o i l type and a zoning a t t r i b u t e . For th i s reason we can use the overlay coverage to answer composite questions such as * "Where are a l l the regions with a rocky s o i l that are zoned for housing?" that could not be answered from either of the o r i g i n a l coverages. (The regions with the sp e c i f i e d charac-t e r i s t i c s are shaded in Fi g . 1.6). Herein l i e s the Importance of o v e r l a y — i t enables us to r e l a t e data from d i f f e r e n t coverages. S o i l Map Zoning Map Intersected map with s o i l and zoning codes f o r each polygon, and requested areas shaded i n . Figure 1.6 Two coverages and the r e s u l t i n g overlay coverage. 22 1.3 THE GRID VERSUS THE POLYGON APPROACH The previous section has described some of the implications of the polygon approach to geographical data processing. However, there i s another approach which has almost as much power and has probably been used more—the g r i d approach. Since most developers of a 2-dimensIonal geographical system w i l l eventually have to choose between a gri d and a polygon system, i t i s useful to compare these two approaches. The difference between the g r i d and polygon as areal units can be summarized by a look at which elements are f i x e d and variable in each case. In a g r i d system the areal unit i s fix e d and the at t r i b u t e i s variable, but in a polygon system the at t r i b u t e i s fix e d and the areal unit i s variable. In each case i t i s the variable element which must be deter-mined. Another way of saying this i s that in a g r i d system the data i s bent to f i t into the areal unit, but in a polygon system the areal unit i s determined by the data. To give a biased analogy, i f one had several insoluble l i q u i d s i n a beaker the polygon approach would be to use the natural separation boundaries between the media, but the g r i d approach would be to put i n a 3-dimensional mesh and deal with the l i q u i d within each cube, as shown l n Fi g . 1.7. 23 A 6 c Polygon Approach Grid Approach Figure 1.7 The gr i d and polygon approach to decomposing several l i q u i d s . The differences between g r i d and polygon systems are outlined in d e t a i l in Table I. In general, computations are simpler f o r g r i d systems. For instance, overlay only involves r e t r i e v i n g matching g r i d squares in a gr i d system, but i t e n t a i l s intersecting polygons in a polygon system. The s u i t a b i l i t y of each approach in a given s i t u a t i o n depends not only on the functions wanted but also on the nature of the data i t s e l f . For data such as census t r a c t s or zoning areas which are administratively defined as non-gr i d areas, the polygons approach i s c l e a r l y more natural. However, for data such as s o i l type which i s empirically determined, a case can be made for either approach depending on the resolution desired. If the data varies widely over an area the size of the res o l u t i o n , the g r i d approach i s probably more f i t t i n g . However, i f the data i s quite homo-geneous over large areas r e l a t i v e to the resolution desired, polygon encoding i s probably more suitable. Thus polygons are usually employed for urban studies and grids for r u r a l studies where the desired resolution i s coarser. 2k TABLE I A COMPARISON BETWEEN GRID AND POLYGON SYSTEMS Feature  1) Data Acquisition 2) Data Encoding -Method commonly used -Accuracy -Resolution 3) Editing and Updating -Attributes -Locatlonal Data k) Storage Costs -Number of Records -Size of each l o c a t l o n a l record 5) R e t r i e v a l -Sequential -Random -Neighbourhood Grid System more suitable for heterogeneous data manual or automatic scanning less fixed to the grid size easy easy more usually 1 point easy f a i r (can be calculated) f a i r Polygon System more suitable for more homogeneous data with e a s i l y determined boundaries usually l i n e following more variable within the l i m i t s of the hardware easy f a i r l y d i f f i c u l t less many points easy must keep an index poor 25 TABLE I (cont'd.) Feature Grid System Polygon System 6) Display -Device best suited for master display such as l i n e printer CRT, Plotter -Boundary Plots poor good -Contour Plots good poor 7) Computation -Area Calcu-la t i o n s t r i v i a l easy -Overlay easy d i f f i c u l t 8) Overall Costs for Software Development less more Another function which i s often important i s the access to the immediate neighbours of a grid or polygon. For example, one might be interested in the s u i t a b i l i t y of a p a r t i c u l a r location f o r a park l n comparison to surrounding locations. It i s r e l a t i v e l y easy to locate the neighbours of a g r i d square, but r e l a t i v e l y d i f f i c u l t to determine adjacencies i n a polygon system. One possible approach i s to store an adjacency graph with every polygonal map as shown i n Fi g . 1.8, but th i s is not usually carried out. 26 Figure 1.8 A set of polygons and the r e s u l t i n g adjacency graph. (Polygon P^ and Pj are adjacent If and only If nodes P^ and Pj In the graph are adjacent) One of the most important measure for comparison i s the r e l a t i v e f i l e sizes required to capture the same f i d e l i t y of data. Assume that data has been recorded and mapped to a given accuracy. It w i l l be shown that the g r i d approach requires more f i l e space to encode the boundaries to a given accuracy d. Let A be the average area of a polygon on the map in square inches. Let L be the average perimeter of a polygon on the map i n inches. Let d inches be the maximum difference allowed between the outline of a polygon and i t s encoding as g r i d or polygon. To achieve this accuracy in the grid system the g r i d size must be no bigger than d. Hence the number of grid squares to cover an average polygon must be at least A 27 In the polygon system If points are d i g i t i z e d accurately every d inches along the boundary, there i s no way that any point on the d i g i t i z e d polygon can be more than d inches off the o r i g i n a l l i n e . Hence at most £ points are required to encode an average polygon to accuracy d. Assume that each g r i d square can be defined by one point. Table II shows the calculated and actual number of points required to encode a square on i t s side to accuracy d fo r various values of d. (See Figure 1.9). Observe that the gr i d method requires far more points. TABLE II THE NUMBER OF POINTS REQUIRED TO ENCODE A SQUARE ON ITS SIDE TO AN ACCURACY d BY THE GRID AND POLYGON METHOD Accuracy d Area A = 1 Length L=4 ,01 1 • 5 NUMBER OF POINTS N Grid Method Calculated N A "37 10,000 100 4 Actual 10,200 120 4 Polygon Method Cal. L 400 40 8 Actual 4 4 28 To encode the square^ 4 points are required GRID METHOD d=.l To approximate the region to .1 by the g r i d method requires 120 squares To approximate the region to . 5 by the gri d method requires 4 squares Figure 1.9 The approximation of a square by grid and polygon methods. 29 A l l these comparisons have been somewhat speculative in that they are based on experience but not on hard-core measurements. Further work ln this area i s required. 1.4 SYSTEMS OF AUTOMATED CARTOGRAPHY Whereas most geographical systems are concerned mainly with the a b i l i t y to r e t r i e v e , analyze, and plot environmental data, automated cartography systems are concerned primarily with automating the process of map-making. One of the main problems in cartography is that maps may take several years to produce and, by then, may be out of date. The use of the computer in producing high qu a l i t y maps is j u s t i f i e d by Its', a b i l i t y to more quickly update these maps. The usual approach i s to encode the map data and store i t on tape. When changes are required l a t e r the data i s up-dated i n t e r a c t i v e l y , and then an up-to-date map is churned out by the computer. Automated cartography systems d i f f e r i n many ways from other geographical Information systems. F i r s t , they use high q u a l i t y , very expensive ( i n the $100,000 range) flatbed p l o t t e r s known as d r a f t i n g units and other spec i a l i z e d equip-ment. Secondly, since computer cartography requires a great deal of Interactive e d i t i n g , but l i t t l e computer processing, the usual c o n t r o l l e r i s a dedicated mini-computer. On the other hand, the more usual geographical systems with th e i r 30 larger volumes of data and analysis requirements run on a larger computer. Nevertheless, the problems of d i g i t i z a t i o n , storage, and graphical presentation of geographical data, are the same. Research in the f i e l d concentrates on improved hard-ware, and such problems as name placement, and new map forms. Several advanced systems have been developed in Canada. The Canadian Hydrographic Service has begun using such a system for preparing nautical charts of the coastal waters (Boyle, 1970), and the Ontario Department of Highways i s experimenting with a system for production of highway maps (MacLeod, 1972). More detailed discussions of these and other cartography systems are given i n the l i t e r a t u r e (Tomlinson, 1972, Chapter 15; Peucker, 1972). 1.5 STATE OF THE ART Tomlinson (1972) notes that i t has been very d i f f i c u l t "to acquire an overview of the f i e l d and, therefore, evaluate what has been accomplished and what remains to be done." This has occurred because although the techniques f o r gathering, s t o r i n g , analyzing and displaying data have become more and more advanced, their development has proceeded l a r g e l y i n separate d i s c i p l i n e s and diverse agencies between which there have been few channels of e f f e c t i v e communication. The r e s u l t has been repeated incidents of the "rediscovery-of-the-wheel phenomenon." 31 There have been several attempts to a l l e v i a t e this s i t u a t i o n by providing comprehensive reviews of the f i e l d . A survey of geographical systems for regional planning has been prepared (U.S. Department of Housing, 1968). UNESCO and the International Geographical Union have also sponsored two important conferences ln Ottawa. The f i r s t conference i n 1970 assembled experts from around the world to examine the state of the art and c l a s s i f y e x i s t i n g systems. The pro-ceedings, published under the name, Environment Information  Systems. (Tomlinson, 1970)» provide a good introduction to the area. About t h i r t y systems were referred to and c l a s s i -f i e d according to their main function as image systems (concerned with mapping), r e t r i e v a l systems (concerned with r e t r i e v a l , not mapping), or integrated systems (concerned with both). A more comprehensive text consisting of 1,400 pages (and weighing 7 pounds) was prepared for the second conference in 1972. Geographical Data Handling, as i n d i -cated by the number of references to i t in thi s thesis, has already established I t s e l f as a good reference text ln thi s area. According to this text, information systems developed in the past have tended to be special-purpose and emphasize single techniques rather than being general-purpose and balanced. Moreover, the course of development has been influenced too much by the technology that was available and too l i t t l e by the user requirements with the r e s u l t that the 32 l e v e l of sophistication of the hardware and software f a r exceeds the l e v e l of information use (see F i g . 1.10). As the figure also shows, the computers and other specialized hardware such as p l o t t e r s , d i g i t i z e r s , and scanners are the most advanced followed clo s e l y by system software, and then by user software. What i s needed most from the software angle are systems which are easy to use. We kept t h i s firmly i n mind i n designing the GIDS system. 1.6 EXAMPLES OF EXISTING SYSTEMS There are many geographical systems in existence which are si m i l a r to GIDS in the i r display and manipulation c a p a b i l i t i e s . This section describes a few well-known systems of both g r i d and polygon v a r i e t i e s that can be useful to planners. 1.6.1 Grid Systems Grid systems record information about each small element of a map g r i d . The size of the gr i d determines the l e v e l of d e t a i l of the data and hence the use to which that information can be put. In general, the size of the gr i d should be small r e l a t i v e to the study areas in question. SYMAP (Harvard, 1968) is a well-known grid mapping system developed at the Harvard Laboratory for Computer Graphics and Spatial Analysis. It i s quite expensive to run but provides f l e x i b l e graphic output on a l i n e p r i n t e r . Since l i n e printers are widely available and SYMAP i s we l l -33 documented, well-advertised and r e l i a b l e , t h i s system Is probably the most widely used geographical information system. SUBSYSTEMS ELEMENTS LEVEL OF DEVELOPMENT Data Acquisition Definition Collection • Data Innut and Storage Hardware System Software User Software r t — • Information Use Analysis Use *Relative order of maqnitude (expressed as proportion development) Figure 1.10 The l e v e l of development of various phases of geographical information systems. (This diagram was taken from Geographical Data  Handling. (Tomlinson, 1972)). 34 Systems with larger g r i d sizes are well-suited to natural resource studies, but not to urban studies. The NARIS (Natural Resource Inventory System) system i s one such system that i s to be used to i n t e r r e l a t e geological, hydrological, f o r e s t r y , s o i l and land use data in an area of I l l i n o i s . Some of NARIS' good features are i t s query language, self-teaching of th i s query language, and optimi-zation of objective functions over a given region (Denenberg). 1.6.2 Polygon Systems The Map/Model System and the Canadian Geographic Information System (CGIS) are two of the e a r l i e s t prototypes of polygon planning systems. Several other systems have been developed since which perform many of the same opera-ti o n s ; namely, GIMMS (Waugh) i n Edinburgh, PIOS (Dangermond, 197D in San Diego, NRIS (Boeing, 1972) in Seattle, and GIDS in Vancouver. 1.6.2.1 Map/Model System The Map/Model system (Arms, 1968; 1970) has been developed during the past seven years by the Bureau of Governmental Research and Service, University of Oregon. It i s a c o l l e c t i o n of powerful and independent modules which can be used in concert i n any appropriate manner. Some of the functions performed are polygon overlay, s t a t i s t i c a l summary, geographic r e t r i e v a l , and p l o t t i n g of maps. 35 Requests are made ln the form of PL/I programs, whereas most other systems have their own query language. Perhaps, this gives Map/Model more power at the expense of being harder to use. Each data f i l e i s s e l f - d e f i n i n g by means of a PL/I structure entered by the user. This means that the user can r e f e r to i n d i v i d u a l f i e l d s by name, but PL/I system programs must be recompiled to include these d e f i n i t i o n s . Under GIDS, on the other hand, ind i v i d u a l f i e l d s can be named by the user and then referred to by name without any recompilation of programs. Several of the Map/Model concepts such as the treatment of point, and l i n e data as s p e c i a l cases of polygon data have been adopted in GIDS. Also, th e i r technique of s t a t i s -t i c a l summarization has l a r g e l y affected the GIDS method of aggregation. Although Map/Model has been developed to a high l e v e l f o r at least three years, i t s use has been su r p r i s i n g l y small. It has been used for planning of recreational programs (Walters, 1970) and by the c i t y of Portland Planning Depart-ment. 1.6.2.2 Canadian Geographical  Information System The Canadian Geographical Information System (CGIS) was developed at great expense by the Canada Land Inventory and IBM, (Tomlinson, 1967; Environment Canada, 1972) but because of l e g a l problems i t i s not generally available. 36 It is a sophisticated system Intended for answering questions about the Canada Land Inventory data base (land use and i t s c a p a b i l i t y for agricu l t u r e , forestry, recreation, w i l d l i f e and watersheds). Each coverage of geographic data i s stored as two data sets, the image data set (IDS) con-t a i n i n g the d e t a i l e d boundaries of the polygon, and the descriptive data sets (DDS) containing the a t t r i b u t e s , area, and centroid of the polygon. This i s an elegant storage scheme because the DDS can be used to answer most Inquiries and requires much less processing than the associated IDS. Another strong feature of the CGIS i s i t s wide range of s e l e c t i o n c r i t e r i a . This enables a user to work with the areas that most naturally f i l l his needs. The scope of an inquiry can be defined by: 1) an a r b i t r a r y p o l y g o n — a l l land within i t ; 2) an a r b i t r a r y c i r c l e , e.g., within 50 miles of Ottawa; 3) a census unit; k) a topographic map sheet number; 5) an administrative unit. There i s l i t t l e graphical output. 1.6.3 Comparison of GIDS to  Other Polygon Systems As mentioned e a r l i e r , the use of geographic systems lags behind the technology. This i s largely because these systems are hard to use. 37 GIDS performs many of the same functions as Map/Model and CGIS, but i s Easier to use because i t can be run i n t e r -a c t i v e l y and has a simple command language. Once the data has been input, one can s i t down at a terminal and display or manipulate any of the data without having to recompile any programs, or grapple with JCL. Interaction enables a user to s i f t through his data base testing hypotheses and exploring for meaningful r e l a t i o n s h i p s . A few other interactive polygon systems have been developed i n the l a s t few years. In Edmonton, Deecker (1970) has implemented an Interactive graphics system with overlay to be used in s i t e location planning. At the University of B r i t i s h Columbia, Nake (1972) and Clement (1973) have developed a system for manipulating urban data in sets using set operations and interactive graphics. However, both these systems are r e s t r i c t e d to data bases small enough to be kept in core memory at a l l times during a run. GIDS, to the best knowledge of the author, i s the only interactive polygon-based geographical information system that can handle large-scale data bases. 38 CHAPTER 2 INTRODUCTION TO GIDS In Chapter 1 the general problem area of geographical Information systems has been discussed and the s p e c i f i c problem area of polygon planning systems has been described. Now in Chapter 2 the strategy adopted in designing our own polygon planning system, GIDS, w i l l be unfolded. The sections i n t h i s chapter explain whom the system is f o r and the r e s u l t i n g design c r i t e r i a (section 2.1), how GIDS handles geographic data (section 2.2), the functions GIDS performs (section 2.3), and how GIDS implements these functions on his data according to the c r i t e r i a mentioned (section 2.4). Then the command language i s introduced (section 2.5), and a sample of the system use i s presented (section 2.6). Every system i s designed with three things in mindt a p a r t i c u l a r class of users, p a r t i c u l a r types of data, and p a r t i c u l a r applications f o r thi s data. The success of a system may be measured in terms of how e a s i l y , how economi-c a l l y , and how well the users can perform these functions on th e i r data with the system. Naturally, the design of GIDS has been larg e l y i n f l u -enced by the hardware available at UBC. There are two large computers (duplex IBM 360/67) running under the Michigan 39 Terminal System (Coulthard, 1970). Jobs can be run either in batch or from one of the many Interactive terminals. Graphical output can be directed on-line to several d i f f e r e n t CRT devices or o f f - l i n e to pen-plotters or a dot p r i n t e r . For data input a manual d i g i t i z e r Is av a i l a b l e . 2 . 1 DESIGN CRITERIA Since GIDS was designed for users from a va r i e t y of d i s c i p l i n e s who were not computer s p e c i a l i s t s , the two primary design c r i t e r i a were generality and ease of use by a non-programmer. The following i s the complete l i s t of design c r i t e r i a ! 1 . The system should be easy to use. 2. The system should be problem independent. 3. The system should be usable i n t e r a c t i v e l y or i n batch. 4. The system should be e a s i l y extendible. 5. The system should emphasize graphical output. 6. The system should present a clear v i r t u a l view of the data base to both the user and the programmer. Easy to Use Since the user need not be a programmer he should not have to write programs to use GIDS, but should be able to address his requests i n an E n g l i s h - l i k e command language. Thus a command language was designed for GIDS with a l l the usual features of any reasonable command language such as 40 powerful defaults and abbreviations as described by Boettner (1970). In GIDS an e f f o r t has been made to keep the commands natural, by querying the user for any required information which does not f i t naturally into the English of the command. Another feature which f a c i l i t a t e s system use i s the a b i l i t y to name variables and then r e f e r to them i n commands by these names. Problem Independent Since the system was to serve a variety of users, i t would have to be problem independent or general purpose. GIDS was designed to handle any geographical data whose l o c a t l o n a l component was of two dimensions or l e s s . Sam Arms has explained some of the requirements to achieve t h i s generality (1970); General-purpose implies a c a p a b i l i t y to e a s i l y specify data formats and processing for a vari e t y of applications; that i s , without rewriting computer programs for each applicat i o n . Program modules must accept data and user-specifications which vary within l i m i t s , from one application to another. To achieve t h i s end i n GIDS, data i s accompanied by headers which define the formats and user names. A l l programs use these d e f i n i t i o n s instead of making b u i l t - i n assumptions on the nature of the data. Usable Interactively or In Batch For the sake of generality l t i s an advantage to provide in t e r a c t i v e or batch use of the system. A r e -searcher investigating his data base and testing hypotheses 41 may prefer the quick response that Interaction permits. However, a production-oriented user w i l l probably f i n d batch runs more suitable because they are cheaper. E a s i l y Extendible Since the system designers could never predict a l l the functions that users might desire, in the sake of generality GIDS should be e a s i l y extendible. We visua-l i z e d GIDS not as a "complete w system but rather as a framework to which new commands could be added with f a c i l i t y . (Section 3.4* outlines the steps one must follow to add a new command). Emphasize Graphical Output Maps show the "where** as well as the "how much" f o r geographical data. According to a reoent S t a t i s t i c s Canada report (1972, p. 14): Heading s t a t i s t i c a l data from a map often has compelling advantages over having the same information tabulated i n report form. Inspection of the map can instantly show where the extreme values of some function occur. A map can highlight problem areas at a glance. For t h i s reason i t was decided to emphasize graphical output and, in p a r t i c u l a r , quick and easy generation of maps. For greater f l e x i b i l i t y we adopted an approach that would f a c i l i t a t e graphical output on not just one but many of the graphics devices available to us at UBC. 42 Clear View of the Data Base In order for the system to be easy to use and easy to evolve there should be a clear and simple view of the data base f o r the user and the programmer respectively. 2.2 GIDS TREATMENT OF GEOGRAPHICAL DATA The basic approach i s the polygon approach described in Chapter 1 where data i s encoded by polygons, l i n e s , or points over which i t i s assumed to be homogeneous. 2.2.1 The Two Components of Geographical Data In Chapter 1, geographic data was characterized by having a location i d e n t i f i e r (position on the Earth) as part of the data element. Like many other systems GIDS views geo-graphic data as being made up of two components: l o c a t l o n a l  data and descriptive data (see Fig . 2.1). The l o c a t l o n a l data could be the boundary of a polygon, the path of a l i n e , the position of a point, the area, centroid or other data items related to a location on the Earth. Each l o c a t l o n a l data record describes one polygon, l i n e or point. The desc r i p t i v e data items are non-locational att r i b u t e s such as zoning codes, s o i l types, or census data describing one l o c a t l o n a l data item. 43 C R O C K \ SAND | / P E A T geographical data descriptive data l o c a t i o n a l data ROCK SAND PEAT ROCK Figure 2 . 1 The two components of geographical data. GIDS can handle any geographic data whose l o c a t i o n a l component i s of two dimensions or l e s s . As an example, i t i s currently being used by the Greater Vancouver Regional D i s t r i c t to explore a data base consisting of land use, s o l i and zoning polygons over the Metropolitan Vancouver area. It i s also being used by the Department of Forestry at UBC to study p o t e n t i a l recreation s i t e s in northern B r i t i s h Columbia based on a wide var i e t y of attributes observed at points. However, there i s no mechanism for handling 3-dimensional data. Topographical data could be handled by considering the z-value of a point as an at t r i b u t e (descrip-t i v e data) describing the (x,y) point, but the a l t i t u d e 44 could not be treated as part of the l o c a t l o n a l data element. 2.2.2 Points, Lines, and Polygons Under GIDS a l o c a t l o n a l data element may be a point, l i n e , or polygon. Our experience with geometry has taught us that a l l three are e s s e n t i a l l y d i f f e r e n t , being of a d i f f e r e n t dimension. However, as Sam Arms (1968, p. 2) has pointed out, l i n e s and points can be treated as s p e c i a l oases of a polygon. A l i n e i s a polygon of no width and a point i s a polygon of no width or length. More important, there i s r a r e l y a need to d i s t i n g u i s h between a point, l i n e and a polygon by GIDS. Thus, f o r the sake of br e v i t y , the generic term "polygon" i s often used by the author to r e f e r to a point, l i n e , or polygon. . 2.2.3 Encoding Schemes There are three p r i n c i p a l methods f o r encoding polygons. These are xy coordinate boundary encoding, chain encoding, and skeleton encoding. The d e t a i l s of each encoding scheme are not given here as they appear i n many other places (Deecker, 1972; Peucker, 1972). Gordon Deecker i s responsible fo r the major work in th i s area. He compared the s u i t a b i l i t y of each scheme for performing various functions and found that no one method was the most suitable over all» An important conclusion i s that the choice of method i s , or should be, very much dependent on which functions of data manipulation are required in the application considered. 45 Boundary encoding was chosen for two reasonst It was the simplest to Implement (the d i g i t i z e r already produced x-y coordinates), and the simplest to p l o t ( p l o t t i n g required x-y coordinates). The boundary encoded representation of a point, l i n e or a polygon Is a l i s t of xy coordinate pa i r s . The fa c t that a polygon Is d o s e d Is Indicated by the f i r s t point equalling the l a s t point. Given an xy coordinate l i s t I t Is easy to Identify the element as a point, l i n e or polygon. If the l i s t has only one point the element Is a point. If the f i r s t point equals the l a s t point the element Is a polygon. Otherwise I t i s a l i n e (see Pig. 2.2). y Point P POLYGON A (0,0) x Locational data element xy boundary encoding P (1,2) A L (3,4) (5,7) (6,4) (8,2) (13,2) (13,7) (18,7) (18,2) (13,2) Figure 2.2 The boundary encoded representation of a point, l i n e and polygon. 46 2.3 FUNCTIONS OF THE SYSTEM GIDS has the c a p a b i l i t y to perform the following functions t 1. Input of point, l i n e , or polygon data and the associated a t t r i b u t e s using f l e x i b l e formatting. 2. Conversion of d i g i t i z e r coordinates to a user-spec i f i e d g r i d . 3. Calculation of area and centroid of polygons, and length of l i n e s . 4 . P l o t t i n g of d i g i t i z e d map and user-specified attributes to check for errors. 5. Creation of f i l e s which are s e l f - d e f i n i n g - i n format and a t t r i b u t e names. 6 . Numeric selection of the portion of a f i l e whose attributes s a t i s f y an a r b i t r a r y l o g i c a l expression. 7. Selection from a l o c a t l o n a l f i l e on the basis of the presence or absence of associated de-s c r i p t i v e records. 8. Drawing a selected portion of a f i l e on a variety of graphic devices with a variety of symbolism. F a c i l i t i e s are included for superimposing maps, shading polygons, drawing a t t r i b u t e values at the polygon oentroids, and symbolizing with t r i a n g l e s and other geometric symbols. 9. Intersecting selected portions of two polygonal f i l e s and writing the polygons of interse c t i o n into a t h i r d f i l e . 10. Aggregating the intersected polygon f i l e to produce new attributes associated with the o r i g i n a l polygons that were intersected. 11. S t a t i s t i c a l summarization of a f i l e according to f l e x i b l e user s p e c i f i c a t i o n s . 12. Output of a selected portion of a f i l e 47 2.4 INTRODUCTION TO THE IMPLEMENTATION 2.4.1 Basic Method of Operation Any of the functions described ln the previous section can be triggered by entering a command In the GIDS command language. Each command Is Interpreted and executed before the next command Is read. Data i s Input to GIDS where I t Is stored ln sequential f l i e s . A flowchart showing the basic steps followed during a GIDS run appears ln Figure 2.3. The supervisor program reads a command and checks that Its f i r s t word Is a v a l i d oommand name. If so, a command routine Is c a l l e d to complete the execution of the command. This routine determines the f i l e s to be read from the command s t r i n g , then reads these f l i e s sequentially with records from the Input f l i e s being selected for processing or rejected on the basis of c r i t e r i a s p e c i f i e d by the u s e r D l n the command. Upon reading the end of the f i l e the process Is terminated and control Is returned to the supervisor. At t h i s point, the process begins again with the supervisor asking the user to enter his next command, and waiting f o r I t . The run Is terminated by the user entering a STOP command. 2.4.2 Sequential F i l e Processing In the ASAP lntroductor report Conway et a l (197D characterized sequential f i l e processing systems as having! 48 Start V READ USER COMMAND v. S INVALID "^\COMMAND/ CALL THE APPROPRIATE COMMAND ROUTINE INITIALIZE (1) SCAN COMMAND! (2) OPEN FILES READ THE NEXT RECORD Yes PROCESS THE RECORD RELEASE THE RECORD TERMINATE THE COMMAND Figure 2.3 Structure of a GIDS run 4f> 1) a single master f i l e , 2) records organized s e q u e n t i a l l y — t h a t i s , i n increasing order of a Mkey M value, 3) a s i m i l a r processing task f o r each record. ASAP Is one example of such a system. Since GIDS s a t i s f i e s these l a s t two c h a r a c t e r i s t i c s , It Is a sequential f i l e processor of sorts. However, In a GIDS run, each command may process more than one sequential f i l e , and d i f f e r e n t commands ln the same run may process d i f f e r e n t f l i e s . Never-theless, viewing GIDS as a sequential f i l e prooessor should lend c l a r i t y to Its operation for both a user and a GIDS programmer. 2.4.3 Program Structure of GIDS The components of the GIDS system can best be I l l u s -trated by a Mock diagram, (see F i g . 2.4). The large box delineates the boundary of the system. Interfacing the system with the external world are the Inputs, the data base and the outputs. The Inputs are the commands and the maps from the user. The geographic data base, stored on disk or tape, Is the f i n a l edited version of thi s data that has passed through the input subsystem of GIDS. La s t l y , the outputs are either graphic or tabular re s u l t s produced by GIDS command routines. Within the system boundary the four most Important modules are the supervisor, the command routines, the selector routines and the I/O routines. The supervisor 50 i n i t i a l i z e s the system, reads In user commands, and then passes control to the appropriate command routines. A command routine accepts the user command s t r i n g , Interprets I t , and executes I t . There Is one command routine f o r eaoh of the GIDS commands. The selection routines determine from the command s t r i n g the subset of a given f i l e to be selected and f i l t e r out those records which are outside that scope. The I/O routines read or write GIDS sequential f l i e s , one record at a time. 2.4.4 Memory Structure of  a GIDS run GIDS Is a large system consisting of many programs coded by several people. While GIDS was s t i l l In an early stage a l l these programs used to be loaded Into core memory at the same time. This required about 200,000 bytes on an IBM/36O and resulted ln the v i r t u a l memory cost being about half the t o t a l cost of a run at a terminal. The user was being taxed heavily f o r those Important pauses to ponder some r e s u l t or scratch his head. The amount of v i r t u a l memory required was cut ln half by Implementing dynamic loading of the command routines and dynamlo storage a l l o c a t i o n of data tables. The supervisor, selector and 1/0 routines were kept resident ln core since they are used during most commands. When a command was entered the supervisor dynamically loaded the appropriate command routine from disk, executed It and then unloaded I t . TABULAR INPUT MAPS 51 USER » -COMMAND LANGUAGE SUPERVISOR INPUT COMMANDS MANIPULATION COMMANDS SELECTOR ROUTINES 1 — ~ * t/O ROUTINES ft: GEOGRAPHIC DATA BASE GRAPHICS COMMANDS COMMAND ROUTINES TABULAR OUTPUT -% X GRAPHIC OUTPUT Figure 2.4 Block diagram of GIDS 52 Thus, each command routine occupies core storage only while i t i s executing. Figure 2.5 shows a map of core memory used by GIDS during a t y p i c a l run. A i s the region permanently resident. B i s the region where a command routine resides while being executed. This space i s released i n between commands. C i s the region where l o c a l f i l e tables, headers, etc., are stored. This space i s released at the end of each command. D i s the region where the geographic data i s stored while i t i s being processed. Usually t h i s consists of one record for each f i l e being processed. *• 2.4.5 Implementation Language Several languages were considered for programming the system; namely, PL/1, FORTRAN, and ASSEMBLER. PL/1 i s the most powerful and the most expensive of the three. ASSEMBLER produces the most e f f i c i e n t object programs, but i s more d i f f i c u l t to program than either PL/1 or FORTRAN. FORTRAN programs are easier to code and less expensive than PL/1 programs but are less powerful i n some areas. Since PL/1 was so expensive, l t was decided-to use a combination of FORTRAN and ASSEMBLER. The I/O and selector routines which must be executed frequently were written in ASSEMBLER, as were the character handling and linked l i s t routines. Most of the other procedures were written i n FORTRAN. •'•The most notable exception i s the INTERSECT command as w i l l be explained in section 4 . 3 . 53 A B C D REGION RESIDENT REGION PROGRAM REGION FILE TABLES REGION DATA REGION CONTENTS GIDS supervisor I/O routines selector rou-tines commonly used u t i l i t y rou-tines global tables the command routine currently executing f i l e tables headers one polygon from each active f i l e WHEN SPACE IS FREED at the end of the run at the end of the command at the end of the command when pro-cessing of the polygon Is complete REGION SIZE IN PAGES 28 0-25 0-3 0-2 resident f o r decreasing periods of time — Figure 2.5 A map of core memory during a GIDS run 54 2.5 INTRODUCTION TO THE COMMAND LANGUAGE The general syntax of a GIDS command Is a commandname, followed by one or more filenames (to perform the operation on), followed by parameters (to control the options). Most parameters are optional and have pre-asslgned defaults. Some commands do not contain a l l the information they require f o r the appropriate processing. After entering these commands the user Is queried for the required Information and only a f t e r he has supplied It i s the command executed. The command syntax and semantics are outlined in Appendix A and, In more d e t a i l , in the GIDS Command Manual (Yen, 1972). Meanwhile, a few simple command sessions w i l l be given ln the next section. 2.6 SAMPLE OF SYSTEM USE This section presents a,real example of what GIDS has done fo r planners showing .the commands required to perform these operations. More detailed examples are given l n Appendix C. Planners at the Greater Vancouver Regional D i s t r i c t have been concerned with zoning and land use and re l a t i o n s between the two In the Vancouver area. Some p a r t i -cular requests have been* 1 . To obtain the land use breakdown by area within given regions; 2. To p l o t maps of regions with sp e c i f i e d zoning or land use c h a r a c t e r i s t i c s ; 55 3. To locate regions of j o i n t zoning and land use ch a r a c t e r i s t i c s . Before GIDS can service these requests the required geographic data must pass through the Input system. The stages Involved are map and menu preparation, d i g i t i z a t i o n , e d i t i n g , lnputlng, p l o t t i n g , conversion to user-specified coordinate system, ca l c u l a t i o n of areas, and output to f i n a l f l i e s . The land use maps were prepared by combining gross l e v e l a e r i a l photographs with detailed l e v e l land use map data on a series of base maps. The process Is described more f u l l y in the HPS Land C l a s s i f i c a t i o n Subgroup Report (George, 1972). Using a base map the polygons were traced onto a transparency with t h e i r land use code. Then these polygons were d i g i t i z e d , edited, Input, and plotted (see F i g . 2.6). We now show the commands to Input t h i s d i g i t i z e d land use map to GIDS. Assume the d i g i t i z e d polygons have been stored l n the MTS f i l e LANDUSE and the menu Is in the f i l e MARVsMENU before we begin the f i r s t session. (The commands are c a p i t a l i z e d below). F i r s t session* #RUN GIDSJ1.0 loads the GIDS system and begins Its execution INPUT LANDUSE TO LANDUSE.I MENU=MARVtMENU reads the d i g i t i z e d polygons from the f i l e LANDUSE, does some computation, writes the data out in intermediate f i l e LANDUSE.I 56 PLOT LANDUSE.I NOAXIS produces a hard copy plot with the codes. (See Appendix D f o r a legend of the codes). STOP terminates the run Then the output plo t i s compared with the o r i g i n a l map, and i f they concur to the desired accuracy the data i s i n i t i a l i z e d to i t s f i n a l form as shown i n the second session below. Otherwise the errors are edited i n LANDUSE and the f i r s t session i s repeated. Second session: #BUN GIDS:1.0 CREATE (LANDUSE.R,LANDUSE.G) creates the f i l e s and writes header information in them INITIALIZE LANDUSE.I to (LANDUSE.R,LANDUSE.G) reads the data from LANDUSE.I converts i t to a more compaot format and writes i t out into the f i n a l f i l e s LANDUSE.R and LANDUSE.G Assume the zoning map has passed through the same input process and has been stored i n f i l e s ZONING.R and ZONING.G. We now show the commands that generate the required Information. Third session: LIST (LANDUSE.R,LANDUSE.G) prints the contents of the f i l e s including the areas and land use of each polygon. From t h i s the t o t a l area of each land use type can be determined (request #1). 57 DRAW (LANDUS E. R,LANDUS E.G) SCOPE=(LANDUSE=40) draws a map of those regions with a spe c i f i e d land use (request #2) CREATE (INT.R,INT.G) create f l i e s that w i l l contain the overlay coverage INTERSECT (LANDUSE.R,LANDUSE.G) WITH (ZONING.R,ZONING.G) AND STORE IN (INT.R,INT.G) Intersect the land use and zoning polygons and stores the r e s u l t s In INT.R and INT.G DRAW (INT.R,INT.G) SCOPE=(LANDUSE=40 ZONING < 10) locates regions of j o i n t landuse and zoning c h a r a c t e r i s t i c s (request #3). STOP terminates the run This completes our Introduction to GIDS. We now begin a more detailed study of the system **#«*«* 58 CHAPTER 3 FOUNDATIONS OF THE SYSTEM From a systems point of view l t i s useful to d i s -tinguish between foundation elements and non-foundation elements of GIDS. The foundation elements are those elements upon which the system Is b u i l t and which continue to be important in future extensions to the system. In GIDS the f i l e structures and the methods for accessing these f i l e s constitute the two primary foundation elements. Chapter 3 describes these foundation elements in some d e t a i l , and Chapter 4 goes on to speak of the other com-ponents of the system. There are four parts to t h i s chapter, describing in turn the f i l e structures, s e l e c t i o n , the input/output structures, and f i n a l l y the steps for programming a new command using these foundation elements. 3 . 1 FINAL FILE STRUCTURES 3 . 1 . 1 Introduction . The f i n a l f i l e structures are the core of GIDS. They are the basic units upon which a l l the graphics and analysis commands operate. GIDS employs several d i f f e r e n t f i n a l f i l e structures, but a l l are sequential and consist of the same two basic ingredients: a header followed by a l i s t of data records. 59 (See Pig. 3.0 for an i l l u s t r a t i o n of t h i s structure). The header records contain information global to the whole f i l e , whereas each data record contains information about one polygon only. The f i r s t f i e l d i n every record i d e n t i f i e s the record as header or data. The next secions w i l l discuss in d e t a i l the data records and then the header records. header records data reoords a GIDS f i n a l f i l e J Figure 3.0 The two types of records i n a GIDS f i l e , 3.1.2 Logical Data Structure  for One Polygon From a l o g i c a l point of view there are three blocks of Information f o r each polygon: the descriptive data, the boundary coordinates, and the dimensioning (see F i g . 3»D« The d e s c r i p t i v e data and boundary coordinates have been described i n Chapter 2. 60 boundary coordinates Figure 3.1 The l o g i c a l data structure of a polygon. The dimensioning i s defined as several items such as area, minimal bounding rectangle, and centroid which characterize the dimensions and position of a l o c a t l o n a l data element. Although these dimensioning items can be calculated from the boundary coordinates, they are used s u f f i c i e n t l y often to merit storing them e x p l i c i t l y with the polygon. D e f i n i t i o n I The minimal bounding rectangle or envelope of a polygon i s defined as the smallest rectangle that encloses the polygon with sides p a r a l l e l to the x and y axes (see F i g . 3»2). 61 Figure 3.2 The minimal bounding rectangle of a l i n e and polygon. The minimal bounding rectangle i s useful because i t gives the maximum extents of the polygon and may serve as an approximation to the polygon, and yet can be spe c i f i e d com-p l e t e l y by four variables. Slnoe points and l i n e s are treated as special cases of polygons and are to have the same data structure, corresponding dimensioning items must be established f o r points and l i n e s . Table III shows thi s correspondence. Take note that the item used to measure size i s d i f f e r e n t for polygons of d i f f e r e n t dimensions. Area i s used f o r the size of a 2-dimensional polygon, length i s used f o r the size of a 1-dimensional poly-gon, and 0 i s used for the size of a O-dlmensional polygon. Polygons do have perimeters as well as area, but i n most applications, one i s more concerned with the area than with the perimeter. 62 TABLE I I I THE DIMENSIONING ITEMS AND THEIR USES FOR POINTS, LINES AND POLYGONS USE POINT LINE POLYGON (1) Location of centre point for p l o t t i n g labels on or near the point near the midpoint of the l i n e within the polygon (2) Size used i n overlay and for reports 0 the length the area (3) Envelope used to see i f 2 polygons intersect Several additional l o c a t l o n a l items such as the number of coordinates i n the polygon were included in the dimensioning bringing the number of dimensioning items to twelve. (See Appendix B for a complete l i s t ) . Although not a l l of the dimensioning items are always used, i t was decided to always store a l l 12 items with each polygon. This s a c r i f i c e d some f l e x i b i l i t y but s i m p l i f i e d the data structures. We o r i g i n a l l y planned to use a more compact data structure f o r point data since most of the dimensioning information i s already provided by the coordinates of the point i t s e l f . However, as we expected to deal r a r e l y with point data and wished to treat a point as a s p e c i a l case of a polygon, we eventually decided on the less oompact data struc-ture that we were using for polygonal data. 63 Within one GIDS f i l e every descriptive data element must contain the same a t t r i b u t e s , but there may be more than one descriptive data element for one polygon. This occurs when there are several observations of the same attributes f o r the same polygon. For example, i f the poly-gons were census t r a c t s , and these had not changed during the l a s t three census, then we could represent census data as three descriptive records (population data) f o r each l o c a t l o n a l record (census t r a c t ) , as shown belowi Census Tract Year Total Population 1961 8,501 1966 9,203 1971 10,740 1961 5,^86 1966 8,921 1971 9,562 3.1.3 Physical Data Structure  of One Polygon For various reasons i t was decided to store the descriptive data and boundary coordinates in two separate f i l e s — a descriptive f i l e and a l o c a t l o n a l f i l e . The f i r s t question that arose was where to store the dimensioning— with the descriptive data or with the coordinates? In one sense, the area and other dimensioning items provide descriptive information about the polygon and thus belong with the other descriptive data. Only the boundary co-ordinates are l o c a t l o n a l data i n the purest sense. On the 64 other hand, there are three good reasons for storing the dimensioning in the same f i l e as the boundary coordinates. F i r s t , since the dimensioning i s either d i g i t i z e d together with the coordinates or calculated from the coordinates, i t is available at the time the coordinates are input. However, the dimensioning i s not necessarily available at the time the attributes are Input. Secondly, It makes ed i t i n g easier. If a polygon boundary Is edited, some of the dimensioning Items, such as the area, w i l l probably have to be changed also. If the dimensioning Is ln the l o c a t i o n a l f i l e , a l l the changes can be made within that f i l e and the descriptive f i l e can be l e f t untouched. L a s t l y , If there are several descrip-t i v e f l i e s f or one l o c a t i o n a l f i l e , I t Is more compact to store the dimensioning ln the l o c a t i o n a l f i l e . This way the dimensioning can be stored once, not many times. Our con-clusion was to place the dimensioning with the boundary coordinates. Now we have the physical data structure f o r one poly-gon. There is a descriptive record and a l o c a t i o n a l record. The l o c a t i o n a l record consists of the dimensioning followed by boundary coordinates (see F i g . 3»3)« descriptive record 65 Land use code=40 Polygon # =5 The Polygon l o c a t l o n a l 1 1— i i i — i — record 5 ; c x , c y i ,r • a b c d e a dimensioning boundary coordinates Figure 3.3 Physical data structure f o r one polygon. The correspondence between a l o c a t l o n a l record and the associated descriptive records i s established through t h e i r equal polygon numbers. The polygon number i s a sequence number which uniquely i d e n t i f i e s a point, l i n e or polygon within i t s f i l e . It i s the f i r s t f i e l d in both the l o c a t l o n a l and de-s c r i p t i v e records. The physical data structure described i n t h i s section i s the view of the data base that i s presented to a l l GIDS processing routines by the I/O routines. The actual format of the data on the f i l e w i l l be described in Section 3.1.4 S p l i t and Merged F i l e s The descriptive and l o c a t l o n a l records described i n the previous section may be organized physically into two d i f f e r e n t f i l e structures. They may be written into two d i s t i n c t f i l e s (a descriptive f i l e and a l o c a t l o n a l f i l e respectively) or they may be written into one f i l e (a merged  f i l e ) . Thus, there are three d i f f e r e n t f i n a l f i l e s t r u c t u r e s — the descriptive f i l e , the l o c a t l o n a l f i l e and the merged f i l e . 1 ^Throughout this document a l o c a t l o n a l f i l e i s also c a l l e d a "geographic f i l e " and a descriptive f i l e i s also c a l l e d a "row f i l e . " 66 The combination of a descriptive f i l e , afaid I t s associated l o c a t i o n a l f i l e Is c a l l e d s p l i t f i l e s . Hence, the same map Information can be stored p h y s i c a l l y In two waysi l n a merged f i l e or ln s p l i t f i l e s . There are situations when ei t h e r the s p l i t f i l e s or merged f i l e s y i e l d advantages over the other (see Section 3.1.5). However, the Input/ output routines make the differences between s p l i t f i l e s and merged f i l e s completely transparent to a l l processing programs. The elegance of t h i s approach Is that any routine which w i l l process a merged f i l e w i l l , without any changes whatsoever, process s p l i t f i l e s and vice versa. Hence, there Is a very small price to pay f o r the added f l e x i b i l i t y . Figure 3 . 4 shows a land use map and the r e s u l t i n g s p l i t f i l e s and merged f i l e . Observe that the descriptive f i l e contains only descriptive, records and the l o c a t i o n a l f i l e contains only l o c a t i o n a l records, whereas the merged f i l e contains a l l the d e s c r i p t i v e records f o r a polygon followed by i t s l o c a t i o n a l record. 3.1.5 The Relative Advantages of S p l i t and Merged F i l e s Whether to use s p l i t f i l e s or merged f l i e s depends on the s i t u a t i o n . Merged f l i e s are usually superior when both the polygons and attributes are to be processed because there Is less overhead l n processing one f i l e than two and less trouble In specifying one f i l e name than two. S p i l t 6 7 Polygon # Land use 1 10 2 3 3 5 4 10 Descriptive F i l e Land use map with land use codes at centrolds Polygon # Area Coordinates 1 10.0 a,b,c,e,f,a 2 14.3 g,f,e,d,l,h,g 3 28.2 d,e,c,m,l,k,n,d 4 5.1 l , d , n , J , l Locational F i l e S p l i t F i l e s descriptive/ data records Polygon # 1 10 1 10.0 a,b,c,e,f,a 2 3 2 14.3 g,f,e,d,l,h,J 3 5 3 28.2 d,e,o,m,l,k,n,d 10 4 5.1 l , d , n , J , l loca-t i o n a l data records The Corresponding Merged F i l e Figure 3.4 A land use map, the corresponding s p l i t f i l e s and merged f i l e . (Uote th i s diagram shows only two of the twelve dimensioning f i e l d s ) 6 8 f i l e s are more economical i f only one component of the geographic data i s to be manipulated. There are three other circumstances in which s p l i t f i l e s are advantageous to merged f i l e s . The f i r s t Is when the attributes are prepared and input completely independently from the polygons. For example, the census tracts for the Vancouver area could be d i g i t i z e d input, and written into a l o c a t l o n a l f i l e L, i n January, 1973. A s soon as the census demographic data was avail a b l e (say in A p r i l , 1973), i t could be input and stored in a row f i l e associated with L. On the other hand, a merged f i l e containing the same demographic data could not have been produced u n t i l both components of the data were available i n A p r i l . A second s i t u a t i o n suited to the use of s p l i t f i l e s i s when there i s more than one descriptive data set associated with a p a r t i c u l a r l o c a t i o n a l data set. This data can be stored i n two wayst as several descriptive f i l e s and one l o c a t i o n a l f i l e , or as several merged f i l e s with the loca-t i o n a l data set repeated in each f i l e . The use of s p l i t f i l e s saves storage and also makes ed i t i n g simpler as there i s only one copy of the polygons to e d i t . A t h i r d advantage of s p l i t f i l e s i s that they can be more e a s i l y processed by other systems. In p a r t i c u l a r , the row with i t s fi x e d length records of fixed format could be processed under a standard f i l e management system i f one 69 TABLE IV A COMPARISON BETWEEN SPLIT FILES AND MERGED FILES IN VARIOUS PROCESSING SITUATIONS S p l i t F i l e s Merged F i l e s 1. Only one of the two components of geographic data Is processed at a time. very good good 2. Both Components of geographio data are processed together. good (more overhead) very good 3. Descriptive and l o c a t i o n a l data sets input at the same time. good good 4. Descriptive and l o c a t i o n a l data sets available for input at d i f f e r e n t times. good f a i r 5. More than one descriptive data set for one l o c a t i o n a l data set. good f a i r 6. Descriptive data to be processed external to GIDS. f a i r poor 70 skipped over the header records at the beginning of the f i l e . It would be much harder f o r an external program to handle a merged f i l e because of Its variable length blocked polygon records. The comparison between s p i l t f l i e s and merged f i l e s Is summarized In Table IV. 3.1.6 Detailed Record Formats* A l l the geographic data i s stored In GIDS f l i e s as r e a l numbers. Integers are handled by converting them to t h e i r r e a l equivalents. Rather than storing these r e a l numbers In EBCDIC character form, they are stored ln the IBM/36O as REAL #4 numbers l n Internal format. Internal format leads to savings on two accounts 1 storage, and pro-cessing time. F i r s t , Internal format Is more compact than character format for representing these r e a l numbers. Since a t y p i c a l map i s twenty Inches square and d i g i t i z e r s are accurate to a few thousandths of an lnoh, a d i g i t i z e d coordinate has up to f i v e s i g n i f i c a n t d i g i t s . A t y p i c a l coordinate Is +18.352. To store this in the IBM/360 would require perhaps 7 bytes In character format, but only 4 bytes ln Internal format. This saving quickly m u l t i p l i e s . If a l o c a t i o n a l f i l e contains 100 polygons with an average of 10 sides then each record consists of 32 r e a l numbers, Including the dimensioning. A simple c a l c u l a t i o n shows that the f i l e would require 12,800 bytes i f stored in i n t e r n a l format, but only 22,400 bytes If stored ln character format. In experiments with a map of 71 377 land use polygons, we found that the d i g i t i z e r f i l e , whioh i s i n character format, occupied 24 pages on disk, whereas the l o c a t i o n a l and descriptive f i l e s , which are both in Internal format, occupied only 13 and 2 pages respec-t i v e l y . In t h i s case, i n t e r n a l format led to a savings of 9 pages or almost 40 per cent. Seoondly, input/output requires less than a quarter as much CPU time for i n t e r n a l l y formatted data than f o r character data because there i s no conversion of format required. Since no a r b i t r a r y upper l i m i t has been Imposed on the number of points in a polygon, a l l storage has to be dynamically allocated and the l o c a t i o n a l records have to be 3 blocked (see F i g . 3.8). This block length and the descrip-t i v e record length are both stored in the header and become known when the f i l e i s opened and the headers are read. Hence the size of buffers needed f o r both the descriptive and l o c a t l o n a l records are known before any data records are read. 3.1.7 Headers* The f i r s t few records of a l l GIDS f i l e s , be they d e s c r i p t i v e , l o c a t i o n a l , or merged, contain the f i l e header. One page equals 4,096 bytes of storage. 3currently the block length f o r the l o c a t i o n a l records i s always 252 bytes. 72 This header contains a variety of useful information about the geographic data in the f i l e such as the type of f i l e , f i l e format, and the fieldnames. By means of t h e i r headers, a l l GIDS f l i e s are s e l f - d e f l n l n g ; t h i s Is an Important factor ln making GIDS problem independent. Because of the headers the binding of many variables such as fieldnames can be delayed u n t i l the time a f i l e Is created. To Increase the e x t e n d l b l l l t y of the system, extra space has been dellb-erately l e f t l n the header so that new Information can be Included If the need arises in the future. The header i s read Into v i r t u a l memory when a f i l e Is f i r s t opened and kept there u n t i l processing on the f i l e Is complete (at the end of the command). Meanwhile, any programs that require Information about the f i l e can look at Its header. For example, when a user gives a command to draw a map with the zoning codes (DRAW f i l e CODED BY ZONING) one routine looks for the position of the f i e l d ZONING ln the given f i l e . Each header Is made up of two or more header records. There are four d i f f e r e n t types of header records, a l l with t h e i r own standard formatst the general header, the descriptive header, the f i e l d header, and the lo c a t i o n a l header. The con-tents of each of these are summarized below. 1) General Header This Is always the f i r s t header record. It contains information such as f i l e type, creation date, year of i n v a l i -dation that i s relevant for a l l types of GIDS f i l e s . Note 73 that the system can automatically check when opening a f i l e i f the data i s no longer v a l i d . 2) Descriptive Header This appears only for descriptive f i l e s and merged f i l e s . It gives the length of the row record. 3) F i e l d Header This contains a l l the information such as fieldname, location in the record, and range of values that refers to one f i e l d . There i s one f i e l d header for each f i e l d i n the des c r i p t i v e f i l e . 4) Locational Header This only appears in the headers of l o c a t i o n a l and merged f i l e s . I t contains a l l the information about the l o c a t i o n a l content of the f i l e , such as the map scale, range of coordinates f o r the f i l e , tolerances in ed i t i n g , and the dimension of the polygon. Now we show what the headers look l i k e for each of the three types of GIDS f i l e s , (a) The header f o r a descriptive f i l e general header descriptive header one for each f i e l d i n the descriptive record f i e l d header f i e l d header f i e l d header f i e l d header 7k Since there i s no l o c a t i o n a l header, no l o c a t i o n a l information whatsoever i s required to create descriptive f i l e s . (b) The header for a l o c a t i o n a l f i l e general header lo c a t l o n a l header (c) The header f o r a merged f i l e one f o r each f i e l d in the descriptive record general header descriptive header f i e l d header f i e l d header f i e l d header y f i e l d header l o c a t i o n a l header 3»1«8 How Headers are Constructed  at Execution Time* Headers are i n i t i a l l y constructed and written onto the f i l e when the f i l e i s created (with the CREATE command). Instead of querying the user for a l l the header information, the policy adopted has been to extract as much information as possible out of the data i t s e l f , and only to ask him for information which cannot be obtained i n this way. For example, since the map scale i s available from input but the fieldnames are not, the user w i l l be asked to name the 7 5 f i e l d s but not to enter the scale.By "CREATE A LIKE B" a user can create a header f o r f i l e A i d e n t i c a l to the ex i s t i n g header for B. La s t l y , when a command i s executed which changes a f i l e In some way so that Its previous header Is no longer v a l i d , that same command w i l l correct the header so that the f i l e header provides an up-to-date accurate description of the data In the f i l e . 3.2 SELECTION AND THE COMMAND LANGUAGE STRUCTURE 3.2.1 Introduction Selection enables a user to extract a subset of a GIDS f i l e f o r processing. The command language enables a user to communicate his requests e a s i l y to the programs. Both selection and the command language are foundation elements of the system. In Section 3»2 the author describes the concept and Implementation of se l e c t i o n , the syntax of filenames and selectors, and f i n a l l y the GIDS approach to command pro-cessing. 3»2.2 Selection vs. R e t r i e v a l Often one wishes to extract a p a r t i c u l a r subset from a f i l e . Selection and r e t r i e v a l are two d i f f e r e n t methods for achieving this goal. With selection , every record Is sequentially and the desired records are selected as they are read. However, with r e t r i e v a l , the records ln question 76 can be read d i r e c t l y (I.e., retrieved) from the f i l e . R e t r i e v a l Is the modus operandi for a random access f i l e environment, whereas selection Is the way to operate In a sequential f i l e environment. 3.2.3 Three Types of Selection There are three completely d i f f e r e n t types of selec-t i o n that have relevance for GIDS (see F i g . 3.5). These aret (1) numerlo selection; (2) geographic s e l e c t i o n ; (3) selection by the presence or absence of a row record. Numberlc selection Involves selection of records based on the values of t h e i r numeric a t t r i b u t e s . An example of numerlo selection i s selection of a l l polygons from a land use f i l e with values for the land use code of less than 4. Numeric selection has been implemented and lends great power to GIDS. It i s described.In the next sections. Geographic selection involves selection of records based on the values of t h e i r geographic coordinates. For example, one might want to s e l e c t a l l the land use polygons from a given f i l e which i n t e r s e c t a given municipality polygon. This type of s e l e c t i o n has not yet been imple-mented, but Section 6.4 discusses Implementing l t In the future. The t h i r d type of s e l e c t i o n occurs as a consequence of the matching of a l o c a t l o n a l record and an associated 77 row record In reading s p l i t f i l e s . Polygons are selected from a l o c a t i o n a l f i l e i f and only i f there is a descriptive record with matching polygon number In the associated row f i l e . Thus, the subset selected Is determined by the presence or absence of row records. Figure 3.5 shows a sample case. Here the l a s t polygons w i l l be skipped; there are no matching descriptive records. Selection by the presence or absence of row records i s implemented within the read routine, and hence w i l l be described further l n Section 3.3. 3.2.4 GIDS Filenames and  Quali f i e d F i l e s Two elements ln the GIDS command language are f i l e -names and q u a l i f i e d f l i e s . Under the MTS operating system, a l l f i l e s have a name which must be supplied before the f i l e can be read or written. MTS filenames consist of from one through twelve alphanumeric characters (plust the period and underscore). A l l row, l o c a t i o n a l and merged f i l e s can be referred to simply by t h e i r MTS filenames, but i t Is not obvious how to name s p i l t f l i e s . The syntax used Is l e f t parenthesis, row f i l e name, comma, l o c a t i o n a l f i l e name, r i g h t parenthesis. For example, i f BOW and LOC are the names of an associated row and l o c a t i o n a l f i l e , then (ROW,LOC) i s the corresponding s p i l t f i l e . One can view a s p i l t f i l e as a single f i l e containing both descriptive and l o c a t i o n a l data Identical to a merged f i l e as far as a user Is con-cerned, except that It has an unusual name. 78 READ WINDOW (contains the next selected record) Numerlo sel e c t i o n FILTER A Geographic Selection Area Not selected because there i s no descriptive record F i l t e r e d out by numeric se l e c t i o n Selected F i l t e r e d out by geographic se l e c t i o n Selected i l^tV^ 7 i \ 1 v # 1 i descriptive f i l e l o c a t l o n a l f i l e Figure 3.5 Three types of selec t i o n . (Numeric selection and selection by the presence or absence of row records are implemented i n GIDS). 79 Under MTS, a l l filenames can be q u a l i f i e d by modifiers to specify carriage c o n t r o l , conversion, etc. The beauty of t h i s design i s that the modifier i s treated as part of the filename, I.e., the modifier Is processed by the MTS Input/ output routines and Is transparent to a l l other routines. GIDS has carried t h i s concept one step further. GIDS f l i e s can be q u a l i f i e d by a selector ln addition to the regular MTS modifiers and.hence are c a l l e d " q u a l i f i e d f i l e s . " This selector s p e c i f i e s which records In the f i l e are to be selected f o r processing and which records are to be Ignored. It Is treated as part of the GIDS filename Just as MTS modi-f i e r s are treated as part of the MTS filename. Qu a l i f i e d f i l e s are Important because they serve as the mechanism for r e f e r r i n g to selected parts of a f i l e ln the GIDS command language (see Appendix A). 3.2.5 Fieldnames Under GIDS a user can define fieldnames for a f i l e , and then he can ref e r to the Individual f i e l d s by name ln a command. Fieldnames are used ln the selector, the graphics commands, and the aggregation commands. Fieldnames are defined In a d i f f e r e n t manner f o r l o c a t i o n a l and row f l i e s . Every l o c a t i o n a l f i l e has the same dimensioning information about each of Its polygons. Thus, the same fieldnames w i l l work for a l l l o c a t i o n a l f l i e s . These names have been defined by the system de-signers once and for a l l and appear l n Appendix B. On the 80 other hand, since row f i l e s do not contain a standard repertoire of information, there can be no standard naming. The user defines the fieldnames for a row f i l e when he creates I t with the CREATE command. A fieldname may contain alphanumeric characters, colons ":", and underscores "_", but may not be one of the keywords of the system. 3.2.6 Syntax of Numeric Selection The mechanism f o r specifying numerical s e l e c t i o n from a f i l e i s to q u a l i f y the f i l e name by a selector l n a GIDS command, I.e., to specify a q u a l i f i e d f i l e . The selector defines the scope of the processing task within the f i l e . The syntax of the numeric selector Is the s t r i n g "SC0BJ5=" followed by a l o g i c a l expression of constants and fieldnames from the f i l e enclosed i n parentheses. Selection occurs by evaluating the l o g i c a l expression for each record . and selecting only those records for which the expression Is true. A l l of the fieldnames within the selector must appear verbatim In the record descriptions (headers) of one of the f i l e s which the selector q u a l i f i e s . The l o g i c a l expression can be quite general. Any of the following r e l a t i o n a l operators can be usedt =, -» =, <, - i C , > , -TI>, > = , < =. The following l o g i c a l operators are also accepted t & for "and", | for "or". In the future, one may also be able to use functions such as "sine" ln the expression, but thi s feature Is not currently Implemented. 81 For readers with a th e o r e t i c a l bent the syntax of q u a l i f i e d f i l e s ( q f i l e s ) i s defined below using Backus Normal Form. Note that S can be used as an abbreviation f o r SCOPE. The l o g i c a l expression can also contain any integer or r e a l constant. Real constants cannot be expressed with an ex-ponent but must be written out longhand with a decimal point. Thus, 0.005 i s acceptable, but 5»0$-3 i s not. Examples are given below. Assume LANDUSE.G i s a l o c a t i o n a l (geographic) f i l e containing land use polygons and that LANDUSE.R i s the p a r a l l e l row f i l e that contains the land use codes. Further assume that the fieldnames for the f i l e LANDUSE.R are POLYGONNO and LANDUSE. ff,qflle ^selector ) <scopeword^ <file> <fname> <scope> :: = <£lle> | <f ile> <selector> tt = <scopeword^ = <scope> : * = scope I s : t - (f name) | ( <f name) , <f name^) 11 = <MTS f i l e or device name> tt - ^ l o g i c a l expression of fieldnames and constants^ Qualified F i l e The Resulting Set of Selected Records 1. (LANDUSE.R, LANDUSE.G) A l l records in the f i l e s 2. LANDUSE.R SCOPE=(LANDUSE =20) A l l records for LANDUSE.R with land use code of 20 82 Qualified F i l e The Resulting Set of Selected Records 3. LANDUSE.R S=(LANDUSE >=10 & LANDUSE <21) k. LANDUSE.R SCOPE*(AREA>2) 5. LANDUSE.G SC0PE=(AREA>2) 6. (LANDUSE.R, LANDUSE.G) SCOPE*(LANDUSE=20 & AREA>2) 7. LANDUSE.G SCOPE*(MINX>5 & MAXX<10) 8. LANDUSE.G S=(MINX+10* (MINY-1)>=100.35) 9. (LANDUSE.R, LANDUSE.G) S=(LANDUSE=20 | AREA>2) A l l records with land use from 10 to 20 Inclusive W i l l not work because AREA is not a fieldname for LANDUSE.R A l l polygons with an area > 2 units A l l records which were selected both In #2 and ln #5 This w i l l e f f e c t a form of windowing. Only polygons with a l l x values l y i n g between 5 & 10 w i l l be selected This example shows that arithmetic expressions within the selector can be evaluated. Polygons that s a t i s f y the given condition w i l l be selected A l l records which were selected In #2 or In #5 or ln both 3 t2i7 The Implementation of  Numeric Selection The method of evaluating these l o g i c a l expressions Is based on an algorithm given by Barron (1968, p.29 ). When the f l i e s are opened the selector expression Is encoded ln P o l i s h notation (by the routine ENCODE). Then the Po l i s h expression Is evaluated for each record l n the f i l e (by the routine EVAL) using a p r i o r i t y stack for the operators. 8 3 3 » 2 « 8 Command Processing Command processing Is handled very simply. The supervisor program receives a command from the user and passes It on to the scanner. The scanner returns a fixed length representation of the command s t r i n g . The super-v i s o r checks only the command name and dynamically loads the appropriate command routine. Since It Is this oommand routine which examines the command In d e t a i l , the syntax of commands can be changed Independent of the supervisor. The scanner Is an Independent package (Parker, 1971 b) which Is used by several command systems other than GIDS. K e y w o r d s , command words, optional words and special characters of the command language are defined ln a keytable f i l e by the system developer. At the beginning of every GIDS run, the scanner Is i n i t i a l i z e d and these tables are read Into core. Upon being passed a command, the scanner recog-nizes Integers and these s p e c i a l words and marks other strings as variables. For each entity in the command, the scanner returns the entity type (integer, keyword, optional word, command word, variable) and a unique i d e n t i f i c a t i o n number. Because the command language Is defined as data on a f i l e , I t can be changed simply by edi t i n g the f i l e . Herein l i e s the power of this approach. Verbosity l n commands can be e a s i l y handled by defining common words as optional e n t i t l e s In the keytable f i l e to be Ignored during processing. 84 Each command routine scans i t s own commands. However, there i s one routine, TABSEL, which i s c a l l e d by a l l commands to scan off f i n a l f i l e names. The use of t h i s routine i s warranted because f i l e names may be quite complicated, consisting of one or two MTS f i l e names and possibly a selector. The TABSEL routine returns to the command routine a pointer to the end of the f i l e name in the command. It i s there that the command routine continues i t s scanning of the command. Since the command routine has no idea i f there i s a selector or not, TABSEL has made selection completely transparent to the command routine. This very important routine w i l l be described further i n Section 3 .3.4. 3.3 INPUT/OUTPUT STRUCTURES FOR THE PROGRAMMER* 3.3.1 Introduction* So f a r i n t h i s chapter, the f i l e structures and concept of selection have been described. Now, d e t a i l s are given on the input/output routines and the tables they keep. The remainder of the chapter provides quite detailed docu-mentation and hence should be of more int e r e s t to a GIDS programme than a general reader. 3.3.2 F i l e Numbers* When a GIDS f i n a l f i l e i s opened for reading or wri t i n g , i t i s assigned two integer f i l e numbers, usually denoted IFILE and JFILE. IFILE i s a f i l e number for the 85 descriptive part of the f i l e and JFILE i s a f i l e number for the l o c a t i o n a l part of the f i l e . F i l e s are referred to i n most routines not by name, but by these f i l e numbers. F i l e numbers are assigned i n ascending order during a run so that each f i l e i s uniquely i d e n t i f i e d by Its numbers. A f i l e number i s 0 i f that component of the data i s missing in the f i l e , and i f a f i l e number of 0 i s passed to any routine, no action Is taken. The table below shows the values of IFILE and JFILE f o r d i f f e r e n t types of f i l e s . TABLE V THE VALUE OF FILE NUMBERS FOR DIFFERENT TYPES OF FILES UNDER GIDS TYPE OF FILE IFILE JFILE 1) Not a GIDS f i l e 0 0 2) Descriptive n 0 3) Locational 0 n 4) Merged n n 5) S p i l t n m (n * m) (Assume m and n are p o s i t i v e Integers and m * n) 86 3.3.3 F i l e Tables* This section describes the tables by which f i l e management occurs. There i s one global table c a l l e d FLIST that contains a l l the f i l e numbers and pointers to the associated tables for each f i l e . Thus, given a f i l e number, i t s tables can be located. For each f i l e there i s a table c a l l e d LOCAL which i s kept in v i r t u a l memory while the f i l e i s open. The LOCAL table contains pointers to the f i l e headers, informa-t i o n on the f i l e selector, and other information such as record lengths. At the close of every command, the f i l e tables are a l l released. See Figure 3.6 for a picture of these f i l e tables. 3.3.4 F i l e Opening  Routine—TABSEL* TABSEL i s c a l l e d by the command routines to open the f i l e s and take care of sel e c t i o n . It i s passed the scanner arrays containing the command and a pointer to the place in these arrays where the filenames begin. I t extracts the filenames, opens the f i l e s , assigns each f i l e a number, reads in the f i l e header, f i l l s in the LOCAL table, sets up I/O buffers and, i f there i s a selector, i t c a l l s the BFLAG routine to encode the selector. If the f i l e s do not have v a l i d headers, i t signals an error and returns. TABSEL returns three items to the c a l l i n g program: the two f i l e numbers IFILE and JFILE with values appropriate to the type IFILE JFILE GLOBAL FILE TABLE 1 2 3 0 \ Local Table General Header Locational Header Row Header F i e l d Header Selector Local General Header Table Row Header F i e l d Header Figure 3.6 F i l e Tables CO 88/ of f i l e s as shown i n Table V, and a pointer to the end of the filename in the command. If there i s a selector i t i s treated as part of the filename. This i s a powerful feature because the command routine which c a l l e d TABSEL continues scanning the command af t e r the filename without knowing i f there was a selector or not. In other words, selection i s completely transparent to the command routines. 3.3.5 Sequential Read Route-TREAD» This routine reads the f i l e ( s ) sequentially and re-turns the next record that i s selected. It i s passed two f i l e numbers and a f l a g which indicates whether selection i s to be turned off or not. If both f i l e numbers are non-zero, both a descriptive and l o c a t i o n a l record and their lengths are returned. To do t h i s , TREAD reads the f i l e s u n t i l i t finds the next matching record within the sp e c i f i e d scope. Both numeric selection and selection by presence or absence may be in e f f e c t . (See F i g . 3.7 for a flowchart). When only one component i s to be read, the operation i s much simpler because there i s no selection by presence or absence of row records. When there are several row records associated with a single l o c a t i o n a l record, the same l o c a t i o n a l record i s returned several times, once with each of i t s row records. A l l of t h i s i s best explained by another example. Below are l i s t e d the polygon numbers of s p l i t f i l e s . Here polygon 1 w i l l be read, polygon 2 w i l l be skipped, and Figure 3 . 7 The operation of TREAD when both a l o c a t i o n a l and a descriptive f i l e are being read. 90 polygons 3 and 4 w i l l be returned once, and twice respec-t i v e l y ; but then, in looking for polygon 5» a l l the loc a -t i o n a l f i l e Is read and en d - o f - f l l e occurs. Hence, absent row records lead to se l e c t i o n , whereas absent polygon records lead to e n d - o f - f l l e . Descriptive F i l e Locational F i l e 1 1 3 2 4 3 Polygon #s 5 6 » t 100 100 In addition to performing selection, TREAD also con-verts the data to a convenient form for processing as shown In F i g . 3.8. On the f i l e data Is stored l n fixed blocked format with a record type at the beginning of each record. TREAD Id e n t i f i e s the type of record by the record type and then deletes t h i s record type and copies a l l of the blocked records into one long continuous record. It returns to the c a l l i n g program a pointer to this long record and Its length. 3.3.6 Sequential Write Routlne-TWRITE* The write routine Is Invoked exactly the same way as the read routine and s i m i l a r steps are performed ln reverse (see F i g . 3.8). Records are blocked and a record type Is Polygon #s THE WAY THE DATA IS ACTUALLY STORED ON GIDS FILES record type Poly.# record type dimens, points "i r 5 1 3 \20 Land use descriptive record io : •T i t i i l o c a t i o n a l record TWRITE TREAD descriptive record l o c a t i o n a l record 3 :io Poly.# Land use dimensioning points VIEW OF THE DATA BASE PRESENTED TO PROGRAMS . Y^ Figure 3.8 A view of the data as stored on the f i l e and as presented to processing programs. 92 inserted at the beginning of each record. Numeric s e l e c t i o n can take e f f e c t as a f i l t e r on wri t i n g , Just as i t did on reading. This might be useful i f polygons have been i n t e r -sected and we want to f i l t e r out polygons of interse c t i o n whose areas are too small to be s i g n i f i c a n t . 3.4 HOW TO PROGRAM A COMMAND USING FOUNDATION ELEMENTS OF GIDS* This section demonstrates how a new command can be implemented by building on the foundation elements that have been described in thi s chapter. In t h i s way, i t provides an insight into the structure of GIDS and demonstrates how e a s i l y the system can be extended. An example i s shown of how to add a command to copy a sel e c t i o n portion of one f i l e to another (COPY command). F i r s t , the programmer must look at the function to be performed, decide (dn the options to be available to the user, and then, specify a command syntax which allows a l l these options to be expressed as command parameters. After the syntax i s chosen, he must enter the reserved words of the command into the GIDS keytable f i l e as described in the scanner writeup (Parker, 1971 b). Then he must code the command routine to process this new command. If the command processes f i n a l f i l e s , t his routine w i l l necessarily contain the following parts t 1) a l a b e l l e d common area by the name of SKIN to oontain the scanner array representation of the command, and a routine to extract needed command information from th i s table; 93 2) a c a l l to the f i l e opening routine TABSEL fo r every f i n a l f i l e named in the command; 3) c a l l s to the TREAD/TWRITE routine f o r every record to be read/written into a f i n a l f i l e . The steps in adding a new command are c l a r i f i e d by considering an example. Assume, for example, one wants to program a command to copy a selected portion of one f i l e to another. F i r s t , the syntax of the command i s spe c i f i e d . COPY " q u a l i f i e d f i l e " to " q u a l i f i e d f i l e " Two words must be inserted i n the system keytable f i l e — " C O P Y " as a command word and "TO" as an optional word. Then the command routine i s programmed. It consists of two small routines, one to scan f o r the two filenames and to c a l l TABSEL with each, and the second to s e l e c t i v e l y read one f i l e using TREAD and t o . s e l e c t i v e l y write the other using TWRITE. See Appendix E for a . l i s t i n g of the source program. In order to awaken the COPY command to l i f e only one small change had to be made to any exis t i n g programs; the supervisor had to be modified to load the appropriate f i l e when a COPY command i s entered. *«*#«** 94 CHAPTER 4 OTHER PARTS OF THE SYSTEM 4.1 THE INPUT SUBSYSTEM 4.1.1 Introduction This section describes GIDS approaoh to data Input and compares i t with that of several other d i g i t i z i n g systems. Then, the detailed steps of the input procedures are given. The input subsystem includes a l l the programs, equipment and techniques for taking a map, encoding i t i n machine readable form, e d i t i n g i t , and converting i t to the required coordinate system. The problems of act u a l l y pre-paring the map ( i . e . , data acquisition) have been covered in Chapter 1 and are not dealt with further here. The d i f f i c u l t y of encoding polygons should not be underestimated. Goodchild (1972, p. 31) notes that i t consumed sixty per cent of the costs in the PIOS system (Dangermond). 4.1.2 GIDS Approaoh to  Data Input The designers of GIDS r e a l i z e d that data input was a large enough problem i n i t s e l f to occupy a l l t h e i r time. They decided instead to choose the simplest input scheme that would do the Job, leaving them to concentrate on other graphical and a n a l y t i c a l c a p a b i l i t i e s . This decision seemed 95 appropriate at the time; experience has now shown that data input i s the weakest part: of GIDS. The f i r s t decision i n any input system i s whether to use scanning or d i g i t i z i n g for encoding the data. Since scanning equipment was not available but a manual d i g i t i z e r was, we chose d i g i t i z i n g . 4.1.3 A Quick Survey of Four  D i g i t i z i n g Systems In manual d i g i t i z i n g errors are always introduced by straying o f f the l i n e . Finding and correcting these errors i s one of the major problems f o r a d i g i t i z i n g system. Four d i g i t i z i n g schemes w i l l be outlined, which r e f l e c t some of the more common approaches to th i s problem of e d i t i n g (see Table VI). F i r s t and simplest in i t s computer requirements i s the method used by GIDS. Each polygon i s d i g i t i z e d i n turn with no s p e c i a l care as to which points in the polygon are chosen. The r e s u l t is that l i n e s are d i g i t i z e d twice, often with a discrepancy in the two d i g i t i z a t i o n s of the same l i n e . These discrepancies are edited manually by comparing a computer plot with the o r i g i n a l , map. Other systems u t i l i z e more sophisticated d i g i t i z i n g techniques which enable the computer to perform some of the e d i t i n g . The Map/Model system (Arms, 1970) d i g i t i z e s one polygon at a time, but i t does much of i t s error detection automatically by a method known as "redundant l i n e e d i t i n g . " 96 This method i s based on the.fact that a l l l i n e segments should be d i g i t i z e d exactly twice ln a polygonal map i f the map perimeter Is d i g i t i z e d as a polygon (see F i g . 4 . 1 ) . By checking that each l i n e segment does, indeed, appear twice ln a d i g i t i z e d data set, programs can detect polygon omissions, duplications and errors. A l l the d i g i t i z e d l i n e segments are sorted and matched. If the two d i g i t i z a t i o n s of a l i n e segment are within a certain tolerance, they are averaged; If not, an error Is flagged. There are two d i s -advantages to t h i s method over the method used by GIDS. F i r s t , a l l points to be d i g i t i z e d must be marked beforehand on the map and, secondly, computer costs are much higher. /' j Note that every l i n e 1 i $ \ segment Is d i g i t i z e d s^^^ j twice. (The l i n e s ^ ^ j are actually super-Y 2 Imposed not separated ' • > as shown). Figure 4.1 A polygonal map as d i g i t i z e d by the Map/Model System. A t h i r d method Is exemplified by David Douglas 1 BNDBYNET program at Simon Fraser University (1972). One l i n e segment rather than one polygon Is d i g i t i z e d at time and hence each l i n e segment i s only d i g i t i z e d once. This leads to savings on two accounts: there Is less d i g i t i z i n g , and the problem with discrepancies between the two d i g i t i z a t i o n s of the same l i n e Is eliminated. Given only the position of the points and which points are joined by edges, BNDRYNET w i l l f i n d the 97 polygons. The program locates a l l the Intersections, cuts of f the t a i l s at these intersections, and then traces out closed c i r c u i t s (polygons). The main l i m i t a t i o n of BNDRYNET is that the computer cost increases as the square of number of points; hence, i t becomes very expensive to use for maps with a large number of points. Usually such maps are input in sections of no more than a thousand points each. With a l l three systems described so f a r , several days are normally required to input a map because one must execute several i t e r a t i o n s of the process; edit o f f - l i n e , input, and plot hard copy. The l a s t system to be described aims at doing a l l of this i n one session by permitting on-line e d i t i n g . Ray Boyle (1972) at the University of Saskatchewan has implemented on-line editing with a hardware configura-tion that includes a dedicated mini-computer, disk, and i n t e r a c t i v e graphics terminal. The t o t a l hardware cost i s an amazingly low #34,000 (Boyle, 1972, Appendix G). Boyle has also done research on many other aspects of data input such as automatic l i n e following, joining l i n e s across map boundaries, and o p t i c a l character recognition. A l l these features together with the i n t e r a c t i v e e d i t i n g make Boyle's d i g i t i z i n g system among the most advanced in the world. Peter Vanden Bosch (1971) did some work on an i n t e r -active polygon editor for GIDS. However, we were discouraged from pursuing this approach because the only available i n t e r -active graphics terminal at UBC was too expensive to use for production e d i t i n g of data. 98 TABLE VI A COMPARISON OF FOUR SYSTEMS FOR DIGITIZING POLYGONAL MAPS GIDS MAP/MODEL BNDRYNET Boyle 1) Preliminary work in preparing the map none mark the points to be d i g i -t i z e d decompose large maps into smaller sections 2) The number of times each l i n e i s d i g i t i z e d twice twice once twice 3) Method of error detection o f f -l i n e com-parison of p l o t and map pl o t plus redundant edit by computer o f f - l i n e comparison of pl o t and map on-line comparison with pro-gram help 4) Method of error correction manual o f f -l i n e manual o f f - l i n e o f f - l i n e on-line 5) Computer required f o r inputting maps medium size com-puter large computer large computer mini-computer Increasing Sophistication 4.1.4 GIDS D i g i t i z i n g  Procedure Figure 4.2 shows the d i g i t i z e r setup used by GIDS. The d i g i t i z e r hardware consists of a large recording table, a cursor, a control unit, and a keypunch. The (x,y) position 99 of the cursor on the table i s recorded by the control unit and punched on a computer card by the keypunch when the operator depresses a button or foot pedal. Before d i g i t i z i n g , the map and associated menu are c a r e f u l l y oriented as shown and taped to the d i g i t i z e r table. The o r i g i n Is set at the lower r i g h t corner of the menu so that a l l points on the menu w i l l have a negative x-coordlnate. This menu consists of gr i d squares with each square containing a d i f f e r e n t code f o r the at t r i b u t e . Codes are associated with a polygon by d i g i t i z i n g a point ln the appropriate square before d i g i t i z i n g the points on the polygon boundary. (See the sample output i n Fig . 4.2). 4.1.5 Input Procedure From the time a map Is d i g i t i z e d u n t i l I t Is written out In f i n a l form, the same Information Is stored ln three d i f f e r e n t forms—as a d i g i t i z e r f i l e , an Intermediate f i l e , and a f i n a l f i l e . A p a r t i a l l i s t i n g of a l l three types of f l i e s together with a sample Input run appear l n Appendix C. Each of these f i l e structures w i l l be described b r i e f l y , and then the steps to Input a map w i l l be outlined. The d i g i t i z e r f i l e contains 2 control cards followed by the d i g i t i z e d data. Each polygon begins on a new card. There Is one or more menu points (which specify attributes of the polygon)) followed by Its centrold and boundary coordinates. 100 DIGITIZER TABLE 1 LAND USE MAP MENU 1 a 3 f S Io 7- t q l O II fa i CURSOR NEGATIVE X POSITIVE X x 1 DIGITIZER CONTROL UNIT OPERATOR KEYPUNCH JZIOIJOOOI —O0.3S * Ol-iS ' I 3 . 0 I **3.il +,o.&--toast » * v . " ' v „ 1 _ header menu centroid boundary! point points Figure 4.2 The D i g i t i z e r Configuration used by GIDS. 101 B 71 EDITED DIGITIZER FILE INPUT COMMAND INTER-MEDIATE; FILE PLOT COMMAND PLOT COMPARE PLOT & MAP FOR ERRORS EDITED INTER-MEDIATE FILE CREATE FINAL FILES ? * INITIALIZE COMMAND Drr/t SufFICIEfTtl E OITIr 0 \ / / / EDITED FINAL FILES / / Figure 4 . 3 The GIDS input procedure. 102 The map data Is next stored i n "intermediate f i l e " form. This f i l e i s formatted in a way that f a c i l i t a t e s the d i f f i c u l t e d i t i n g process which must invariably occur. It i s produced as the output of the INPUT command and expected as input for the PLOT and INITIALIZE commands. The format i s described in d e t a i l i n Appendix F. The f i n a l form f o r the geographic data i s the f i n a l  f i l e structure that was described in Section 3.1. Whereas the d i g i t i z e r and Intermediate f i l e s contained data i n d i g i t i z e r inches the f i n a l f i l e contains data in a user-s p e c i f i e d coordinate system. These f i l e structures are designed for e f f i c i e n t input and output as they w i l l be processed often by a l l the data, manipulation commands of GIDS. The input steps are enumerated below» 1. D i g i t i z e the map and store the r e s u l t in a d i g i t i z e r f i l e . 2. Edit t h i s f i l e for any errors which can be detected. 3. Use the INPUT command. This reads the d i g i t i z e r f i l e , does some data massage, and writes the r e s u l t i n g intermediate data out i n intermediate f i l e form. 4. E d i t the intermediate f i l e for any errors detected by INPUT. 5. Plot the intermediate f i l e with the PLOT command. 6. If the plot compares well enough with the o r i g i n a l map go to 7» otherwise return to step 2 or 4 and do the necessary e d i t i n g . 103 7. Create the f i n a l f i l e and Its headers using the CREATE command. 8. Use the INITIALIZE command. This reads the Intermediate f i l e , transforms the data to user-specified scale and o r i g i n , calculates a l l the dimensioning information and then writes the f i n a l f i l e . Figure 4.3 depicts t h i s input procedure p i c t o r l a l l y . 4.1.6 Experience with  the Input System The Greater Vancouver Regional D i s t r i c t has used GIDS for Inputting a set of 16 land use maps. It was found that the f i r s t map had to be edited and plotted no less than 10 times. However, with improved d i g i t i z i n g and editing procedures (Tautz and Belford, 1972) 3 or 4 passes were s u f f i c i e n t for l a t e r maps l n the serie s . The costs to input the data w i l l be given i n Chapter 5. 104 4.2 THE GRAPHICS SUBSYSTEM 4.2.1 GIDS Approach In the graphics subsystem we have developed a very useful t o o l f o r the display of geographic data. Our aim was to give maximum graphic v e r s a t i l i t y with minimum user s p e c i f i -cations. I t was not high accuracy, but quick and easy genera-ti o n of a variety of maps which was Important. V e r s a t i l i t y has been achieved by permitting a variety of symbolism and a var i e t y of graphic devices. 4.2.2 Graphics Functions The functions performed by the GIDS graphics system are drawing and superimposing maps, where maps are made up of the following p r i m i t i v e s i 1) the boundaries of selected points, l i n e s or polygons from a given l o c a t i o n a l f i l e ; 2) symbolism* (a) shading of polygons according to the value of one of t h e i r a t t r i b u t e s ; (b) l a b e l l i n g of points, l i n e s or polygons with the numeric or alphameric value of one of their a t t r i b u t e s ; (c) regular geometric symbols at the centre of the point l i n e or polygon; 3) t i t l e . A l l maps contain at l e a s t the selected boundaries, and they may also be symbolized and have a t i t l e . Furthermore, any two of the three types of symbolism can be combined ln a map. 105 4.2.3 Graphics Commands At th i s point, It Is Interesting to consider the syntax of the graphics commands because It c l e a r l y r e f l e c t s GIDS view of the primitives of a map. This consideration also provides a concrete example of the advantages of a command language. We s h a l l define the syntax and then I l l u s -t r a t e various options of the DRAW command (see F i g . 4.4). An example of a SUPERIMPOSE appears In Figure 4.5. denotes an optional parameter. This s p e c i f i e s the name of the f i l e and the subset of the f i l e from which the point, l i n e or polygon boundaries are to be drawn. •marked1 BY * fieldname• This parameter s p e c i f i e s the type of symbolism to be used on the map. I f i t Is omitted no symbolism Is drawn (see F i g . 4.4 a). Some of the types of symbolism available are shown l n the plots of Figure 4.4. .... A complete l i s t of the marking option available Is given ln Appendix A. Note that the command s t r i n g Is automatically used as a t i t l e f or the map. ON 'graphic device' This parameter controls the graphic device to which the graphs are to be directed. Section 4.2.5 describes the graphic devices available at UBC. • q f l l e ' ['marked' BY 'fieldname*] £bN 'graphic device?] • q f l l e ' FIGURE 4.4 106 DRAW (MUNI.R.MUNI.G) CODED AND SYMBOLLED BY MUNICIPALIT FIGURE 4.4 10? DRAW (MUNI.R.MUNI.G) CODED BY MUNICIPALITY DRAW (MUNI.R.MUNI.G) SHADED BY MUNICIPALITY f DRAW (MUNI.R.MUNI.G) CODED AND SHADED BY MUNICIPALITY DRAW (MUNI.R.MUNI.G) TRIANGLED BY MUNICIPALITY DRAW (MUNI.R.MUNI.G) SHADED AND TRIANGLED BY MUNICIPALIT DRAW (MUNI.R.MUNI.G) CODED AND TRIANGLED BY MUNICIPALITY Figure 4.4 A map of 3 municipalities symbolized l n various ways. 109 DEflSE LAKE ( IBRD RIVER FINLflY STIKINI D MF)P_805.G SUP (MAP_804 .R .MAP_804 .G ) LABELLED BY WATER-ELEMENT Figure 4 . 5 Sample output produced by a DRAW command followed by a SUPERIMPOSE command. (This map depicts a section of northern B r i t i s h Columbia). 110 4.2.4 Shading and Geometric Symbolism Symbolism employs d i f f e r e n t i a t i o n ln shape, size or colour to connote differences i n s p a t i a l Information. 1 Two types of symbolism used by GIDS p a r t i c u l a r l y meant some commentst shading and geometric symbolism. Shading Is a powerful symbolism for d i f f e r e n t i a t i n g regions of d i f f e r e n t c h a r a c t e r i s t i c s . (See the example i n Appendix C which shades r e s i d e n t i a l land by d e n s i t y — t h e higher the density the darker the shade). In a shaded map each polygon i s shaded to one of seventeen l e v e l s of dark-ness (see Pig. 4.4. e and f ) . The darkness of a polygon Is l i n e a r l y proportional to the value of the "SHADED BY" a t t r i -bute A. The formula used i s darkness = 16 x (A - MINA) MAXA-MINA where MINA and MAXA are the minimum and maximum values of the attributes f o r a l l selected polygons. To produce a shaded graph, the selected f l i e s must be read twice, the f i r s t time to determine MINA and MAXA, and the second time to draw and shade the graph. Shading i s Implemented by p a r a l l e l l i n e s patterns, dot patterns, or character patterns depending on the graphic xSee Mapping Quantitative Information (Fisher. 1970) for I l l u s t r a t i o n s of many types of symbolism. I l l device (see Table VII) To f a c i l i t a t e the d i f f e r e n t i a t i o n of regions shaded by p a r a l l e l l i n e s , the angle Is varied as a function of the shading factor (see F i g . 4.6). TABLE VII METHOD OF SHADING ON DIFFERENT DEVICES Device Method fo r Shading on Area Method f o r d i f f e r e n -t i a t i n g darkness 1) P l o t t e r s , Vector CRT'S 2) Dot printers 3) Line pri n t e r families of p a r a l l e l l i n e s within area regular dot pattern within an area the same character at every p r i n t position within an area v a r i a t i o n l n angle and spacing of p a r a l l e l l i n e s density of dots the darkness of the prin t character GIDS employs two types of shading f o r the p l o t t e r s : p a r a l l e l l i n e shading and cross-hatching as shown l n Figure 4.6 ia) and (b) respectively. Robinson notes that dot patterns are v i s u a l l y more stable than p a r a l l e l l i n e s (1969* p. 255). However, dotted shading Is also much more d i f f i c u l t to Im-plement on a pen-plotter device. The cross-hatching e f f e c t , which i s achieved by drawing two families of p a r a l l e l l i n e s perpendicular to each other, Is more pleasing to the eye but almost twice as expensive as there are twice as many shade l i n e s to draw (see Table VIII). D (DISTRICTS.R.DISTRICTS.G) SHRDED BY HIGHWflY_DIS Figure 4.6 a An example of p a r a l l e l l i n e shading on the calcomp. (This depicts 8 highway d i s t r i c t s in B.C.) 113 114 TABLE VIII THE EFFECT OF MAP SIZE AMD THE TYPE OF SHADING ON THE COST OF DRAWING ON THE PLOTTER P a r a l l e l l i n e Shading Cross-hatching P l o t time for large p l o t VPlot time f o r small plot 29.3 minutes 59.9 minutes 5.0 minutes 9.25 minutes Plot cost f o r large plot P l o t cost for small plo t 1 9.75 $19.98 I.67 3.08 CPU time for large plot CPU time for small plot 20.3 seconds 30.1 seconds 11.89 seconds 14.00 seconds CPU cost for large p l o t CPU cost f o r small plo t $ 1.41 $ 2.09 0.85 1.00 Large Plot = 34" x 26" Small Plot = 12" x 9" Plotter = Calcomp Table VIII also shows the e f f e c t of the map size on the plot costs; by reducing the map by a factor of three the p l o t cost was reduced by a factor of s i x . The use of small geometric characters as symbolism i s achieved by drawing a regular n-gon at the centroid of the polygon with n being proportional to the value of the "SYMBOLIZED BY" attr i b u t e (see F i g . 4.4 b and c ) . This type 115 of symbolism i s most appropriate for nominal data such as land use codes. However, GIDS choice of symbols Is poor because It Is very d i f f i c u l t to d i s t i n g u i s h between an n-gon and an (n+l)-gon when n Is greater than about 5« Also, the user cannot control the symbols as the number of sides Is determined by a formula depending on the minimum and maximum codes. Hence, a land use code of 40 f o r "vacant" might be represented as a square l n one plot and a hexagon In another. For these two reasons geometric symbolism has not been very useful i n GIDS. Shading and symbolism could be much improved If the following features were Included In GIDSt 1) the a b i l i t y to define a function that associates d i f f e r e n t values of an attribute with given shadings or symbols. This would enable a user to better control the symbolism on his map. 2) the a b i l i t y to code, shade by, or symbolize the values of arithmetic expressions, Instead of just the values of f i e l d s . For Instance, If one had the population of each census t r a c t , one could shade by POPULATION/AREA and hence display a population density. 3) the a b i l i t y to Include text of s p e c i f i e d size at a s p e c i f i e d position on a map. 4.2.5 Graphics Devices Available Most mapping systems are geared exclusively towards one device. For SYMAP (Harvard, 1968) It Is the l i n e p r i n t e r , fo r high accuracy systems It Is the flatbed p l o t t e r , and for Interactive systems It Is the CRT. However, often there are several d i f f e r e n t graphic devices available at a single 116 i n s t a l l a t i o n . These devices usually have a wide range of c h a r a c t e r i s t i c s and hence are useful in d i f f e r e n t circum-stances. For example, there are at l e a s t f i v e types of graphic devices at the University of B r i t i s h Columbia. 1) Adage int e r a c t i v e graphics terminal. It gives the quickest response and most v e r s a t i l i t y but i s also the most expensive to use. It can be controlled i n t e r a c t i v e l y v i a a l i g h t pen and other in t e r a c t i v e controls. 2) Techtronix Storage Scope. This CRT device has a slower response time than the adage but i s much cheaper to use. Its screen i s smaller than the adage but can hold more information. 3) Calcomp drum p l o t t e r s . These are pen p l o t t e r s that produce hard copy plots of widths 10 and 30 inches on blank or graph paper. Their plots are much higher qu a l i t y than pri n t e r plots but much more expensive (|20 an hour for plo t time) and have stjnuch longer response time (at least several hours). However, calcomp plots are accurate to .01" whereas l i n e printers are accurate to one character i n the x-direction and one p^inkallneiln^theay-direction. (See f i g . 4.4). 4) Line p r i n t e r . This produces hard copy plots much cheaper and quicker than a p l o t t e r . However, the quality of maps i s much l e s s . (See F i g . 4.7). 5) Versatec dot p r i n t e r . This e l e c t r o s t a t i c printer produces small hard-copy plots which are of comparable accuracy to the p l o t t e r output. Espe c i a l l y good shading effects can be obtained (see F i g . 4.8). Clearly there i s a wide spectrum of devices at UBC. GIDS i s d i f f e r e n t from other systems i n that i t does not r e s t r i c t a user to one device, but l e t s him choose the device most suited to his needs. For example, i f he wants a "quick and d i r t y " map he can use the l i n e p r i n t e r , but i f he wants a good reference plot he can use the calcomp or dot printer. 117 Figure 4 . 7 A plot of Vancouver on the dot p r i n t e r . * * *. * * * ** * * * * * * * * * * * * * * * * * * ** * * * * **.*** * * «* * * * **** * * * * * * * * r * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** * * (.**»**** * * * * * * * > Figure 4 . 8 A p l o t of three municipalities on the l i n e p r i n t e r . lit? 4.2.6 Device-Independent Graphics and Other Concepts The c e n t r a l concept behind the GIDS graphics system i s device-independent graphics. The idea i s that a l l the device dependencies of d i f f e r e n t graphic devices are made i n v i s i b l e to the user. Hence, he can choose the device most suited to his needs without concern for the d e t a i l s . A canonical graph and a l o g i c a l area are two other useful concepts that are related to device-independent graphics. A canonical graph i s an abstraction of the shape of a graph, independent of the device, scale, and mode of presentation. It i s a generalized form for representing a great variety of graphs. A l l the information required to plot a graph can be obtained from the canonical graph data structure. A l o g i c a l area i s an abstraction of the medium or device on which the graph i s to be plotted. Both these concepts originated in the graphics package of the Simulator/Supervisor system (Parker, 1971 c; McRae, 1972) developed i n the Department of Computer Science at the University of B r i t i s h Columbia. This i s a system for super-v i s i n g the execution of int e r a c t i n g simulation models i n whioh the r e l a t i o n s h i p s among the variables can be displayed on any l o g i c a l area as l i n e , point, or other types of graphs a l l stored as canonical graphs. On his experience with this system the author found that the canonical graph and the l o g i c a l area concepts c l a r i f i e d the problem of having many types of graphs which can be plotted on many devices. Display space Is a term used In computer graphics f o r the space on which graphs may be drawn. For a p r i n t e r or p l o t t e r It Is the paper and for a CRT device It Is the screen. Rather than drawing only one graph on a l l of the display space, It may be advantageous to divide display space into several l o g i c a l areas and draw one graph on each area. For example, two l o g i c a l areas may be established on a p l o t t e r and then graphic output may be directed to an "area" rather than to a "device." One can Imagine there Is one v i r t u a l  device for each area whose job i s to plot on that area. An analogy can be drawn between a l o g i c a l unit and a l o g i c a l area of a FORTRAN program, PROG, writes output on l o g i c a l unit 7 . Logical unit 7 must be assigned to a 2 physical unit ( f i l e or device) before execution. Si m i l a r l y a l o g i c a l area must be assigned to a physical area (graphics device) before graphic output can be obtained. 4 . 2 . 7 The O r i g i n a l Graphics Design The o r i g i n a l plan f o r the GIDS graphics system u t i l i z e d both the canonical graph structure and l o g i c a l area concepts. F i r s t , an extractor routine selected the data and massaged It Into canonical graph form. Then, a second routine processed the canonical graph and plotted i t on the l o g i c a l area (see F i g . 4 . 9 ) . *Under MTS the following command establishes this assignment: #RUN PROG 7 = OUTPUT 120 Figure 4.9 The o r i g i n a l design of the graphics subsystem. Several canonical graphs per device were to be stored in computer memory. This would have f a c i l i t a t e d various i n t e r a c t i v e manipulations on the image such as those performed by Deecker's system (1971)J change of scale and centre, and enlarging of one part of the image to f i l l the screen. However, we f i n a l l y decided not to implement th i s because i t was not useful in batch and one of our design c r i t e r i a was that the system be easy to use i n t e r a c t i v e l y and in batch. Graphs produced by r e a l world users of GIDS usually contain too much information to be viewed on only part of display space; but i f only one area i s required on each graphic device the l o g i c a l area.concept Is not very useful. Hence we decided against using l o g i c a l areas; graphs are directed to devices rather than areas with commands l i k e "DRAW...ON CALCOMP" rather than "DRAW...ON AREA 1" In the end, the drawing of maps was implemented as another sequential f i l e processing operation. Each polygon i s drawn, symbolized and then freed before the next polygon i s read In; the only record of i t thereafter i s i n the plot. Device independence was Implemented, but l o g i c a l areas and canonical graphs were not. 121 4.2.8' Implementation of Device Independence Device Independence has been Implemented by establishing a standard interface for p l o t t i n g on a l l the graphics devices. The interface used is the UBC PLOT routines3 plus one added routine for shading. Any program, which draws graphs by c a l l i n g the UBC PLOT routines, Is device independent In that the graphs can be directed to any device merely by running the program with the appropriate version of the UBC PLOT routines for that device. This program i s l i k e a tap spewing out graphs and each version of the UBC PLOT routines i s l i k e a hose which i s connected to i t s graphic device at one end and which can be screwed onto the tap at the other end (see Pig. 4.10). When the command i s scanned, the graphic device, D, i s determined. Then there are almost three tasks to be performed which are s p e c i f i c to the device: 1) Obtain the addresses of the UBC PLOT routines fo r device D. 2) Obtain the size of display space for the device so that graphs can be scaled to f i t on the device. 3) Handle other device-dependent features such as queuing plots for the calcomp. •-'This i s a package of FORTRAN-callable routines for p l o t t i n g l i n e s , symbol, axes, etc. Versions have been written f o r the adage, calcomp, l i n e p r i n t e r (Coulthard), techtronix (Webb), and dot print e r (Mathews) and are available from the UBC Computing Centre. 122 Figure 4.10 Device Independent graphics The draw routine i s defined as the program which i n i t i a t e s the graphic output in that i t invokes the UBC PLOT routines. 123 There are two methods f o r performing the f i r s t two of these three tasks$ I have dubbed them the switch method and the sandwich method. In the switch method the draw routine keeps track of the appropriate size of display space and c a l l s a switch routine which switches control to the appropriate version of the UBC PLOT routines for device D. This method was used by the Simulator/Supervisor System. draw routine switch routine UBC PLOT routines f ADAGE routines CALCOMP routines LINE PRINTER routines DOT PRINTER! routines Figure 4.11 The switch method of device independence. In the sandwich method a preprocessing routine handles the device dependence so that the draw routine can be com-p l e t e l y ignorant of the graphic device on which i t is p l o t t i n g . The preprocessor scans the command to determine the device, sets the size of display space In a common area, and selects the correct UBC PLOT routines to pass to the loader. Hence, upon dynamic loading of the draw routine i t i s automatically linked to the correct UBC PLOT routines. The advantage of the sandwich method i s that device dependence i s completely i s o l a t e d from the draw routine. GIDS uses the sandwich approach. 124 UBC PLOT routines DRAW routine routines Figure 4.12 The sandwich method of device independence 125 4.3 THE INTERSECTION SUBSYSTEM The GIDS intersection system (INTERSECT command) intersects two sets of polygons f o r use as an overlay or as the f i r s t step i n a regional base transformation. This section w i l l discuss the motivation for i n t e r -section, then the techniques for intersecting two polygons and f i n a l l y the techniques for intersecting two sets of polygons. 4.3.1 Motive t l o n — R e g i o n a l  Base Transformation In the o r i g i n a l conception of GIDS, one of the most important operations was the regional base transformation. For example, one might have a map showing s o i l type polygons and another map of study areas, and wants to get the area of each s o i l type within each study polygon (see F i g . 4.13). This transformation i s performed In two steps* intersection , and aggregation. F i r s t , the s o i l and study polygons are i n t e r -sected, then the area of the d i f f e r e n t s o i l types are aggregated to the boundaries of the study polygons. The o r i g i n a l plan c a l l e d f o r performing both these steps within a single GIDS command and not saving the polygons of inte r s e c t i o n afterwards. However, l t became clear that the int e r s e c t i o n f i l e was useful in i t s own r i g h t . One can use composite c r i t e r i a for s e l e c t i n g polygons from i t , or overlay i t with a t h i r d set of polygons. 126 SOIL TYPE rea=2) STEP l l Intersection Study S o i l Area Type Area 1 SAND 8 1 PEAT 2 2 PEAT 7.5 2 SAND 1.5 3 PEAT 6.5 3 SAND 0.5 3 SAND 2 STEP 2t Aggregation Study Area of Area of Area Peat Sand 1 2 3 2 7.5 6.5 8 1.5 2.5 Figure 4.13 Regional base transformation. Hence, two subsystems of GIDS were born—the intersection subsystem (Section 4.3) and the aggregation subsystem3 (Leong, et a l , 1973). To perform a regional base transformation a 3This thesis i s already too long for the aggregation system to be discussed. 127 user must give an INTERSECT command, and then an AGGREGATE command. 4.3.2 Intersecting  Two Polygons 4.3.2.1 E x i s t i n g Algorithms Several algorithms f o r intersecting two polygons have been described in the l i t e r a t u r e (Arms, 1968; Franklin, 1972; Deecker, 1970). Franklin's ANOTB routine i s int e r e s t i n g because i t can f i n d not only the intersection but also the union and a l l of the other 16 possible r e l a t i o n s between two polygons. We obtained ANOTB from the University of Ottawa and found i t not completely r e l i a b l e and not suitable for large data bases because of i t s very large storage require-ments. In his t h e s i s , Deecker (1970, p. 53) presented two algorithms for intersecting polygons. They consist of three basic steps; 1) f i n d the equations of a l l the l i n e segments and then locate any points of intersection; 2) in s e r t these points of intersection in the appropriate places in the l i s t s of boundary coordinates of the two polygons; trace through these l i s t s using a point in polygon routine to determine which points from one l i s t are inside the other polygon. 4.3.2.2 Point i n Polygon  Algorithms One of the most basic operations required by an i n t e r -section routine i s a point in polygon determination, which i s to determine i f a given point i s inside, outside, or on the 128 boundary of a given polygon as shown below. Inside Outside On the boundary Several point In polygon algorithms have been described In the l i t e r a t u r e (Aldred, 1972; Tomlinson, 1972, Chapter 11). Aldred compared the performance of eleven d i f f e r e n t methods and found the line-extension method to be the f a s t e s t single method that gives a complete solution i n a l l cases. This algorithm uses the general p r i n c i p l e that i f a l i n e Is extended i n d e f i n i t e l y in one d i r e c t i o n from the point under consideration, i t w i l l intersect an odd number of polygon sides i f the point l i e s Inside the polygon and an even number otherwise (see F i g . 4.14). GIDS uses a point i n polygon routine of this type obtained from David Douglas at the University of Ottawa. Point 1 i s inside P since there Is an odd number of intersections Point 2 i s outside P since there Is an even number of Intersections Point 2 Figure 4.14 The l i n e extension method for point in polygon determination. Aldred described another class of point in polygon methods which are quicker than the l i n e extension method but 129 do not always give a solution. Typical of these is the smallest rectangle method which can sometimes indicate very quickly that the point i s outside the polygon. If the point i s outside the smallest rectangle containing the polygon, i t i s outside the polygon. However, i f the point i s inside the rectangle, i t i s not determined whether the point i s inside the polygon or not, and another method must be applied (see F i g . 4.15). If a point i s outside the rectangle i t must be outside the polygon If a point i s inside the rectangle i t i s not neoessarily Inside the polygon Figure 4.15 The smallest rectangle method for point i n polygon determination An i n t e r e s t i n g r e s u l t Aldred found was that a multi-stage process, such as the smallest rectangle method followed by the line-extension method, was faster than the l i n e -extension method alone. 4.3.2.3 GIDS method The algorithm GIDS uses to intersect two polygons has been programmed and documented by Dale Troyer (1972). B a s i c a l l y , i t follows the three steps referred to in Section 4.3.2.1. Since Deecker (1970) has already provided us with a mathematical description of a si m i l a r algorithm, we s h a l l explain GIDS algorithm by example. 130 Figure 4.16 shows the steps in intersecting polygon A with polygon B. In the f i r s t stage, the intersections are found and l a b e l l e d with numbers. In the second stage, they are inserted in the l i s t of coordinates as shown to form A - l i s t and the B - l i s t . Now the polygons of intersection are found. Start at (1), the f i r s t point of intersection; mark l t , then begin tracing along polygon B In the d i r e c t i o n that i s inside polygon A. One of the points adjacent to (1) in the B - l i s t must be Inside polygon A and one c a l l to the point i n polygon routine w i l l determine which one. Now trace along B i n that d i r e c t i o n u n t i l the next point of Intersection. If i t i s marked, a complete polygon of intersection has been found. If not, change polygons. Following this method we f i n d the 2 polygons of intersection (the shaded areas in F i g . 4.16). 4.3.2.4 Extendible Design We designed the modules of the intersection routine in such a way that polygon union, complement, and other such routines could be easily added. The f i r s t two steps are the same for a l l these operations; namely, f i n d the points of inters e c t i o n and in s e r t them in a l i s t of coordinates. However, the tracing step i s d i f f e r e n t for polygon intersec-t i o n , union, etc. Thus we wrote one routine, INT, to perform the two steps which are common to a l l , and a separate routine, ITRACE, to read in the l i s t of coordinates and intersections and trace the polygons of i n t e r s e c t i o n . This i s an extendible design in that a polygon union program could be achieved simply by writing a union tracing program (see F i g . 4.17). 131 Stage l t Find the points of Intersection. Stage 2t Insert them In the l i s t s of coordinates In the order they occur on the polygon boundary A - l l s t t (Ai,l,A2,A3,A4,A5,A6,4,A7,3,2,A1) B - l l s t t (,BltB2,ltBjt2fB^t3t35,k,BstBi) Stage 3t trace through these l i s t s f i n ding which points from one l i s t are Inside the other polygon The polygons of Intersection are shaded In here Figure 4.16 The three stages In intersect&ng polygons A and B 132 I N T E R S E C T I O N T R A C I N G R O U T I N E ( I T R A C E ) I N T routine for f i n d i n g points of intersection _ \ ! U N K I TRA( ! R0U1 i i I DN ! : I N G j D I N E i COMPLEMENT TRACING ROUTINE i A and B A or B A not B F i g . 4.1? The structure of the intersection routines showing the extendible design. A dotted box indicates the routine is not yet written. 4.3.2.5 Methods f o r Speeding  up Intersection Since intersection i s the most costly operation performed by GIDS, various techniques were considered f o r reducing t h i s cost. Three of these techniques w i l l be described; namely, checking for the Intersection of minimal rectangles, checking f o r nexting of polygons, and reducing polygons. 133 The f i r s t technique Is to f i n d the Intersection of the minimal bounding rectangles of the polygons. A n u l l Intersection of the rectangles Is a s u f f i c i e n t but not a necessary condition for a n u l l intersection of the polygons. Nevertheless, t h i s test eliminates the majority of cases, (see F i g . 4.18) and i s r e l a t i v e l y cheap. Thus, l t i s used by the GIDS inters e c t i o n routines. Figure 4.18 Intersection of the minimal rectangles can often avoid i n t e r s e c t i o n of the polygons. A^ second t r i c k Is applicable when Intersecting two polygons of widely d i f f e r i n g s i z e s . If these polygons i n t e r -sect at a l l , there i s a high p r o b a b i l i t y that the smaller polygon w i l l be completely contained in the larger polygon. The idea Is to recognize t h i s containment, and hence avoid in t e r s e c t i o n . Assume polygon A i s small r e l a t i v e to polygon B (see Fi g . 4.19) and R A and Rg are the respective minimal bounding rectangles. If R^ i s contained in B, A i s contained i n B, Since the rectangles do not intersect, the polygons do not intersect Rectangles 2 and 3 both intersect 1, but polygon 2 intersects 1 whereas polygon 3 does not 134 I.e., R A In B i s a necessary (but not a s u f f i c i e n t ) con-d i t i o n for A i n B. By four c a l l s to the point in polygon routine we may be able to ascertain that B A Is in B, and hence A i s i n B. Checking f o r t h i s nesting i s more ex-tensive than checking for the intersection of minimal rectangles and less l i k e l y to be applicable; i t was not Included i n GIDS. Figure 4.19 Testing i f the bounding rectangle of polygon A Is contained in polygon B. In general, intersecting two polygons with n and m sides Is an n by m process. When the number of sides Is large and the two rectangles i n t e r s e c t , l t may be p r o f i t a b l e to.reduce the number of sides i n each polygon by intersecting the polygons with the rectangle of intersection, and then in t e r s e c t i n g the two reduced polygons. For example, i n the figure below, instead of intersecting A and B we can Intersect A 1 and B 1. 135 ( M i * , the rectangle of i n t e r s e c t i o n the o r i g i n a l problem—intersect A and B the reduced problem-intersect A l and Bl Figure 4.20 Reducing the polygons before intersection. Cl e a r l y , t h i s operation would not be p r o f i t a b l e i f the polygons had only three or four sides, but would become more p r o f i t a b l e as the number of sides increased. We wondered at what point t h i s polygon reduction would become p r o f i t a b l e , and attempted to answer t h i s by an analysis of the algorithms along the l i n e Knuth has suggested (1970). The d e t a i l s of th i s appear i n Troyer's report (1972). Results indicated some benefit i n reducing the polygons when there were more than about twenty sides in each of the polygons. In summary, there are various techniques which may speed up the inters e c t i o n of two polygons. The Intersection of the minimal rectangles should always be found. If i t i s n u l l , the polygons do not intersect. If i t Is equal to one of the rectangles, i t may be worthwhile to check f o r nested polygons. If the number of points i s large, polygon reduction may be useful. 136 4.3*3 Intersecting Two  Sets of Polygons 4.3.3.1 The Problem In p r actice, a geographic system must Intersect not two polygons but two f i l e s of polygons. If there are n polygons in f i l e A and m polygons in f i l e B, there are nm pairs of polygons which may Intersect each other. However, the actual number of polygons of intersection i s of the order of n+m.^ The problem, then, on which this subsection w i l l focus, is—how to e f f i c i e n t l y f i n d a l l the polygons from f i l e B which Intersect a given polygon from f i l e A. Various methods of achieving t h i s w i l l be described. S t r i p sorting, a method of sequencing polygons by t h e i r loca-tions i n r e l a t i o n to s t r i p s , i s found to be the most suitable fo r GIDS. This method i s described In some d e t a i l as i t i s o r i g i n a l to the author. Indexed f i l e structures have been used to solve t h i s problem (Arms, 1970) in the following manner1 each square in a regular g r i d serves as a key pointing to a l l the polygons which l i e at l e a s t p a r t i a l l y within i t i n the same way that the g r i d squares on a road map serve as an index to the st r e e t s . For example, in Figure 4.21 polygon P l i e s within g r i d squares Aa and Ba. Hence, only polygons from f i l e B For instance, in one case we found that 56O polygons of i ntersection were produced from the intersection of two maps with n=96 and m=377. 137 that intersect Aa or Ba are considered f o r interse c t i o n with polygon P. Indexed f i l e data structure L I 3 A 6 c y ( * / 3 r — -/ ? \ °\ \ ^ KS1 £ a C <x A i L y y H J ? 10 2 (o ...polygon P from f i l e A polygons from from f i l e B 2 5 Cb z 2 10 Figure 4.21 Using an overlaid g r i d as an index to the polygons. Since we had decided to use sequential f i l e s f or GIDS, we could not apply t h i s indexing method. The f i r s t method that oomes to mind f o r intersecting two sequential f i l e s i s what might be c a l l e d the brute force method* Intersect a l l n polygons from f i l e A with a l l m polygons from f i l e B. The NRIS system (Boeing) employs such a brute force technique fo r i n t e r s e c t i o n . They read in one polygon from f i l e A and 138 pass a l l of f i l e By by i t , then read the next polygon from f i l e A and do the same, etc. This method requires reading and rewinding f i l e B n times, once for each of the polygons ln f i l e A. However, t h e i r Intersection times were s t i l l reasonable fin f i l e $ on a CDC 6600 computer. However, we can do better than the brute force method. By ordering the polygons within the sequential f l i e s ln a way that preserves some of the 2-dlmensIonal l o c a t i o n a l Informa-t i o n , we can reduce the number of Intersections that must be made from nm. Each of the following methods of sequencing the polygons In a sequential f i l e w i l l be considered! (a) one-dlmensIonal ordering (b) g r i d ordering (c) s t r i p ordering 4.3.3.2 One-DlmensIonal Ordering Sequencing the polygons l n a f i l e according to their locations ln the y dimension (or the x dimension) Is ca l l e d a one-dlmenslonal ordering. This sort could be keyed to one coordinate of the centroid or one coordinate of the minimal bounding rectangle. Since It Is more useful to know a bound on the extent of a polygon than to know where the polygon Is centred, It Is preferable to sort by the l a t t e r . A f i l e sequenced by minimum x values Is shown l n F i g . 4.22 a. Note that ordering only conveys Information about the location of the polygons In the x-dlrectlon. For Instance, polygon B Is closer to A than E or F are; yet, ln the f i l e , E and F are closer to A than B Is. Figure 4.22 Polygons from the same map ordered in several ways in sequential f i l e s . (The l e t t e r s uniquely i d e n t i f y polygons and the numbers give t h e i r sequence). 14$ 4.3.3.3 Grid Ordering In this case, a g r i d Is chosen and each polygon Is assigned to a g r i d square which It Intersects on some basis.^ A l l the polygons within one g r i d square appear together on the sequential f i l e order by minimum % within the g r i d square. Grid squares could be arranged on the f i l e ln a Morton Matrix order as described by Tomlinson (1970, p. 71). (This Morton Matrix order Is useful because It provides a minimum sequential search on a s t a t i s t i c a l basis between any two adjacent areas ln any d i r e c t i o n ) . 4.3.3.4 S t r i p Ordering As shown l n Figure 4 . 2 2 c, a set of horizontal s t r i p s which covers the map Is chosen and then each polygon Is assigned to s t r i p on the basis of Its largest y value. The f i l e i s ordered by s t r i p s from top to bottom and from l e f t to r i g h t (by the smallest x-value of a polygon) within each Individual s t r i p . In e f f e c t , I maxy I mlnyl Is being used as a key for ordering the polygons. S t r i p ordering w i l l be described i n more d e t a i l In the sections to come. 4.3.3.5 A View from Problem  Solving The problem of sequencing polygons in a sequential f i l e can be expressed i n terms of the metaphors of problem solving.^ -'in F i g . 4.6 b, polygons are assigned to g r i d squares on the basis of t h e i r centrolds. ^See, for example,N&llson 1s book (197D for a thorough coverage of problem solving. 141 T y p i c a l l y in problem solving there i s a large problem space (usually represented as a graph) which is to be searched for states s a t i s f y i n g certain c h a r a c t e r i s t i c s (goal states). Rather than searching the space exhaustively, there i s an attempt to d i r e c t the search by the use of i n t u i t i v e l y derived h e u r i s t i c s . In the case at hand, the problem space i s a l l the B-polygons and the goal nodes are those B-polygons which i n t e r -sect a given polygon P. Each B-polygon i s represented as a node in the graph (see Pig. 4.23) and two nodes, 1 and j , are connected i f and only i f one can examine polygon 1 a f t e r polygon j . Since the polygons can be searched in any order the graph i s a complete graph as shown. One-dimensional ordering, g r i d ordering and s t r i p ordering are a l l techniques for "pruning" the graph into a l i s t . In some sense, they are heu r i s t i c s that determine which B-polygon to consider next. 4 . 3 . 4 S t r i p Sort in More D e t a i l 4.3.4.1 Algorithm for S t r i p  Sorting a F i l e There are two inputs : 1) a f i l e FI of polygons to sort. (For each polygon we know maxy and minx a s part of the dimen-sioning information); 2) a l i s t of y-values which determine the s t r i p boundaries. There are three steps to s t r i p sorting f i l e FI: SI. Read the f i l e FI, sequentially. For each polygon determine the s t r i p number from the l i s t of y-values and then write t h i s number and the polygon into f i l e F2. 142 5.2. Sort f i l e F2 into f i l e F3 in ascending order by the s t r i p number and miny. 5.3. Read the f i l e F3 sequentially. Assign each polygon a number that i s in sequence, and write i t into f i l e F4. Stop on reaching end of f i l e F3. A STBIPSORT command for performing these steps has been designed but not yet implemented. 4.3.4.2 Intersecting Two S t r i p Sorted F i l e s This section w i l l describe two d i f f e r e n t methods for Intersecting f l i e s A and B that take advantage of the fact that A and B have been s t r i p sorted. Both methods lead to memory savings by intersecting the f l i e s one s t r i p at a time instead of one map at a time. In the examples to follow polygons from f i l e s A and B are l a b e l l e d A^, A 2, ....and B^, B 2, ....respectively where the subscript denotes the s t r i p sorted order of the polygon. Defi n i t i o n s t A polygon i s said to be in a s t r i p i f Its maximum y value i s in the s t r i p . During overlay, a polygon from f i l e A i s said to be fi n i s h e d i f a l l possible intersections of l t with polygons from f i l e B have been found. During overlay, a polygon P i s said to be covered i f i t has produced polygons of intersections whose union make up P. 143 Figure 4.25 Sequencing polygons In a sequential f i l e as ex-pressed in a problem solving context. Polygon Ai i s f i n i s h e d when i t has been intersected with B i and B 2; however, i t i s not covered. Polygon A 2 i s covered and f i n i s h e d when i t has been intersected with B 2 and By The f i r s t method Is to intersect a l l the sections of polygons from the two f i l e s that are ln the current s t r i p , hence f i n i s h i n g that s t r i p ln one blow. As shown ln Figure 4.24, th i s requires intersecting a l l the polygons that are In the s t r i p and polygons from previous s t r i p s that have not been fi n i s h e d with the s t r i p boundary P^ P 2 P3 P^» Then the two sets of polygons of inters e c t i o n are Intersected, f i n i s h e d , and freed. However, the shaded polygons must be saved f o r processing in the next s t r i p , and a complement routine Is required. Thus, we decided against using th i s method. The method actually used by GIDS Is si m i l a r to t h i s l n that polygons are intersected one s t r i p at a time from top to bottom of the map, but there are no intersections with the s t r i p s themselves. One s t r i p of polygons Is read Into core where i t i s stored in a doubly linked l i s t structure (the B-11st; then one A-polygon In the same s t r i p Is Intersected 145 with a l l polygons in the l i s t . If t h i s A-polygon i s not covered and extends into the next B-s t r i p i t i s saved i n another l i s t (the A - l i s t ) . After reading the l a s t A-polygon in the s t r i p a l l the B-polygons in that s t r i p which are f i n i s h e d , or which do not extend into the next A - s t r i p , are freed. Then the next lower s t r i p i s read in and the process i s repeated. This may be a s t r i p of A-polygons or B-polygons as w i l l be explained l a t e r . Figure 4.24 Intersecting polygons with the s t r i p , and then intersecting two s t r i p s of polygons. A l l polygons are stored in one of three doubly linked l i s t s of i d e n t i c a l structure: the A - l i s t , B - l i s t and C - l i s t . The A - l i s t and B - l i s t consist of unfinished A and B polygons respectively and the C - l i s t consists of polygons of i n t e r -section that have not yet been written into the intersection f i l e . Each of these l i s t s are arranged in order by ascending values of minimum x of the polygons. 14$ TAKE THE FIRST B-POLYGON IS ITS AXX MINX OF P> IS ITS MINX ,MAXX OF P JL DOES ITS' tECTANGLE ^INTERSECT "S RECT./  T INTERSECT THE POLYGONS & INSERT POLYGONS IN THE C-LTST I IS P : COVERED? ANY MORE POLYGONS \ j « £ _ IN THE B-LIST? MARK P AS UNFINISHED TAKE THE tfEXT 3-POLYGON \ 1 YES MARK P AS J FINISHED ->( RETURN Figure 4.2<£ The method used by the INTSL routine to intersect a polygon P with a s t r i p of polygons stored l n the B - l i s t . 14? One of the most important of the intersection routines i s INTSL which intersects the contents of the A - l i s t and B-l i s t and stores the r e s u l t i n g polygons of inter s e c t i o n on the C - l i s t . This routine makes good use of the information that the f i l e i s s t r i p sorted and that the l i s t s are ordered by minimum x (see how in F i g . 4.25). As shown in F i g . 4.26, the s t r i p boundaries of A and B do not necessarily coincide. In such cases, how do we choose which s t r i p to read in next? We read in and store the s t r i p 1 whose bottom boundary i s higher, and pass the other s t r i p J by i t because there i s a greater chance of f i n i s h i n g the polygons i n j by intersecting them with polygons In i than vice versa. F i l e A S t r i p Sorted F i l e B S t r i p Sorted The A - l i s t a f t e r reading in s t r i p SA^ Figure 4.26 Two s t r i p sorted maps, and a t y p i c a l A - l i s t . -148 For example, the stages In intersecting f i l e s A and B that are s t r i p sorted as shown in F i g . 4.2& are given below. Upon completing a s t r i p unfinished polygons are kept on the l i s t only i f they extend into the next s t r i p of the other f i l e . Stage (1) Bead the polygons from s t r i p SA^ and store them in the A - l l s t ; pass the polygons of s t r i p SB± by the A - l i s t and store unfinished B-polygons, i n the B - l i s t . Stage (2) Pass the polygons of s t r i p SB2 by the A - l i s t and store unfinished B-polygons in the B - l i s t . Stage (3) Read the polygons from s t r i p SA 2 and store them in the A - l i s t and store unfinished B-polygons in the B - l i s t . Stage (4) Pass the polygons of s t r i p SBij. by the A - l i s t and store unfinished polygons in the B - l i s t . 4.3.5 The Current State of the Intersection Subsystem A l l the routines for intersecting two s t r i p sorted f i l e s as described in the previous section have been written, but have not yet been completely debugged. U n t i l s t r i p s o r t i n g i s working, our approach i s to treat each map as a single s t r i p ; using t h i s technique we have successfully i n t e r -7 sected a few f i l e s . ' However, one important step in future work on GIDS w i l l d e f i n i t e l y be to perfect the Intersection subsystem so that i t can assume i t s r i g h t f u l place in over-laying data polygonal data f i l e s . *«*#«»* ?Cost s t a t i s t i c s for these runs are included i n Chapter 5. 149 CHAPTER 5 CRITIQUE OF GIDS This chapter presents a c r i t i c a l view of the GIDS design and Its implementation to date. The system at present Is developed to about half i t s p o t e n t i a l . The next chapter describes d i r e c t i o n s this development may follow. The implementation Is on the whole a success. Except f o r overlay, a basic system has been running reasonably smoothly since the f a l l of 1972 performing most of the impor-tant functions required of a geographic Information system. The "proof of the pudding" Is that various organizations have been using I t , and supporting Its development f i n a n c i a l l y , and plan to continue to do so. To the best knowledge of the author, there Is nowhere else a system which performs a l l the same functions i n t e r a c t i v e l y . However, th i s Is not to say that other geographic Information systems are not superior l n other ways. One way to evaluate GIDS Is to observe how well It s a t i s f i e s the design c r i t e r i a l a i d down in Chapter 2. Clearly, the system s a t i s f i e s the c r i t e r i a of emphasizing graphical output, being usable i n t e r a c t i v e l y or ln batch, and being problem Independent. As f o r being e a s i l y extendible, new commands can be added at any time by following a sequence of steps shown i n Section 3.4. The question of ease of use Is completely r e l a t i v e . GIDS Is much easier to use than 150 Map/Model where one has to contend with PL/I, JCL, and recom-p l l a t l o n s . However, the user of GIDS must have some fami-l i a r i t y with the MTS operating system and must know the MTS f i l e names of his disk data f l i e s . The author contends that an I n t e l l i g e n t user could learn the fundamentals of the f i l e structures and command languages i n an hour. 5.1 STRONG FEATURES OF DESIGN Perhaps the strongest parts of GIDS are i t s basic approach to geographic data described in Chapter 2 and i t s foundation elements described in Chapter 3. The approach of encoding geographic data by points, l i n e s , or polygons over which some at t r i b u t e i s homogeneous, enables a user to maintain the Integrity of in d i v i d u a l coverages, and yet to r e l a t e d i f f e r e n t coverages together. Secondly, the GIDS f i l e struc-tures provide e f f i c i e n t and elegant storage of both l o c a t i o n a l and descriptive data. T h i r d l y , the command language with i t s sel e c t i o n c a p a b i l i t i e s enables a user to e a s i l y specify a great variety of subsets of these f i l e s f or processing. These few components are the bases of a system which i s both easy to use and easy to evolve. Within the various subsystems of GIDS described i n Chapter 4 there are two elements of GIDS that are p a r t i c u l a r l y noteworthy. These are device-independent graphics which f a c i l i t a t e s obtaining graphs on several devices, and s t r i p 151 sorti n g which speeds up the process of r e l a t i n g across f i l e boundaries polygons which occupy the same location. 5.2 WEAKNESSES OF DESIGN The weakest l i n k of the system i s the input sub-system. Since a l l polygons, must be d i g i t i z e d i n d i v i d u a l l y , each l i n e must be traced twice, often withaanotlceable difference ln the two d i g i t i z a t i o n s of the same l i n e . Editing of these discrepancies Is a d i f f i c u l t manual process. Another shortcoming of GIDS Input Is the i n a b i l i t y to match l i n e s across map boundaries. In short, the Input process Is quite expensive and time-consuming without being very accurate. An Investigation Into Ray Boyle's interactive d i g i t i z a t i o n (1970) and David Douglas' once only d i g i t i z a t i o n (1972) i s required, followed by a comprehensive reworking of the input subsystem. A minor weakness of the system Is that It does not support some version of indexed f i l e structure. In cases where one p a r t i c u l a r a t t r i b u t e Is to be used consistently as a key for a f i l e of s i g n i f i c a n t s i z e , there i s no doubt that an indexed f i l e would lead to cheaper r e t r i e v a l than the sequential f i l e . There are other parts of the system which suffer not from weakness of design of, but rather from weakness of emphasis. These are parts of the system which are r e l a t i v e l y weak, but which could be Improved without any fundamental 152 changes to GIDS. Some of these are l i s t e d below. 1. Update c a p a b i l i t y for GIDS sequential f i l e s . 2. User-defined symbolism and shading as mentioned in Section 4.3. 3. Report generation of data in GIDS f i l e s (e.g. sorted tables of frequency counts or sums for the attributes i n a GIDS f i l e ) . 5.3 COST TO USE GIDS Costs to use GIDS are incurred at two d i s t i n c t points in time: f i r s t in preparing the maps and inputing them to f i l e s under the system, and secondly in displaying and mani-pulating these f i l e s . The former cost can be estimated from the experience of the Greater Vancouver Regional D i s t r i c t Planning Department. To input and edi t a set of sixteen land use maps of about 400 polygons each, they had to invest about $10,000 as shown below. D i g i t i z e r operator - | 600 D i g i t i z e r r e n t a l @ #20/hour - 2,400 Edi t i n g @ 2.50/hour - 5,600 Computer p l o t t i n g @ $20.hour - 500 Other computing - 500 Total - $9.600 The costs to use GIDS for data manipulation can be extracted from the sample sessions of Appendix C. The CPU times to perform various operations on a land use f i l e of 377 polygons were as follows: 1. 40 seconds f o r INPUT 2. 17 seconds f o r PLOT 3. 15 seconds f o r INITIALIZE 4. 12 seconds for DRAW 5. 5 seconds f o r COPY 153 Note that although DRAW i s performing a more sophis-t i c a t e d operation than PLOT, i t i s s t i l l f a ster because of the difference In I/O for f i n a l f i l e s and intermediate f i l e s ; the same Information can be read quicker from a f i n a l f i l e (by the DRAW command) than from an intermeidate f i l e (by the PLOT command). In an attempt to measure how much computer time and elapsed time were required to read GIDS f i l e s of various sizes, we measured the time to l i s t the f i r s t two records of s p l i t f i l e s of various s i z e s . (Note that the whole f i l e must be read In each case because of the way selection works.) The resu l t s are shown in Table IX. TABLE IX THE RESPONSE TIME AND CPU TIME TO BEAD SPLIT PILES OF VARIOUS SIZES AND LIST TWO RECORDS # of poly-gons l n during a busy period during a quiet period the f i l e CPU time elapsed time drum reads CPU time elapsed time drum reads 377 3.5 28 4 13 48 150 2.5 18 228 2 10 32 2 1 12 142 1 8 42 These experiments were conducted both when the computer was quite busy as shown by the large number of drum reads and when It was r e l a t i v e l y Idle. As we expected, the CPU times 15* were comparable In both cases, but the response times were s i g n i f i c a n t l y longer during the busy periods. Response time i s an important measure i f the system i s to be useful i n t e r a c t i v e l y . For Instance, we found that f o r processing the given f i l e of 37? polygons, the response time of 28 seconds achieved during a busy period was uncomfortably long but 13 seconds was quite s a t i s f a c t o r y . Intersection i s the most expensive operation, but i t i s not as expensive as we had o r i g i n a l l y anticipated. To i n t e r s e c t a f i l e of 96 polygons with a subset of 50 polygons from another f i l e producing 136 polygons cost only $6.50 on low p r i o r i t y requiring 2 minutes of CPU time. In a second case 5° seconds were required to intersect the f i r s t 5 poly-gons of a zoning f i l e with the 377 polygon land use f i l e . 5.4 REAL USEFULNESS SO FAR At the Greater Vancouver Regional D i s t r i c t (GVRD) GIDS Is now a household word. According to Peter George, planner, i t Is the most useful information system in the GVRD Planning Department. It i s used frequently f o r p l o t t i n g and superimposing selected portions of maps, and for c a l c u l a t i n g areas. Also i t has l a r g e l y influenced the way information i s being organized; data i s now being gathered as polygonal coverages that can be d i r e c t l y converted to GIDS f i l e s . For the GlfRD planners the most important feature of GIDS i s Its a b i l i t y to maintain the f i d e l i t y of separate data sets, and 155 yet to r e l a t e them together. Because of the d i f f i c u l t y in Inputting data they have not been able to use GIDS for as many maps as they would have l i k e d . However, GIDS w i l l continue to play a very important part in the use of geo-graphical information at the GVRD. GIDS display and selection c a p a b i l i t i e s have been of some value to Peter Doollng of the UBC Department of Forestry for a study of po t e n t i a l recreation s i t e s l n northern B r i t i s h Columbia; however, GIDS has not been able to answer t h e i r more in t e r e s t i n g questions which require knowledge of adjacencies of points. L a s t l y , GIDS has been used as a display t o o l for the output from regional simulation models by the HPS project at UBC. 156 CHAPTER 6 FUTURE DEVELOPMENTS OF GIDS 6.1 INTRODUCTION The system has not yet been developed to i t s f u l l p o t e n t i a l . In t h i s chapter, some new applications of the system at i t s current l e v e l and various extensions such as an abbreviated command language and geographical selection w i l l be discussed (see F i g . 6.1). F i n a l l y , a summary of the system as i t stands at present w i l l be given. USE WITH CENSUS OR ADDRESS DATA CURRENT GIDS SYSTEM USE AS A GRAPHICAL TOOL ABBREVIATED COMMAND SYNTAX ' ."MINICOMPUTER ! • I N P U T S Y S T E M | G E O G R A P H I C A L ] S E L E C T I O N I INCREASING CHANGE FROM CURRENT GIDS Figure 6.1 Possible Extensions to GIDS. 6.2 NEW USES FOR GIDS 6.2.1 With Census and  Address Data Most of the data sets described have been either physical (such as s o l i or land use) or j u r i s d i c t i o n a l (such 157 as municipality boundaries) c h a r a c t e r i s t i c s of the land. However, the realm of applicable data for GIDS i s f a r greater; for Instance, It Includes census data and other data which contain an address as part of each record. Census data has been aggregated to areal units l i k e census tracts and published in tape form. If thi s census data were stored in a descriptive f i l e and the census tract boundaries in a corresponding l o c a t i o n a l f i l e , GIDS could be used as a r e t r i e v a l system for the census data (see F i g . 6.2i|\a). The most common method of coding location for socio-economic data has been by street address, but It i s d i f f i c u l t to r e l a t e this data with data coded by x-y coordinates. However, the past few years has seen the development of geo-coding systems, such as the GRDSR system of S t a t i s t i c s Canada ( 1 9 7 2 ) , which can automatically assign x-y coordinates to street addresses. One of the implications of these geocoding systems Is that street address data has become accessible to s p a t i a l analysis by a system l i k e GIDS (see F i g . 6 .2 b). 6 . 2 . 2 As A Graphical Tool for Regional Simulations In a regional simulation, there i s usually a fix e d set of polygonal study areas over which data i s projected into the future. Each i t e r a t i o n of the model produces a row of output variable f o r each study area. This output i s usually tabular or, i f graphical, then quite primitive. However, GIDS with i t s a f f i n i t y f o r polygonal maps, could be used to produce e x c i t i n g displays from t h i s data. This Is accomplished by 158 GIDS SYSTEM GIDS POLYGON] FILE DIGITIZED CENSUS TRACTS (a) GIDS DESCRIP-TIVE FILE GIDS POINT FILE GIDS DESCRIP TIVE FILE EXTRACTOR PROGRAM / DATA CODED BY COORDINATES-^ STATISTICS CANADA GEOCODING PROGRAMS 7K Address DATA CODED BY ADDRESSES • Data 5"S MAiu ST so, o os 5" Figure 6.2 Inputting census or address data to GIDS 159 s t o r i n g the study area boundaries as a lo c a t i o n a l f i l e ; then, as simulation output was generated, i t i s copied into GIDS descriptive f i l e s to which the f u l l power of GIDS graphics with selection are applied (see F i g . 6.3). PLOT GIDS LOCA-TIONAL FILE GIDS DESCRIPr^ TIVE ""FILE— MAP OF STUDY AREAS SIMU-LATOR Figure 6.3 GIDS as a graphical t o o l for regional simulations. GIDS has already been used in thi s context with the I n t e r - I n s t l t u t i o n a l P o l i c y Simulation (HPS) Project (R o l l i n g , et a l . , 1971). 6.3 EXTENSION-ABBREVIATED COMMANDS Probably the most awkward part of the command language i s the s p e c i f i c a t i o n of f i l e names and the selector. For instance, to draw a l l the polygons from l o c a t i o n a l f i l e L and descriptive f i l e D with a value for the f i e l d of zoning of 10, one must say DRAW (D,L) SCOPE=(ZONING=10) 160 A l l f i l e s to be processed must be referred to by name in every command, even when a whole series of commands process the same f i l e s . However, i f the f i l e names were known to GIDS in advance i t could be s u f f i c i e n t to say DRAW Z0NING=10 It i s recommended that GIDS be extended to support t h i s abbreviated command structure. This could be accomplished by enabling the user to define a f i l e or s p l i t f i l e s as "active f i l e s " to be processed i f no other f i l e s are e x p l i c i t l y men-tioned in a command. One possible command syntax for defining a f i l e as the active f i l e i s "GET f i l e . " The example below shows a command session f i r s t as i t i s now, then as i t could be i f this extension were implemented. Note that the old syntax can s t i l l be used and must s t i l l be used f o r some commands such as COPY. Session A - GIDS In i t s current form DRAW (D,L) SCOPE=(ZONING=10) LIST (D,L) DRAW (D,L) SC0PE=(Z0N1NG=10) CODED BY AREA COPY (D,L) SC0PE=(Z0NING=10) TO (D1,L1) DRAW (D1,L1) DRAW (D1,L1) SC0PE=(Z0NING=15 & AREA >1) LIST L l EMPTY (D1,L1) Session B - GIDS with extension GET (D,L) DRAW Z0NING=10 LIST DRAW Z0NING=10 CODED BY AREA COPY (D,L) SC0PE=(Z0NING=10) TO (D1,L1) GET (D1,L1) DRAW Z0NING=15 & AREA >1 LIST L l EMPTY 161 6.4 GEOGRAPHICAL SELECTION 6.4.1 Theory Geographical s e l e c t i o n i s defined as selection on the basis of geographical c r i t e r i a . (A t y p i c a l example i s sel e c t i o n of those areas from a data f i l e which intersect an inquiry area). It i s an important access method which i s noticeably lacking in GIDS and which should be incorporated l n future versions of the system. Some theory i s presented and then an implementation i s suggested. Geographic selection i s sp e c i f i e d by a selection c r i t e r i o n and an inquiry area. The Inquiry areQ»I, i s defined by a set of points, l i n e s , or polygons. A few sample geographic selectors are l i s t e d below and i l l u s t r a t e d i n Figure 6.4. Select a l l l o c a t i o n a l records from a data f i l e which (a) have a non-empty Intersection with I; (b) are t o t a l l y contained in I; (c) are t o t a l l y exclusive from I; (d) are within distance r of I. 6.4.2 Implementation Geographical selection should be Implemented within the I/O routines so i t i s transparent to a l l processing routines (see F i g . 3.-$). Since i t i s cheaper to evaluate l o g i c a l expressions of the form " i s the land use=3w than to check i f two polygons i n t e r s e c t , numerical selection should be applied before geographical sele c t i o n . 162 FIGURE 6& Regions Selected from a Data F i l e by Different Selection C r i t e r i a . 163 The geographic selector routine must be passed the current polygon, the inquiry area, and the r e l a t i o n . It returns "true" i f the record i s to be selected and " f a l s e H otherwise. Some of the elements required for the implementation of geographical s e l e c t i o n are; 1) a method of defining, storing, and manipulating inquiry areas; 2) a mechanism fo r specifying geographic selection i n the command language. These inquiry areas could be stored either on disk as GIDS l o c a t i o n a l f i l e s or i n core i n a new data structure referenced by name through a directory. Let us assume the former. One should be able to create an inquiry area i n three ways t 1) by copying a selected portion of a GIDS f i l e (with the COPY command); 2) by inputing the coordinates from the source stream; 3) by using the l i g h t pen. I t i s not clear how to best specify geographic selection ln the command language. Suggestions are given for defining i t g l o b a l l y or l o c a l l y for each f i l e . To define i t g l o b a l l y , one might say SET WINDOW= ^geographic selector> where ^geographic selector> <bperator) <inquiry areq> <bperator> »i=INTERSECT/IN/OUTSIDE/WITHIN r <lnquiry area); » Mr <set of points, l i n e s or polygons^ 164 To define the geographic selector l o c a l l y to one f i l e l t could be included as part of the f i l e name i n the same way that the numeric selector was. Recall in Section 3§2 that a " q u a l i f i e d f i l e " ( q f l l e ) was defined as a GIDS f i l e o ptionally q u a l i f i e d by a numeric selector. Now we could define a "geographically q u a l i f i e d f i l e " as a " q u a l i f i e d f i l e " optionally q u a l i f i e d by a geographical selector. (geographically q u a l i f i e d f i l e > »t= <qfile> |<qfile) (geographic selector^ For example, i f BURNABY i s a l o c a t l o n a l f i l e containing the outline of the municipality of Burnaby, and i f ' . f i l e S ^  (ZONING;B,ZONINGfG) contain zoning information for Burnaby and the surrounding area* If we wanted to draw only those parts of the zoning map,flying within Burnaby, we could specify t h i s in two ways t 1) with a global window SET WINDOW=INTERSECT BURNABY DRAW (ZONING.R,ZONING.G) 2) without a global window DRAW (ZONING.R,ZONING.G) INTERSECT BURNABY We could also combine numeric and geographic s e l e c t i o n as shown in the example below. DRAW (ZONING.R,ZONING.G) SC0PE=(Z0NING=10) INTERSECT BURNABY 165 6.5 SUMMARY In the past, the emphasis lw geographical information systems has ) been on computational power rather than on ease of use. The r e s u l t i s that the o v e r a l l l e v e l of hardware and software technology far exceeds the l e v e l of information use. Now we must bring up the l e v e l of system use. To accomplish t h i s end system designers should concentrate on making the i r systems more user-oriented. The goal should be not the development of new techniques, but the synthesis of the old techniques in a manner that makes the data and computational powers more r e a d i l y accessible to the decision-maker. There are several elements present in GIDS which enable us to claim that our system Is one step on the path towards the more useable systems of the future t 1 . There are two simple v i r t u a l views of the data base, one f o r the user and one f o r the programmer. 2. The system can be used i n t e r a c t i v e l y . 3. Requests are expressed in a simple command language. 4. The system i s problem-independent. (It can be applied to any 2-dimensional data and associated a t t r i b u t e s ) . 5. The system is r e a d i l y evolvable. 6. The user can r e f e r to his data Items by names he chooses himself. 166 BIBLIOGRAPHY Aldred, B.K. "Point in Polygon Algorithms," unpublished paper. IBM S c i e n t i f i c Centre, Neville Road, Peterlee, County Durham, U.K., 1972. Arms, S. "Map/Model System—Technical Concepts and Program Descriptions," unpublished document. Columbia Region Association of Governments, Portland, Oregon, 1968. Arms, S. "Map/Model System—System Description and User's Guide," presented at the Puget Sound Governmental Conference, Euguene, Oregon, Bureau of Governmental Research and Service, 1970. Barron, D.W. Recursive Techniques in Programming. American Els e v i e r Publishing Company, Inc., New York, I968. ^oettner, D.W. "Command (Job control) languages for general purpose computing systems," unpublished paper. University of Michigan Computing Centre, I969. Boyle, A.R. "Automation in Hydrographic Charting." The  Canadian Surveyor. Vol. 24, No. 5, (Dec. 1970), PP. 519-537. Boyle, A.R. "Preliminary User's Notes on Interactive Display System f o r Manipulation of Cartographic Data." University of Saskatchewan, E l e c t r i c a l Engineering Department, Saskatoon, 1972. Clement, A. "Report on INTURMAP—An Interactive Urban Mapping System," unpublished document; Department of Computer Science, University of B r i t i s h Columbia, 1973. Conway, R.L., Maxwell, W.L., Morgan, H.L. " F i l e Processing with ASAP—An Introduction." Department of Computer Scienoe, Cornell University, Ithaoa, New York, 1971* PP. 3-7. Coulthard, W.J. "MTS Commands," unpublished report. Computing Centre, University of B r i t i s h Columbia, 1970. Dangermond, J. "Polygon Information Overlay System," unpub-lis h e d report. Comprehensive Planning Organization, San Diego, C a l i f o r n i a , 1971. Deecker, G.F.P. Interactive Graphics and a Planning Problem., M.Sc. Thesis. Department of Computing Science, University of Alberta, Edmonton, 1970. 167 Deecker, G.F.P., Penny, J.P. "On Interactive Map Storage and Ret r i e v a l . " INFOR, Vol. 1 0 , No. 1 (Feb. 1972), pp. 62-74. Denenberg, S., Corbin, C , Alsberg, P. "NARIS, A Natural Resource Information System." Centre f o r Advanced Computation, University of I l l i n o i s at Urban Champaign, Urbana, I l l i n o i s , 61801. Douglas, D. "BNDRYNET," unpublished paper. Department of Geography, Simon Fraser University, 1973. Dueker, K.J. "Spatial Data Systems: Organization of Spa t i a l Data." Technical Report No. 4, Department of Geography, Northwestern University, A D 6 5 2 0 0 5 , Clearing House for Federal Domaments, S p r i n g f i e l d , VA., 22151, 1966. Environment, Canada. "Canada Geographic Information System," unpublished report. Lands Directorate, Lands Forest and W i l d l i f e Service, Environment Canada, Ottawa,1972. Fisher, H.T. Mapping Quantitative Information. Laboratory for Computer Graphics and Spa t i a l Analysis, The Graduate School of Design, Harvard University, 1970. F r a n k l i n , W.R. "The ANOTB Program," unpublished document. Computing Centre, University of Ottawa, 1972. Goodchlld, M.F. "A Positi o n Paper on Geographic Data Pro-cessing," unpublished paper. Department of Geography, University of Western Ontario, 1972. George, P. "HPS Land C l a s s i f i c a t i o n Subgroup Report," unpublished report. Resource Science Centre, University of B r i t i s h Columbia, 1972. Harvard University. "SYMAP V Operator*s Manual." Laboratory fo r Computer Graphics and Sp a t i a l Analysis, Cambridge, Mass., 1968. H o l l l n g , C.S., Goldberg, M.A., K e l l y , R. "Vancouver regional simulation study 1970-1971," unpublished paper. Resource Science Centre, University of B r i t i s h Columbia, 1971. Kenney, J.F., Clapp, G.D. "Natural Resource Information System (NRIS)—Overall Description." Boeing Computer Services, Inc., Seattle, Washington, 1972. Leong, E., Ng, R., Lau, W., Yau, S. "The Report Generating System of GIDS," unpublished report. Department of Computer Science, University of B r i t i s h Columbia, 1972. 168 MacLeod, M.H. "Semi-Automated Large Scale Mapping," presented at the XII Congress of the International Society of Phot©grammetry, Ottawa, 1972. McRae, R.N. A Supervisor to Monitor Multiple Simulators. M.Sc. Thesis, Department of Computer Science, University of B r i t i s h Columbia, 1972. Nilsson, N.J. Problem Solving Methods In A r t i f i c i a l I n t e l l i -gence. McGraw-Hill, Inc., New York, 1971. Nake, F., Peucker, W, "Progress Report After Year One—The Interactive Map in Urban Research," unpublished paper. Department of Computer Science, University of B r i t i s h Columbia, 1972. Parker, J.L. "Information R e t r i e v a l with Large-Scale Geographic Data Bases," unpublished paper. Resource Science Centre, University of B r i t i s h Columbia, 1971. Parker, J.L. "The Scanner—A System f o r Processing Command Languages i n User-Oriented Systems," unpublished document. Department of Computer Science, University of B r i t i s h Columbia, 1971. Parker, J.L! "A graphics and information r e t r i e v a l supervisor f o r simulators," AFIPS, Vol. 40, 1972 (Spring Joint Computer Conference). Peucker, T.K. "Computer Cartography." Resource Paper Noi 17. Commission on College Geography, Washington, D.C., 1972. Rapp, M.H., Goldman, M., Smallwood, R. "The Interactive Graphic Transit Simulator, A Tool for Planning Node-Oriented Transit Systems." Research Report No. 7» Urban Trans-portation Program, Department of Urban Planning and C i v i l Engineering, University of Washington, Seattle, 1971. Robinson, A.H., Sale, R.D. Elements of Cartography. John Wiley and Sons Inc., New York, 1969. Schmidt, W. "The AUTOMAP System." Surveying and Mapping. Vol. 29, No. 1, 1969. S t a t i s t i c s Canada. "GRDSR, An Introduction," unpublished paper. S t a t i s t i c s Canada, Methodology and Systems Branch, Ottawa, 1972. Tautz, A., Belford, D. "Editing Procedures for GIDS Data," unpublished document. Greater Vancouver Regional D i s t r i c t Planning Department, Vancouver, 1972. 169 Tomlinson, R.F. "An Introduction to the Geo-Information System of the Canada Land Inventory," unpublished paper. Department of Forestry and Rural Development, Ottawa, 1967. Tomlinson, R.F., (ed.). Environment Information Systems. The Proceedings of the UNESCO/IGU F i r s t Symposium on Geographical Information Systems, Ottawa, 1970. (A publication of the IGU Commission on Geographical Data Sensing and Processing, Ottawa). Tomlinson, R.F., (ed.). Geographical Data Handling. A publica-t i o n of the International Geographical Union Commission on Geographical Data Sensing and Processing, Ottawa, 1972. Troyer, D. "The Intersection of Polygons," unpublished report. Department of Computer Science, University of B r i t i s h Columbia, 1972. United States Department of Housing a Urban Development. Urban  and Regional Information Systernst Support f o r Planning  ln Metropolitan Areas. Washington, 1968. VandenBosch, P. "An Interactive Picture E d i t o r — A Subsystem of the Geographical Information and Display System," unpublished document. Department of Computer Science, University of B r i t i s h Columbia, 1972. Walters, H.W. "Map Modeling—Geographic Data Handling at Land Council of Governments, Eugene, Oregon," presented at the P a c i f i c Northwest National Recreation Parks Associa-t i o n Conference, Vancouver, May 1972. Waugh, T.C., Thomas, A.L. "Geographic Information Manipulation and Mapping System (GIMMS), a system d e s c r i p t i o n , " unpublished report. Department of Geography, Edinburgh University, Edinburgh, Sootland. Witluk, S.W. "SGIDS—A Simple Geographical Information Display System," extended essay, Department of Geography, Simon Fraser University, 1973. Wlttlck, R.I. "The Geography Program Exchange." Computer Institute f o r Social Science Research, Michigan State University, East Lansing, Mich., 1973. Yan, J.Z. "The Command Manual for GIDS," unpublished document. Resource Science Centre, University of B r i t i s h Columbia, 1972. **«*««« 170 APPENDIX A. SUMMARY OF THE COMMAND LANGUAGE The following description gives a b r i e f outline of the GIDS command language. The text i n upper case represents words which must appear without change. The text i n lower case within quotes i s to be replaced by the appropriate variable by the user. The text within square brackets i s optional. The text within round brackets denotes alternative forms of a parameter. Underlined text i s either an abbrevia-t i o n of a command or the default value of a parameter. Com-mands that are marked with a plus sign query the user for add i t i o n a l information. The following types of f i l e s are referred to i n the command syntaxt • d f i l e * - contains the d i g i t i z e d data • i f l i e ' - contains the data in intermediate form, used f o r e d i t i n g • f i l e ' - GIDS f i n a l f i l e ( descriptive, l o c a t i o n a l , s p l i t , or merged) without a selector • q f i l e * - GIDS f i n a l f i l e perhaps q u a l i f i e d by a selector + AGGREGATE • q f i l e * [TO] 'row f i l e 1 The selected portion of a f i l e i s aggregated according to user s p e c i f i c a t i o n s and the r e s u l t i s written into a row f i l e . COMMENT 'any information* A mechanism for entering a comment. 171 COPY • q f l l e 1 [TO] • q f l l e 1 The selected portion of a f i l e Is copied to another f i l e . •CREATE •flle» [ L I K E 'file]] [KIND=(ROW/SPLIT/ GEO/MERGED)j (SIZE** Integer]] [TYPE=(SEQ/LINE/SEQWLJ A f i n a l f i l e Is created and fieldnames and other header Information are written into I t . *DRAW • q f l l e * [jmarked* BY •fleldnamej (ON •graphic device]] [PAPER*(BLANK/GRAPH]] [SCALE*• p o s i t i v e no.'] The selected portion of the f i l e Is drawn on the speolfied device with the specified symbolism. EMPTY ' f i l e * The data, i n the f i l e Is emptied, but the headers are not. EXECUTE •mts program f i l e 1 f'l/oassignments^] (PAR**execution parameters 1 J Runs some programs under MTS without unloading GIDS. • I N I T I A L I Z E ' f i l e ' [TO] ' q f l l e * The Intermediate f i l e i s input, converted to a user-s p e c i f i e d coordinate system; the dimensioning Is calculated, and the r e s u l t i n g data Is written out Into the f i n a l f i l e . •INPUT ' d f l l e ' [TO] 'If He' MENU*•menuflie*[pEL=»real no. *J JTOL='real no.^| [CENTROIDS=fcNQWN/UNKNOWN)j [TYPE*(POLYGON/LINE/DOTT) The d i g i t i z e d data i s read l n , edited s l i g h t l y , r e -formatted, and written out into an intermediate f i l e . The descriptive data i s decoded v i a the menu l n 'menuflle'. INTERSECT ' q f l l e ' [WITH] ' q f l l e ' (AND STORE IN| ' q f l l e ' The selected portions of two f l i e s are overlaid; the r e s u l t i n g polygons of Intersections are written Into the th i r d l o c a t i o n a l f i l e , and the r e s u l t i n g concatenated at t r i b u t e s are written into the t h i r d d e s c r i p t i v e f i l e . 172 LIST • q f i l e 1 [ON 'mts f i l e or device*] The selected portion of the f i l e i s l i s t e d on the spe c i f i e d device. MTS This command returns a user to MTS, during which a ^RESTART returns him to GIDS. PLOT ' i f l i e ' [SCALE= treal no. •] [CODE^ integer 1] j(AXIS/NOAXISJj ON •graphic device* PAPER=(BLANK/GRAPH} The intermediate f i l e Is plotted, so that the data can be edited. SET (AREA_PRINTING=(ON/OFF) / SCALING=(DEVICE/•positive no.') /COMMANDJTITLING=(ON/OFF) / CHARACTER^jSIZEs1 p o s i t i v e no. • /SYMBOL^SIZE^positive no. 1 / DOUBLETSHADING=(ON/OFF)) This command allows the user to control various options of the DRAW or SUPERIMPOSE Commands. SIGNOFF This command w i l l submit any graphs for p l o t t i n g and then sign a user off the computer. STOP Any pending graphs are submitted for p l o t t i n g , and then the GIDS run lssterminated. •^ -SUMMARIZE • q f i l e 1 JOM •mts f i l e or device 1] The selected portion of a f i l e i s aggregated and the re s u l t s are printed as a report on the sp e c i f i e d f i l e or device. ^SUPERIMPOSE ' q f i l e ' ["'marked BY 'fieldname] [JON 'graphic device [PAPER=(BLANK/GRAPH^ The selected portion of the f i l e i s drawn superimposed on tops of previous graphs on the device with the spe c i f i e d symbolism. 173 * •marked' may be replaced by any of the following* CODED, TRAINGLED, SQUARED, CIRCLED, SYMBOLLED, SHADED, TRIANGLED AND CODED, SQUARED AND CODED, CIRCLED AND CODED, SYMBOLLED AND CODED, SHADED AND CODED, TRIANGLED AND SHADED, SQUARED AND SHADED, CIRCLED AND SHADED, SYMBOLLED AND SHADED. •graphic device' may be replaced by any of the following: ADAGE, CALCOMP, LARGE CALCOMP, SYN1, SYN4, SYN6, 2260, 27^1, TTY, 'mts f i l e ' " B. FIELDNAMES FOR LOCATIONAL FILES Below are the twelve fieldnames associated with any l o c a t i o n a l f i l e , be It polygonal, l i n e , or point data. These are the 12 dimensioning Items described in Section 3.1. (Fields #5 through #8 specify the minimum bounding rectangle). 1. STRIPSORTNO.S unique polygon number 2. NOCOORDS 3. XCENTROID 4. XCENTROID 5. MINX 6. MINY 7. MAXX 8. MAXY 9 . AREA 10. STRIPNO 11. POLYGONNO 12. MAPNO to t a l number of coordinates In the polygon (twice the number of points i n i t ) x-coordlnate of the v i s u a l oentrold y-coordinate of the v i s u a l centroid minimum x-value in the polygon minimum y-value maximum x-value maximum y-value area for polygon, length f o r l i n e , and zero fo r point data has to do with s t r i p s o r t i n g — c u r r e n t l y t h i s i s always zero user assigned polygon number an I d e n t i f i e r f o r the map from which this record was d i g i t i z e d 174 C. SAMPLE BUNS WITH GRAPHICAL OUTPUT The following computer print-out shows two actual computer runs. The maps produced by these runs are included at the end of the computer text. The f i r s t character on each l i n e Indicates the intention of that l i n e . A l i s t of these p r e f i x characters and the interpretation of the corresponding l i n e i s given below: a user command to GIDS or a response from GIDS ? answer to a question asked by GIDS # a user command to MTS or a response from MTS > a l i n e of a f i l e l i s t e d by MTS 175 SCO 7 ACH: EXA "l.E i ENTER «)S£». 'A'.SJIRO. : I  ? <l * * l f. ST SlONl'l *A5: 14:59:37 i f A O J I , „ L U J ; o „P,f AT IJL-c;u Q3-5R 9U_\uS _3i/T3 : _ 'I SET TO»=ON * TO. 00 CF = 0 a JLIST LANOUSEI 1•>Q1 ^ ' •" > 1 32yC770052-O270KCCC*0277^ 196 + 1712f2186H7IO+OOOO > 2 33 7077 10 11-0=23 +027/,-002° + 0274+0563 + 2093+03 05+2186+ 0891 + 2186+0892 + 21 79* C899+2178 > 3 3J_707_7•) 01 j • 089 8+2195 + 09JJ4 + 2 1 35 + 0902 + 2161 + 08 56 + 2 16 3 + 03 56 + 21 5 3 + 0e 73 +2 1 52 + 0872 + 2_147 > 4 i3 7C7 7(:T)'i'3 + ' c l 6 3"+? l-.4ro'3 67+Ti3'6+"cefc*8+ 2131 i06'74• 212b*~Oi80*2r26To'895 '«-2127"*096b~2i2T > 5 33 707 '0013 +09 10+1 •;09+C33i + 1<;33 + OR80+1956 — > — f — i ^ f ^ o f ^ ^ > 8 3.3 7O77O016 +020 3 +2 1 55 > 0 3 3 7 07 70017-C470 + 0472-00 22+02 73 + 08 3 6+ 1?2<.+0784•194 3 + 0806+1967+0899t_924+ C893 + 1887 > io 3 l7oT7oneVc7s^Y945 > 11 337C770119-0227+0126-0026+0273+0759+1398+0624+1969+0639+2004+0767+1926+0766+1943 > ' 12 3 3 7 07 7Q 02 0 + 0 856+ i 90 3+ C3 57 » 1 3 32+ 0E64 + 1 8 56 » 03 7 5 + 1 84 4 + 0 3 86 +1 8 3 3 +0861 +1 824 + 0798+1824 > 13 33 7C7 70 021 » 07 JI H .n 6+ C7 85 H 3 21 +7JT 7lTlTloTbT6TTinr3T+OT66 + 184 S+T>T5§+lT&9*m'!SV* 18 > 14 33 70770 022 +073 6+1 8 7.3 + 0716 • 1 8 87 + 0689+1 908+06 57+1 93 1 + 06 29 +1 94 7 +0 635+1 955+0632 + 196 3 > 1 5 3 3 7C7 70 024-O52 5+CC71-CO27+O2 68* 0380+ 2 14 5 + 03 73+ 2 1 52+ 0856 + 2 1 53 +08-56 +2 1 63 +0902 +2 161 > 16 3T?OT7:)025»b9OoT2Y2X^^ > 1 7 38 7077O026+Ci"'2+al47+0374 + 2i52+O856+2153 > 18 33 7CT 'O02 7-0326 + 02 2 5- 00 24 + 02 7 9+ 089.5 + 2 1 S3+ OR 92 + 2 1 S 8+ 089 2 + 2 180 + 0899 +2 I 80+ C899 + 2 1S 7 - _ 3l-?O7r)O23+-0-39'2+2ifl7 ' > 2 0 33 7C7 7J 32 9-0 52 3 +CC77-C024+0274 + 0883 + 1975 + 0831+1990+0899 +1990 + 0899fi556+0878+1958 1 END OF FILE S"T^oriT^S = 4T * tCO'l-'ENT -THIS IS THE DIGITIZER FILE. LINE 1 CONTAINS CONTROL INFORMATION 1 T-0,06 CR = 8 il iCF-.MM E T : FROM COLUMN 13 ON "ARE X AMD Y C nTTPTJf rfAlTTS " •I T = 0.05 0°=7 SRU-v GIDS: 1.0 ; --'THE SET COM.'.A'il IS WORKING - SEE GIDS:NEWS FOR DETAILS 0 "PLEASE ENTER CCM4N0 TO GtOS* fj CG^MF.NT: TH+: L A ' D ISS M E N U h A S"""!5^ £ VI Ou S I. Y " h"£ S N " W K l'TTEN~nrNT0~TTiTnnnr£^E^5t! a iais:vAL to c J-MviJ*** 3 *PLFASE F- ITE^ CO'MANO TO GIOS* " V 1 I':.•>•;.• r !\\\>'iSE; ( yENU=?ACH:"ME'iU " •0 ESTF3 SCAL E JF . j , . ) ? 2M0) it w»jt> v6>( a<i c A w a ^ n c K s t hKmryrs-vtrm • ? YES. a WILL T+-ERE M •JEST IMG CF "ClYGC'MS'.' SMHSR YPS OK NO ~~ ? YES " " " • " - -ENTER FILE v\ME -OR M\N!° U L A 7 I C N L" I LE ? -M r~s^5rT-p<r~ir^ 9 TOTAL A--£4 Ci O'lT-'-IT ^R T» W F ' L E « 201.07 T-irat ARE A "••! l\ II •''UL \ r MN FILE-- 118.02 ' ",3 " ""'' PLEAS E" "; 'HER"'cr"J"A*N l" TO "G [OS* ' " ' " "' " 3 *TS 1 T ; 1 ( 1 ( » C P,C O 176 •J. M S " L 6 V V « S ! .'.6 V M S ' Ii •• 32 3 \ G E S 7 = 0 . 0 ? CR = ia K . >'-'-tE\'Y : THE F U S T FEW O Q L V G C N S Or THE I N T E R M E D I A T E F I L E T = 0 . 06 OR=8 ' L I S T L . w n i J S E . 1( 1 , 1 3 1 ' . ' . O J 5 . 3 J 4 0. 6 2 . 7 o 0. 00 0 . 0 . '• •> 2 0 . ° ? 9 . 6 1 63~~ R. 5 6 " 2 1 . 53 24 9 . 0 0 l o . S ° 9^ > 5 . 4 9 2 0 . 2 2 2 . 7 0 0 . 0 ; 1 l _ P T S - > 3 . 7 3 2 1 . 52 8 . 8 1 1 9 . 8 3 5 . 1 1 2 0 . 4 0 . 7 7 21 . 85 1 7 . 1 2 2 1 . . 1 6 1.7, 1 0 0 . 0 2 5 C C 0 . O 0 0 0 . 0 2 0 . 0 2 7 0 7 A U C 3 1 , 1 9 7 3 _ 3 . 0 5 _ _ 2 1 . 8 6 6 . 9 1 2 1 . 8 6 _ 8 . < ? 2 2 1 . 7 9 _ 0 . 7 2 2 i~ .4 7 ' f iT69 ' 2 1 . 4 4 " S.67""2"i'."3 6 8 . 8 0 l . o . 5 6 8 . 9 8 1 9 . 56 8 . 9 9 1 9 . 2 3 4 . 61 2 0 . 7 7 4 . 2 1 2 1 . 14 4 . 1 3 2 1 . 1 4 8 . 9 0 2 1 . 7 8 S . 9 8 2 1 . 8 5 9 . 0 4 2 1 . 8 5 8 . 6 8 2 1 . 3 1 8 . 0 8 1 9 . 6 6 3 . 7 0 2 1 . 4 1 8 . 7 4 2 1 . 2 6 7 . 6 8 1 9 . 2 7 3 . 4 6 2 1 . 5 4 6 . 8 0 2 1 . 2 6 6 . 9 5 2 1 . ; 6 . 3 9 2 0 . 0 4 6 . 2 3 1 9 . " 3 . 0 5 2 1 . 8 6 > _>_ > 9 1 3 11 3 . ' 2 5 8 . 7 5 7 . 5 1 1 . 3 . 7 6 . ""f. 1 8 . 1 sj. 00 0 . 0 36 1 ••>.?. 4 0 0 0 . 0 0 . 3 6 17 P T S - > 7 . 8 4 1 9 . 4 3 S . 0 6 1 9 . 6 7 8 . 9 9 1 9 . 2 4 8 . 9 8 1 8 . 8 7 7 . 8 4 1 9 . 4 5 7 . 8 4 1 9 . 4 3 5 ° 1 .3 .93 1 . 5 2 4 4 3 .3f t 1 8 . 3 8 59 7 ,? ,6 1 8 . 7 3 19 P T S - > 6 , 2 4 1 9 . 6 9 6 . 3 9 2 0 . 0 4 7 . 6 7 1 9 . 2 6 7 . 8 6 1 9 . 4 3 8 . 5 6 1 9 . 0 8 3 . 8 1 1 8 . 2 4 7 . 9 8 1 8 . 2 4 7 . 9 1 1 8 . 1 6 7 . 8 5 1 8 . 2 1 7 . 7 2 1 8 . 3 0 7 . 6 7 1 8 . 3 1 7 . 16 1 6 . 8 7 6 . 8 9 1 9 . 0 8 6 . 5 7 1 9 . 31 6 . 3 9 1 9 . 4 7 6 . 3 5 1 9 . 5 5 6 . 3 2 1 9 . 6 3 8 . 5 7 1 8 . 8 2 8 . 6 4 1 8 . 5 7 . 6 6 1 8 . 4 2 7 . 5 9 1 8 . 1 6 . 2 4 1 9 . 6 9 > 1 2 1 3 1 4 1 5 1 6 1 7 4 . 1 5 8 . 7 4 5 . 5 6 . 3 0 . 3 . 2 1 . 00 0 . 0 80 21 . 4 5 0 . 1 . 3 . _____ _9.6_8 21. . 3 1 CO " 0 . 0 " 9 5 2 1 . 8 3 0 . 0 1 00 0 . 0 24 P T S - > 3 . 6 7 21 . 36 8 . 7 3 2 1 . 52 8 . 5 6 2 1 . 53 8 . 5 6 2 1 . 6 3 9 . 0 2 2 1 . 6 1 9 . 0 0 2 1 . 2 4 8 . 69 2 1 . 4 4 8 . 7 2 2 1 . 4 7 8 . 7 4 21 . 5 2 8 . 5 6 2 1 . 53 8 . 7 3 2 1 . 52 8 . 9 5 2 1 . 2 7 8 . 8 0 2 1 . 2 27 P T S - > 8 , 9 2 2 1 . 8 8 3 . 9 2 21 . 8 0 . 9 9 2 1 . 8 0 8 . 9 9 2 1 . 8 7 8 . 9 2 2 1 . 8 8 T = <>, 1.8 O F F I L E . 6 4 OR=92 8 . 33 1 9 . 7 5 0 . 06 2 9 P 7 S - > 6.6.1 1 9 . 9 0 8 . 9 9 1 9 . 9 0 3 . 9 9 1 9 . 5 6 8 . 7 8 1 9 . 5 8 8 . 81 1 9 . 9 0 IRE: COM ;T»RT * ? L E A S E ENTER. i £ N T : P L O T T H E IN1 MAMO TO G I 0 S « T E R M E D ! A T E F I L E P L C " P L E A S E E N T E R LANOI I .SE . 1 T 3 * P I E » S E E N T E R CC'-1. A C COM MAMO TO G I D S * O0E = 0 S C A l 5 = 2 . 0 MA'-ID TO G I D S " a PL71T IU S Y S T E M , T O T A L PLOT T I M E MINUTES 0 S E C O N D S T= l E X U T 1 0 N T E R M I N A T E D 8 . 3 9 OR =1.1 02 P L O T _ _ 0 P A R = A L l N E D _ C U T ION" B E G I N S P L ->T I N SY S T E M , T O T A L PLOT T I M E C O T l O f J TERMINAT ED 4 Mi M U T E S 3 5 S E C O N D S EKE T = ; S.R! EXE W A ! A . 0 6 O R = 5 3 N W E R R : C O S T CT ! C U T I O M B E G I MS T M.EMORY = 5 . 6 2 P A G E - H O U R , C G S T = S 2 . 7 9 V E M E M O R Y * 5 6 . 5 4 P A G E - M I D , C 0 S T = t l . 3 1 « s E L A P S E D T I M E M IN 34 S E C , C C S T = » 1 . 0 2 C P L ' T I M E U S E 0 = 6 7 . 6 B S E C , C C S T = 1 6 . 5 8 J O T A L C O S T S I N C E S I G'-I0N=___1. 69 S 1 . 4 E X F C U T ' l O I T T S K M IN AT to" T = 0 . 7 9 0 R = 1 3 E N T E R U S E R P A S S W O R D . * * L OS L R U •F X ' — 7 A S T SIC..TV4 WAS:- 1 5 : 0 2 : 0 8 F P. _" ? A C i r _ S l G IE D O M A T - 1 . 6 ; " G U T S ' : " ! . 0 " " IT I T ! 8 E G I N S H E SET COMMAND I S W O R K I N G -1 0 : 1 6 ON FR I AUG 31 / 7 2 ; E E nros:NEwr, F O R D E T A I L S 177 a * P L E A S E E N T E * C O M M A N D TO G I O S * aCPEATE I LANOins.a,tANOUSE.G> 3 YEAR M VMIC- I T H E D A T A IN T H I S F I L E W I L L H E I N V A L I D ? 1 9 8 0 a E'ITF.P. F I E L D N A M E , M P P E R D O W O , L O W E R 8 D U M 0 O N I T S V A L U E S_ ! F T H E F I E L D I S mOUNDSD IM V M.IJE E N T E R O N L Y T H E F I EL D N A M E a I N D I C A T E NO MOIE F I E L D S BY E N T E R I N G *END a FOR E X A M P L E LANDUSE. 0 ICO -a P O P U L A T I O N a' SEMO ? POL'YGONNO ? 1ANOUSE ? L E V E L ? SEMO ••? IS OAT A FPC '1 MOrE THAN 1 MAP TO BE PUT IN THIS F I L E 7 E N T E R YES OR NO 7 M!l a *4A*e F I L E ' L A N D U S E . G ' HAS BEEN CREATED a * * * * * F I L E ' L A N D J S E . R ' HAS B EEM CREATED a ' P L E A S E E N T E t COMMANO TO G I D S * 3 MTS #_ • . D I S P L A Y V S T IE u It V ' S I Z E = 32 "JA GES ? S E T Tnp.=OM u T = 0 . 0 0 DR = 0 <r SRESTART a a ' P L E A S E ENTE3 COMMAND TO G I D S * COMMENT : MOW WE WRITE THE C ATA INTO F I N A L F I L E S a • P L E A S E E N T E * CO"<MAND TO G I D S * a I N I T I A L I Z E L A N D U S E . I TO ( L AM DUSE .P. , LANDUSE . G 1 a ENTER F I L E MAMS - I ITH GLOBAL OFFSETS ? GI.OP/AL a ' P L E A S E E M T E l COMMAND TO G I D S * a " T S T = 1 6 . 5 0 D R = 1 ! 2 8 D I S P L A Y V M S I Z E V M S I Z E = 40 °A GES i T = 0 . 1 8 DR = 41 p c a * PL E AS E ENTEH COMMAND TO G I O S * a EXECUTE KEB'.StCOSr a E X E C U T I O N B E - , IMS a WAIT M E M O R Y * * . * ! ° - \GE-HCURi C d S T = S 1 . 4 3 3 A C T I V E •MFMO^Y=l<5.46 P A O E - M I M , C T S T = « . 0 . 4 5 S E L A P S E D TIM-1 =5 II M 4 1 S E C , C 0 S T = S 0 . 3 9 J ^ C P i ^ T j V E U S £ _ J * 2 6 . 1 _ l _ S E C , j £ - T l ! 2 1 * 2 . '. 3 "tofAL C O S T ' ' S f N C E SIGN )M="'S4.S2 " ' *" " " ~ '"~ a EXECUTION TERMINATED _3 * P L E A S E SMTEt C 0 M ^ N 0 TO GIOS* a C O M M E M T : N)'-J w= T E S T T H E T1VE TO READ 3(50,150. AT® '2 "OLVSONS a ' P L E A S E E N T E * C C K M I M O TO G I O S * a L I S_T (LAMDUsf . R .LA'-iaUSE.G) SC0PF = (_P0LYGCNMn<3! "a'sosi DAY A:~ P ' l l .Y •("= I,' '"'"CiTDE'S " A P . f": "' 4"D~."00"""til 0 ~ "" a S T C . P S T I * 1. <r.nru05 = 77 CENTRA 4 .43 21.48 RECT = 0 . 3 5 1".73 6. 94 22.36 AREA OR LENGTH* 9.61 a »1U«= 0 . *'.•-•> > = 7 J 7 . COORDINATES: a ) .!^ 2 2 .36 >^. • 1 2 2.36 6 • 7 7 22.29 ' 6 . 7 0 2 „ 2 S 6 . 79 22.35 6 . S 4 22.35 6 .32 22.11 6 . 3 6 22.13 6 . T6 6TT3 22.02 . 3 r>.5 2 21.9 7 6 . 4 1 U . 9 4 6 . 4 7 2 1 . F. 6 6 . 4 1 2 1 . 51 6 . 5 4 21 . 7 6 6 . 6 0 2 1 . 7 6 6 . 7 5 21.77 6 . 8 0 2 1 . 7 4 6 . 80 20.30 6 . 61 2 0 . 38 a 6 . 6 1 2 0 . 0 6 6 .'" 1 2 0 . 0 6 6 . 7 9 1 73 5. 1 6 5. <-!> 1 9 . 7 7 4 . 1 9 20.54 4 . 0 3 20.20 3 . 6 5 2 0 . 4 9 3 . 29 20.72 2.91 20 .90 ' i " ••: 0 4 1 '.- 1 ."2 1 ~}„ ? ._. 7T. 6 -~ 1 0 '2! . " 6 4 " " r. •:• r '•1 ' "  T. 2 6 "22. 0 4 " J . :< '22. - 6 ' "' " i ROW DATA: 0 "II. Y»* 2. cnn - S A'". E : 1. 00 0 . 0 a s T R P s r - i * ll.RDS = 12 C E N T SO* 6 , 1 6 1 °» 84 SECT*' 5.64 19.37 6 . 7 9 20 .17 AREA OR L EMGTH= 0 . 3 6 178 3 P O L Y * * 0 . MA»* = 7 0 7 . C 0 0 F . 0 I N A T E S : 3 5 . 6 ' . 1 9 . 9 3 5 . 3 6 2 0 . 17 6 . 7 9 1 9 . 7 ' . " 6 . 7 8 1 9 . 37 5 . 6'- 1 9 . 9 5 5 . 6 ' . 1 9 . 9 3 a ' P L E A S E E N P t H C OK MA NO 10 G I O S * 3 " T S « T = 7 . 7 0 DR = 372 H RE 3 ' P L E A S E E N T E R COMMAND TO G I D S * 3 C R E A T E ( - R . - G ) L IKE ( LAND U S E , R . L A M D U S E . G ) 3 F I L E ! - .^J ._H A S 1SJEN .CREMATED 3 * " * V « * F ' l L E '-f< ' (AS B E E N C R E £T¥D 3 ' ' P L E A S E E N T E l COMMAND TO G I D S * 3 MTS ; * T = 2 . 4 7 0 R = 1 5 9 tt . R E 3 ' P L E A S E E N T t l COMMAND TO G I D S * 3 L I S T ( - R . - G ) 3 * P L EAS E E N T E l COMMAND TO G I D S * 3 MTS  T = 3 . 6 2 DP = 99 RE a ' P L E A S E E N T E R COMMAND TO G I D S * 3 a a C O P Y ( L A N D U S E . <l, L A N D U S E . " . ) S ' l P O L Y G G N N O < ' P L E A S E E N T E J . COMMAND TO G I O S * MTS 1 5 1 ) TO ( - P , , - G ) T = 4 , 7 6 DR=108 RE • P L E A S E E N T E * COMMAND TO G I O S * 3 a a a a L I S T ( - P . . - G ) S C 0 J E ' ( P C L Y G 0 N M Q < 3 ) ROW D A T A : P O L Y « » 1 . C O D E S A R E ! ' 0 . 0 0 S T P . P S T " = 1 . <C0OR0S= 7 2 C E N T R D * 4 , 0 . 0 , 43 2 1 . 48 R E C T = 0 . 3 5 1 9 . 7 3 6 . 84 2 2 . 36 A R E A OR L E N G T H = 9 i 6 1 PDLY-a=- 0 . 0 . 8 5 2 2 . 3 6 6 . 52 2 1 . 9 7 '.lA'3.(.=-70-7. 6 . 7 1 2 2 . 3 6 6 . 4 ? 2 1 . 9 4 C O O R D I N A T E S . : 6 . 7 2 2 2 . 2 9 6 . 4 7 .21.-36 6 . 6 0 2 0 . 0 6 2 . 4 1 2 1 . 2 7 POH D A T A : POL 6 . 7 3 2 0 . 0 6 2 . 0 1 2 1 . 6 4 Y-')= 2 . 5 . 7 9 2 2 , 2 8 6 . 4 j i _ 2 3 . £ ! . _ 6 . 7 9 1"9."7 3 5 V 3 3 207 16 1 . 9 3 2 1 . 6 4 1 . 5 0 21 . 9 1 : 0 0 5 S A R E : 1 . 0 0 0 .0 6 , 7 8 2 2 . 3 5 6 , 6 . 54 21 . 7 6 b. r. . '• : f ! . / 7 4 , 1 .2 6 2 2 . 0 4 0 , 84 22 6 0 21 ! 9 "2 0 85 22 35 6, 76 6, . 5 4 "4", 36 . 82 2 2 , 75 21 , '0 3" 2 0 . 11 6, LL -A? "20~ 3, 36 2 2 . 1 3 6 . 8 0 _ 2 1 . 7 4 6 . 65"" 2 0 . 4 9 "3, 36 2 2 . 0 3 80 2 0 . 3 9 2 9 ' 2 0 , 7 2 6 . 53 6 . 61 2"."9T 2 2 . 0 2 2 0 . 3 8 _ "2"0';"9'0 S f R P S T * * 2 P O L Y i » = 0 . 5 . 6 4 1 9 . 9 3 i C C O R D S = MA3 ' ( - 7 0 7 . 5 . 8 S 2 0 . 1 7 * P L E A S E E MTS T = 2 . 5 4 DR=223 12 CENT ?.D= 6 . 1 6 1 •= COORD I N A T E S : 6 . 7 0 1 9 . 7 4 _ 6 . J _ 8 • 37 N i i: < C 0 M M AN.) TO G I O S * " , 8 4 P. E O T - 5 . 6 4 1 9 . 3 7 5 . 6 4 1 9 . ° 5 5 . 6 4 1 9 . 9 3 6 . 7 9 207TT AREA OR L E N G T H ' R E * PL E A S E E J L ^ f l Y . J_-R , - Gt ' P L E A S E" E COMMENT : C0-> ' P L E A S E E ITER COMMAND TO G I D S * J f E 3 . COMMAND Y 0>ILY THE F N T E R COMMAND "TO" "GIDS*" " " " IRST 2 P C L Y C O N S TO G I D S * AN JUS E..", N T E l C 1MMA.M0 S C f l P Y ( L A N D U S E 3 ' P L E A S E 3 " T S "« "T'= 5 7 2 9 'OR 2711 " a 0 = _3 ' P L E A S E E N T E < COMMAND T a I 1ST ( - R . - O I 3 ROW CAT A : POL 3 _STCr>sj ra= 1. " a •• Vi V i - - " 0 . " " a 0 . B 5 2 2 . 36 3 6 . 5 2 2 1 . 9 7 ) S ' l P O L Y G O N N O <~5) TO ( - R . ^ f T ) TO G I D S * Y1= 1. : Kn IRHS = M A ) < = 7 0 7 , 6 . / L 2 2 . 3 6 6 . 4 ' M . 9 4 : n - 1 E S AR 4 0 . C 0 0. 0 CENT RO- 4,43 COP.-r ! N A T ? s : 22 . ? o 6 , 79 2;;. :, . 4 7 2 1 , R 6 6 . 4 8 6. 7? 6, 5 R E C T = 22. 3 5 0 . 8 5 1 ° . " 7 3 6 . 8 4 2 2 . 3 6 A R E A 0 0 L E N G T H ' i .84 2 2 . • , 6 0 2 1. = 2 r 2 7 5 21 1 1 77 36 2 ' . 1 3 BO 2 1 . 7 4 b. 36 2 2 . 0 3 j . 80 2 0 . 3 ° 6 . 5 3 6 . 6 1 22.02 20. 38 179 •4 a 6.60 20,06 6.74 20. 06 6.79 19.73 5 .63 2.0. 16 5.<-e 19.77 ',.19 20.54 4.03 20.2 C 3.65 20.49 3.29 20.72 2.91 20.90 3 2. 41 21. 2 7 2.01 21.64 1 .93 21 .64 1 .50 21.91 • 1.26 22.04 0.85 22, 26 3 ROW 1ATA: P0LYS= 2. COOES APE: l.OQ 0.0 . 3 STKPST>i= 2. 'ICJOROS* 12 CENT»D» 6,16 19.84 P.ECT* 5.64 19.37 6.79 20. 17 A P E A OP. L E NG T H = 0.36 3 POLYS* 0 . «*-M= 70 7, COORD I NA TES: J 5ift4_.L2iiL3 5.34 20. 17 6.70 19.7/. 6.78 19.37 5. 64 19.95 5.64 19.93 |  3 'PLEASE ENTER C CM 4 A MO TO GIOS* 3 '-US .I?1*JL?J)R=_IA2. « D I S P L A Y V M S I Z E 'I V M S U E = 4 5 P A G E S 1 T.Q.1Q pp - * RE a ' P L E A S E E N T E R C O M M A N D TO G I O S * 3 C O M M E N T : MOW WE D R A W O N L Y R E S I D E N T I A L P O L Y G O N S A N D S H A D E B Y D E N S I T Y ~a ^CsK^~?"rTf^''CW^H'S~TO~C,TOS* " 3 S E T C H A R A C T S R _ S ! Z E = , 0 7 _2 ' P L E A S E E N T E R C CM MA N D TO G I D S ' ' ; 3 S E T S C A L I M G = 3 . 0 a ' P L E A S E E N T E R C O M M A N D 7 0 G I D S * a .ORAM (LANOUSE.R.LyiOUSE.-;! _S_*( LANOUSE < 4-) S H A D E D BY LA MOUSE. 3 T O T A L A R E A 0.5 L E ' H T H = 7 9 , 2 7 " " ~ 3 * P L E A S E E N T E R COMMAND TO. G I O S * 3 S E T A R E A P R I N T I N G * O F F ~5 *!^LE^rE^TEl"Tci^NT^ : a ^ T S » T = 1 4 . 7 5 D R = 3 3 1 " 3 ' P L E A S E E N T E R C O M M A N D 1 0 G I D S * C - I M M E N T •• OR A J 0 1 R \ S . A M D T H E N S U P E R I M P O S E R E S I D E N T I A L A R E A S L^TATriNTET C O M M A N D To^IOS^- ' S DRAW <LANDUSE,R,LANDUSE.GI S = (LAMDU3E > 69 f. L ANDUS E < 30) COOED AND TRIANGLED B Y LANDUSE I N T = R R |p T AT 6G506B2A 3 A T T E N T I O N IMT=s H R E 3 - ' P L E A S E = N T E R 0 O ' " ' 4 N O TO G I O S * 3 SUP tLANDUSE.R.LV-l-jUSE.-il S=(LANOUSc <3> C0DE6 RY LANDUS6 3 ' P L E A S E E N T E * COMMAND T O G I O S * ? S T O P a P L O T I N S Y S T E M , T O T A L P L O T T I M E 4 M I N U T E S 44 S E C O N D S S E X E C U T I O N T E R M I N A T E D i co * S O U R C E * / s ^ T L ^ " T T r ~ E T m T E T a r r n * s i r . 180 0.0 3.0 6.0 9.0 12.0 15.0 1B.0 Y P Y T S 181 Figure 7.2 Residential land shaded by density. DRAW ( L A N D U S E . R . L A N D U S E .6) S=( LANDUSE < 4) SHADED BY LANDUSI 182 Figure 7 . 3 A map of recreational land (enclosed in t r i a n g l e ) , with r e s i d e n t i a l land superimposed on i t . This was produced by the coTjunands DRAW (LANDUSE.R, LANDUSE.G) S-(LANDUSE > 6 9 & LANDUSE <80) CODED AND TRIANGLED BY LANDUSE SUPERIMPOSE (LANDUSE.R, LANDUSE.G) S=(LANDUSE< 3) SUP (LANDUSE.R.LANDUSE.G) S=(LANDUSE<3) CODED BY Lf 183 D. LEGEND OF LAND USE CODES The land use codes used i n the maps in thi s thesis are summarized below. For a more complete l i s t see "HPS Land C l a s s i f i c a t i o n Subgroup Report" (George, 1972). Interpretation Residential Industrial manufacturing Vaaant land Agriculture, forestry-Transportation, communication Commercial Recreation Institutions Water bodies Single Family-Townhouse, Garden Apartment Apartment T r a i l e r Parks Summer Cottages Urban Vacant Duplex and Conversion St r i p Residential Park Development Parks—Undeveloped Beach Areas Skiing Areas Drive-In Theatres Race Tracks Golf Courses, Driving Ranges and Putting Greens Recreational Campgrounds Miscellaneous and Marinas E. LISTING OF THE COPY COMMAND ROUTINE This l i s t i n g has been included because i t shows how to construct a command out of the foundation elements as explained in Section 3.4. ###*##* Code 1-9 10-39 40 41-49 50-59 60-69 70-79 80-89 90-99 RESIDENTIAL RECREATION 1UT LISTING OF F I L E COPY 05:06 PoMo 0 C T o 05 , 1973 ID=J0EL 1 SUBROUTINE COPY 2 C SYNTAX OF THIS COMMAND: 3 C COPY 'QFILE' (TO) 'QFILE' 4 C 5 C THIS COMMAND ROUTINE SCANS OFF THE 'COPY' COMMAND, 6 C AND CALLS TABSEL TO OPEN THE GIDS FILESo J__ COMMON /SKIN/ j A R (1 32 ) , LOGU.3^ )_»JLJ^G»NpATJJ33_) , ERR , IPOSC 132) , " 8 ~ ~ * LENI132) '"" * " " " " " " 9 C THIS COMMON AREA CCNTAINS THE INFORMATION 10 C RETURNED FROM THE SC ANNERFQR THE COMMAND,  U N=IAR(2)+2 12 1=5 13 IF< LOG( 5)oEQo 8) 1=6 14 C OPEN INPUT F I L E 15 CALL TABSEL(IAR,LOG,IPOS,LEM, I , I EN D, I FI L E , J F ILE , £ 100 ) 16 1=1 END + 1  17 C SKIP OVER BLANKS AND OPTIONAL KEYWORDS 18 5 J = L O G ( D 19 _ IF (_J_o_N E 08 oANDoJoNEo 2) GOTO 10 _ 2 0 1 = 1 +1 21 IF( I oGT.N1 GOTO 200 2? GOTO 5  23 10 I3EG=I 24 C OPEN JUTPUT F I L E S _25 J^AL_L_ TABSEL <I AR_,LOG , IP OS,LEN, I REG , IE N D I F I LEI , J F IL E1, £ 100 j 26 C DO THE COPY 27 CALL C0PY1 ( I F I L E , J F I L E , I F I L E 1,JF ILE3. ) 28 C RETURN TO THE SUPERVISOR ROUTINE  •29 100 RETURN 30 C ERROR - NO TOFILE - PRINT ERROR MESSAGE 31 200 CALL EMSG(200) 32 RETURN 33 END 34 SUBROUTINE C 0 P Y 1 ( I F I L E , J F I L E , I F I L E 1 , J F I L E 1 )  35 C THIS SUBROUTINE COPIES SELECTED RECORDS FROM F I L E ( I F IL E , J F I LE ! 36 C TO ( I F I L E l t J F I L E l ) 37 C 38 C RETURN IF THERE IS NO FILE TO READ 39 IF(IFILEoEQoOoANDcJFILEoEOoO) RETURN 40 C RETLRN IF THERE IS NO FILE TO WRITE  41 I F { I F I L E l o E Q o O o A N D o J F I L E l o E Q o O I RETURN 42 I5ELCT=1 43 C CHECK ON COMPATIBILITY OF FILES 44 C 45 C SET THINGS UP SO NOTHING IS READ IF NOT NEEDED 46 IF; I F I L E l o E Q o O ) IFILE=0  47 I F( J F I L E l o E O o 0) JFILE=0 48 C RETURN IF NO F I L E S HAVE TO BE READ 49 I F(IFILEoEQoOoANDoJF ILEoEQo0) GOTO 206 "50 C rjiTpcirTT^rTrTimr^^ 51 I F ( I F I L E l . N E o O o A N D o I F I L E o E Q . O ) GOTO 206 52 IF( JFILEloNEoOoAMDo JFILEoEQoO) GOTO 206 "53 T COPY IS ACCEPTABLE 54 C READ ONE RECORD USING TREAD 55 10 CALL TREAD(IFILE,XROW,N ROW,J FIL E,C,N C, ISELCT, ICODE,£100,£2 02) 56 C WRITE ONE RECORD USING TWRITE 57 CALL TWRITE(IFILE1,XROW,NROW,JFILE1,C,NC, I SELCT,I C O D E , £ 2 0 4 , £ 2 0 4 58 C FREE THE SPACE OCCUPIED RY THE RECORD I [STING OF F I L E COPY 05:06 P 0M 0 OCT, 05, 1973 ID=JOEL 59 IF!IFILEoMEoO) CALL FS°ACE< XROW) 60 I F ( J F I L E o N E o O ) CALL FSPACE(C) 61 GOTO 10 62 C RETURN ON EOF 63 100 RETURN 64 C ERROR IN READING F I L E 65 202 MESS=202 66 GOTO 500 67 C EFROR IN WRITING FILES 68 204 MESS=204 69 GOTO 500 70 C NOT ENOUGH INPUT TO DO THE COPY 71 206 MESS=206 72 500 CALL EMSG(MESS) 73 RETURN 74 END 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0052000/manifest

Comment

Related Items