A Formal Definition of Binary Topological Relationships
Max Egenhofer Third International Conference on Foundations of Data Organization and Algorithms (FODO), Paris, France,
W. Litwin and H. Schek (eds.), Lecture Notes in Computer Science, Vol. 367, Springer-Verlag, pp. 457-472, June 1989.
Abstract
The exploration of spatial relationships is a multi-disciplinary
effort involving researchers from linguistics, cognitive science,
psychology, geography, cartography, semiology, computer science,
surveying engineering, and mathematics. Terms like close and far or
North and South are not as clearly understood as the standard
relationships between integer numbers. The treatment of
relationships among spatial objects is an essential task in
geographic data processing and CAD/CAM. Spatial query languages,
for example, must offer terms for spatial relationships; spatial
database management systems need algorithms to determine
relationships. Hence, a formal definition of spatial relationships
is necessary to clarify the users' diverse understanding of spatial
relationships and to actually deduce relationships among spatial
objects. Based upon such formalisms, spatial reasoning and
inference will be possible. The topological relationships are a
specific subset of the large variety of spatial relationships. They
are characterized by the property to be preserved under topological
transformations, such as translation, rotation, and scaling. A
model of topological relations is presented which is based upon
fundamental concepts of algebraic topology in combination with set
theory. Binary topological relationships may be defined in terms of
the boundaries and interiors of the two objects to be compared. A
formalism is developed which identifies 16 potential relationships.
Prototypes are shown for the eight relationships that may exist
between two objects of the same dimension embedded in the
corresponding space.
PDF
Max Egenhofer