Cardinal Direction Calculi

Origin. Frank ("Qualitative spatial reasoning about cardinal directions", 1991) gave the two point-based schemes — cone-based and projection-based — that everything since has been a correction of. Ligozat, "Reasoning about cardinal directions" (Journal of Visual Languages and Computing 9, 1998), supplied the algebraic treatment of the projection-based case. Goyal and Egenhofer (1997; "Cardinal directions between extended spatial objects", IEEE TKDE) replaced points with regions and produced the Cardinal Direction Calculus, the model the field now means by the name. Skiadopoulos and Koubarakis ("Composing cardinal direction relations", Artificial Intelligence 152, 2004) found that Goyal and Egenhofer's composition method fails on some inputs and gave a correct one; Liu, Zhang, Li, and Ying (AIJ 174, 2010) settled the complexity.

Models. Direction between extended regions, without coordinates. Point-based schemes ask which of eight sectors a target falls in and cannot say that Portugal is west of Spain and south of it; the CDC replaces the point with a reference region's bounding rectangle, extends its four edges to cut the plane into nine tiles, and records which tiles the target actually occupies. A relation is therefore a set of tiles, not one of them, which is what makes the calculus expressive enough for real geography and what makes its algebra fail to be a relation algebra.

Formalism.

Point-based (Frank 1991): Cone-based — the plane around the reference point is cut into four or eight cones plus a neutral zone at the centre. Projection-based — the two axes through the reference point cut the plane into nine sectors; direction is read off each axis independently. The two disagree: cone-based makes direction depend on angle, projection-based on coordinate order, and neither is a refinement of the other. Ligozat (1998) showed the projection-based scheme is the product of two point algebras on the axes, and inherits their composition.

Cardinal Direction Calculus (Goyal–Egenhofer 1997): Let b be a bounded region in ℝ², and mbr(b) its minimum bounding rectangle — the smallest axis-parallel rectangle containing it. Extending mbr(b)'s four edges partitions the plane into nine tiles:

        NW  |  N  |  NE
       -----+-----+-----
         W  |  O  |  E
       -----+-----+-----
        SW  |  S  |  SE

For a primary region a and reference region b, the CDC relation δ_ab is the 3×3 Boolean matrix (d_ij), with d_ij = 1 ⟺ a° ∩ b_ij ≠ ∅ where a° is the interior of a and b_ij the corresponding tile. So the relation says which tiles the target meets, and a single relation may be N∧NE∧E — direction is a set, not a value.

Basic relations: 218, for connected regions — not 2⁹ = 512, because most tile-sets are not realizable by a connected region. (Skiadopoulos–Koubarakis; the count is what a correct composition algorithm has to range over.)

Composition, and why it is only weak: Skiadopoulos and Koubarakis (2004) gave the first correct consistency-based composition algorithms, and proved a non-expressibility result: the existential composition of two CDC relations cannot in general be written using the relations of the language, unless the language is extended with further predicates. So composition in CDC is weak composition in Renz and Ligozat's sense (2005) — the smallest relation in the language containing the true composite — and CDC is not a relation algebra. The composition table is a device, not a structure theorem.

Complexity (Liu–Zhang–Li–Ying 2010): Consistency of a network of basic CDC constraints — realizability by connected regions in ℝ² — is decidable in cubic time, and the algorithm returns a canonical solution. Consistency of general CDC networks is NP-complete. Navarrete, Morales, and Sciavicco (2007) had settled the basic connected case independently.

Neighbours: Rectangle Algebra — Allen's interval relations taken on both axes; coarser than CDC and a relation algebra. LR and Double-Cross (Ligozat 1993; Freksa 1992), Dipole (Moratz–Renz–Wolter 2000), OPRA (Moratz–Dylla–Frommberger 2005) — orientation rather than absolute direction. Li (2007) combines CDC with RCC-8, where the interaction of topology and direction is the question. 3D-nCDC extends the tiling to 27 cells in space.

Symbols.

Metatheory. The CDC is the most expressive qualitative calculus for direction and it pays for the expressiveness in algebra: because a relation is a set of tiles rather than a tile, the existential composition of two relations is generally not expressible in the language (Skiadopoulos–Koubarakis 2004), so the calculus has only weak composition and is not a relation algebra. That places it against RCC-8, which is one, and makes the composition table a computational device rather than a statement about a structure. The complexity is the other half: basic networks are cubic and general networks are NP-complete, so the tractability boundary sits exactly at whether the input relations are basic — which is the same shape of result as RCC-8's maximal tractable subclasses and reached by an entirely different route. Two of the field's three original composition tables were wrong in published form and were corrected only by machine-checkable reanalysis; that is worth recording as a fact about qualitative calculi rather than about these authors.

Applies to. Geographic information systems and spatial databases, where "north of" is the query and coordinates are the wrong abstraction. Image retrieval and scene description. Natural-language spatial semantics, where direction terms are region-to-region and vague at the edges. Robotics and qualitative navigation. Combined topological-directional reasoning (Li 2007), where CDC meets RCC and the interaction is the open problem.

Limitations. The bounding rectangle is an artifact: two regions with identical mbrs are indistinguishable to the calculus, so direction is computed against a box rather than a shape, and Portugal's relation to a crescent-shaped Spain is the relation to Spain's rectangle. Not a relation algebra, so the standard qualitative-reasoning machinery — path consistency as a decision procedure, algebraic closure — does not transfer, and each result must be reproved. NP-complete in general. The 218 basic relations make hand computation infeasible and published composition tables unreliable. Axis-parallel by construction: the calculus presupposes a global frame, and has nothing to say about direction relative to an observer, which is what the orientation calculi (LR, OPRA, Dipole) exist for.

© 2026 Lingenic LLC