Abstract: | Direction relations between extended spatial objects are important commonsense knowledge. Skiadopoulos proposed a formal model for representing direction relationsbetween compound regions (the finite union of simple regions), known as SK-model. Itperhaps is currently one of most cognitive plausible models for qualitative direction information, and has attracted interests from artificial intelligence and geographic informationsystem. Originating from Allen first using composition table to process time interval constraints; composing has become the key technique in qualitative spatial reasoning to checkthe consistency. Due to the massive number of basic directions in SK-model, its compositionbecomes extraordinary complex. This paper proposed a novel algorithm for the composition.Basing the concepts of smallest rectangular directions and its original directions, it transforms the composition of basic cardinal direction relations into the composition of intervalrelations corresponding to Allen''s interval algebra. Comparing with existing methods, thisalgorithm has quite good dimensional extendibility, that is, it can be easily transferred tothe tridimensional space with a few modifications. |