Composing Cardinal Direction Relations

We study the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Our approach is formal and complements the presentation of Goyal and Egenhofer. We focus our efforts on the operation of composition for two cardinal direction relations. We point out that the only published method to compute the composition does not always work correctly. Then we consider progressively more expressive classes of cardinal direction relations and give composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. Finally, we demonstrate that in some cases, the binary relation resulting from the composition of two cardinal direction relations cannot be expressed using the relations defined by Goyal and Egenhofer.