Definition 1 (direction relation matrix). Suppose *a, b* are two bounded connected regions. Take b as the reference object, and a as the primary object. The cardinal direction of a to b is encoded in a 3 × 3 Boolean matrix

$$\mathrm{dir}(a,b)=\left[\begin{array}{c c c}{{d^{N W}}}&{{d^{N}}}&{{d^{N E}}}\\ {{d^{W}}}&{{d^{O}}}&{{d^{E}}}\\ {{d^{S W}}}&{{d^{S}}}&{{d^{S E}}}\end{array}\right],$$
$$(6)$$
$$(T)$$
$$N\}.$$
$\mathbf{v}=\mathbf{v}\cdot\mathbf{v}$ 2. 
$\mathbf{a}=\mathbf{a}$. 
7
where for each tile name $\chi\in\{NW,N,NE,W,O,E,SW,S,SE\}$.  
$$d^{\chi}=1\Leftrightarrow a^{\circ}\cap\chi(b)\neq\varnothing,$$
◦ ∩ χ(b) 6= ∅, (7)
where a
◦is the interior of a and χ(b) denotes the χ-tile of b. The cardinal direction relation of a to b is compactly represented in the form δ1 : δ2 :*· · ·*: δk, where {δ1, δ2, · · · , δk} is the set of tile names χ such that d χ = 1.

Take the two regions *a, b* in Figure 2(b) as example. The cardinal direction relation of a to b is N :NE :E and that of b to a is W :O:SW :S.

There are altogether 218 cardinal direction relations. Write Bdir for the set of these relations. Then each pair of connected regions are related by one and only one relation in Bdir. This means that Bdir is a set of jointly exhaustive and pairwise disjoint (JEPD)
relations. The cardinal direction calculus (CDC) is the Boolean algebra generated by Bdir.

Relations in Bdir are called basic relations of the CDC, and non-basic CDC relations are unions of basic relations. The universal relation, denoted by ∗, is in particular the union of all basic CDC relations.

Remark 1. Note that in the above definition we assume connected regions. When possibly disconnected regions are used, the calculus is called the cardinal direction calculus for possibly disconnected regions, written as CDCd. There are 511 basic relations in CDCd
[15, 10].

## 3. Define Relations Outside The Cdc

Non-basic CDC relations are formed by taking unions of basic relations. Relations outside the CDC may be *definable* in the CDC in the following sense.

Definition 2. Let N be a possibly incomplete network of basic CDC constraints over variables *u, v* and w1, · · · , wk. We say a relation γ is *entailed* by N , written N |= γ, if γ = {(*a, b*) : (∃c1, · · · , ck) s.t. (a, b, c1, · · · , ck) is a solution of N }. (8)
If γ is entailed by some basic CDC network, then we also say γ is *definable* in the CDC.