Integrating existing cone-shaped and projection-based cardinal direction
  relations and a TCSP-like decidable generalisation
  We consider the integration of existing cone-shaped and projection-based
calculi of cardinal direction relations, well-known in QSR. The more general,
integrating language we consider is based on convex constraints of the
qualitative form $r(x,y)$, $r$ being a cone-shaped or projection-based cardinal
direction atomic relation, or of the quantitative form $(\alpha ,\beta)(x,y)$,
with $\alpha ,\beta\in [0,2\pi)$ and $(\beta -\alpha)\in [0,\pi ]$: the meaning
of the quantitative constraint, in particular, is that point $x$ belongs to the
(convex) cone-shaped area rooted at $y$, and bounded by angles $\alpha$ and
$\beta$. The general form of a constraint is a disjunction of the form
$[r_1\vee...\vee r_{n_1}\vee (\alpha_1,\beta_1)\vee...\vee (\alpha
_{n_2},\beta_{n_2})](x,y)$, with $r_i(x,y)$, $i=1... n_1$, and $(\alpha
_i,\beta_i)(x,y)$, $i=1... n_2$, being convex constraints as described above:
the meaning of such a general constraint is that, for some $i=1... n_1$,
$r_i(x,y)$ holds, or, for some $i=1... n_2$, $(\alpha_i,\beta_i)(x,y)$ holds. A
conjunction of such general constraints is a $\tcsp$-like CSP, which we will
refer to as an $\scsp$ (Spatial Constraint Satisfaction Problem). An effective
solution search algorithm for an $\scsp$ will be described, which uses (1)
constraint propagation, based on a composition operation to be defined, as the
filtering method during the search, and (2) the Simplex algorithm, guaranteeing
completeness, at the leaves of the search tree. The approach is particularly
suited for large-scale high-level vision, such as, e.g., satellite-like
surveillance of a geographic area.
