The Head-Body-Tail Intersection for Spatial Relations Between Directed Line Segments

Yohei Kurata and Max J. Egenhofer, The Head-Body-Tail Intersection for Spatial Relations Between Directed Line Segments, in: M. Raubal, H. Miller, A. Frank, and M. Goodchild (eds.) GIScience 2006—4th International Conference on Geographic Information Science, Lecture Notes in Computer Science, Vol. 4197, pp. 269-286.

Directed line segments are fundamental geometric elements used to model through their spatial relations such concepts as divergence, confluence, and interference. A new model is developed that captures spatial relations between pairs of directed line segments through the intersections of the segments’ heads, bodies, and tails. This head-body-tail intersection identifies 68 classes of topological relations between two directed line segments highlighting two equal-sized subsets of corresponding relations that differ only by their empty and non-empty body-body intersections. The relations’ conceptual neighborhood graph takes the shape of a torus inside a torus, one for each subset. Another 12 classes of topological relations are distinguished if the segments’ exteriors are considered as well, lining up such that their conceptual neighborhood graph forms another torus that contains the other two tori. These conceptual neighborhoods as well as the relations’ composition table enable spatial inferences and similarity assessments in a consistent and reasoned manner.