Qualitative Spatial Reasoning with Cardinal Directions

Informatik-FachberichtePublished 1 January 1991

Andrew U. Frank

Citations210

TL;DR

An algebraic method is used to formalize the meaning of cardinal directions and two examples of systems to determine and reason with cardinal directions are discussed in some detail and results from a prototype are given.

Abstract

Following reviews of previous approaches to spatial reasoning, a completely qualitative method for reasoning about cardinal directions, without recourse to analytical procedures, is introduced and a method is presented for a formal comparison with quantitative formulae. We use an algebraic method to formalize the meaning of cardinal directions. The standard directional symbols (N, S, E, W) are extended with a symbol 0 to denote an undecided case, which greatly increases the power of inference. Two examples of systems to determine and reason with cardinal directions are discussed in some detail and results from a prototype are given. The deduction rules for the coordination of directional symbols are formalized as equations; for inclusion in an expert system they can be coded as a look-up table (given in the text). The conclusions offer some direction for future work.

Keywords

Computer Science

The Philosophical ReviewSemantics and Cognition.

2,184 Citations1985Steven E. Boër, Ray Jackendoff

IEEE Transactions on Pattern Analysis and Machine IntelligenceIconic Indexing by 2-D Strings

596 Citations1987Shi-Kuo Chang, Qingyun Shi +1 more

This approach allows an efficient and natural way to construct iconic indexes for pictures and proves the necessary and sufficient conditions to characterize ambiguous pictures for reduced 2D strings as well as normal 2-D strings.

Elsevier eBooksINFORMATION PROCESSING

268 Citations1974Ralph Norman Haber

This chapter discusses the origins of information processing approaches and the unity of sensation, perception, memory, retrieval, Cognition, cognition, and knowledge.

Computer Graphics and Image ProcessingThe modelling of spatial relations

242 Citations1975John H. Freeman

This report is a discussion of how people encode the spatial relations between objects in a picture, and describes some mathematical and computational formalisms which can be used to embody the semantic content of these terms.

Communications of the ACMExpert systems: perils and promise

237 Citations1986Daniel G. Bobrow, S. Mittal +1 more

Based on a review of some actual expert-system projects, guidelines are proposed for choosing appropriate applications and managing the development process.

Pattern RecognitionAn algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane

200 Citations1987Donna J. Peuquet, Zhan Ci-Xiang

A model for determining the directional relationship in 2-D space between two simply-connected polygons of arbitrary shape, size and distance from each other is developed and found to have a computational complexity of O ( n ), where n is the total number of vertices or cells used to represent the two polygons.

Artificial IntelligencePlanning routes through uncertain territory

159 Citations1984Drew McDermott, Ernest Davis

A partial solution to the problem of constructing a fuzzy map is presented, an algorithm that assimilates a fact first by imposing constraints on the fuzzy coordinates of the objects involved, then by rearranging or growing the tree of frames of reference.

Relative Representation of Spatial Knowledge: The 2-D Case

105 Citations1991Daniel Hernández

This work introduces “abstract maps,” an analogical representation that inherently reflects the structure of the represented domain, and demonstrates their use in spatial reasoning and facilitates “coarse” reasoning and the hierarchical organization of knowledge.

Computers & GeosciencesSpatial concepts, geometric data models, and geometric data structures

102 Citations1992Andrew U. Frank

There seems to be some uncertainty in the GIS literature regarding the use of the words data model and data structure, but there is a clear understanding of these notions in the database literature and it is possible to define analogous terms for GIS: geometric data model.

Lecture notes in computer scienceQualitative spatial reasoning: A semi-quantitative approach using fuzzy logic

67 Citations1990Soumitra Dutta

This paper formulates a computational model for obtaining all induced spatial constraints on a set of landmarks, given aSet of approximate quantitative and qualitative constraints on them, which may be incomplete, and perhaps even conflicting.