DP1.1 - introduction

For the sake of posterity, please cite from the published version:
Kirby, G H, Visvalingam, M and Wade, P (1989) "The recognition and Representation of Polygons with Holes" Computer J, 32 (6), 554 - 562.

CONTENTS

Introduction
Background
Disassociative Area Model (DAM)
3.1 Geometry
3.2 Geography
3.3 Comparison of DAM with predecessors
Deriving the Topology
4.1 Extracting the Boundaries
4.2 Forming the Containment Hierarchy
An application of DAM
5.1 Background to the OS 1:625,000 Data
5.2 Extraction of the Geometric Topology
5.3 Identification of Area Objects
5 .4 Summary of the Project
Conclusion

REFERENCES
FIGURES It is best to open the figures in another browser window, so that you can read the text while studying the figures

1. Introduction

One of the more challenging tasks in the development of Geographic Information Systems (GIS) is the derivation of an appropriate conceptual model for describing area entities. This paper introduces the Disassociative Area Model (DAM) and contrasts it with other existing descriptions of areal entities. Most available systems for spatial data processing require from the outset object-related information, in the form of left/right or on line references or area-seeds, for extracting the area topology.

Conceptually, it is preferable to break down the vector encoding of polygonal areal covers into three distinct stages:
1) the geometry of the linework of the area boundaries is encoded;
2) the topology (or spatial relationships) is determined; and
3) the geography of the areal entities is encoded.

There are several advantages in separating these stages. Firstly, there can be flexibility in the order and the method by which data is supplied to the system if the geometry and the geography are considered separately. Secondly, it is possible to derive the topology by an automatic process, thus minimising the information which has to be input by the user and reducing the possibility of error. Thirdly, the separation of the geometry from the geography enables a data structure to be used which can represent complex relationships between areas (such as overlaps, hierarchies, holes and islands), and also allows several sets of areas to be held in the same database. Fourthly, if the topological description of the geometry is also held within the data structure, it is possible to use this knowledge to perform efficiently spatial operations on areas and data associated with areas; for example, the disaggregation and reassignment of attribute data from one set of areas to another. Finally, and importantly, it is possible to use the computed topology to check for completeness and consistency in the data supplied, and ensure that any rules that exist about how areas are related (such as in a hierarchy) are obeyed in the data.

This paper presents a new model for representing the spatial relationships between polygons. It disassociates the geometric and geographic components of areas for separate academic consideration. Additionally, an automatic method is given for progressing from a node matched set of vectors, which describe the linework of area boundaries, to a complete topological description of the uncut spatial units which can be built from the boundaries. Following a discussion of some existing techniques for representing geographic areas in the next section, Section 3 describes the new model for representing the spatial relationships between polygons, which we have called the Disassociative Area Model (DAM). In Section 4 an algorithm for generating the uncut spatial units and their topology from a set of vectors is described. A description of a supporting data structure is also given. Section 5 will illustrate the utility of the methods developed in this paper by describing how they were applied in a project which was undertaken on behalf of the Ordnance Survey.