Research Paper

Abstract

The 4-intersection, a model for the representation of topological relations between two-dimensional objects with connected boundaries and connected interiors, is extended to cover topological relations between two-dimensional objects with arbitrary holes, called regions with holes. Each region with holes is represented by its generalized region—the union of the object and its holes—and the closure of each hole. The topological relation between two regions with holes, A and B, is described by the set of all individual topological relations between (1) A's generalized region and B's generalized region, (2) A's generalized region and each of B's holes, (3) B's generalized region with each of A's holes, and (4) each of A's holes with each of B's holes. As a side product, the same formalism applies to the description of topological relations between 1-spheres. An algorithm is developed that minimizes the number of individual topological relations necessary to describe a configuration completely. This model of representing complex topological relations is suitable for a multi-level treatment of topological relations, at the least detailed level of which the relation between the generalized regions prevails. It is shown how this model applies to the assessment of consistency in multiple representations when, at a coarser level of less detail, regions are generalized by dropping holes.

Notes

† This work was partially supported by the Italian National Council of Research (CNR) under grant No. 92.01574.PF69. Max Egenhofer's work is partially supported by Intergraph Corporation, NSF grant No. IRI-9309230, and the NCGIA under NSF grant No. SES-8810917.

Additional information

Notes on contributors

Max J. Egenhofer‡

‡On a leave of absence from the National Center for Geographic Information and Analysis, Department of Surveying Engineering, and Department of Computer Science, Boardman Hall, University of Maine, Orono. ME 04469–5711, U.S.A.