Metric Details of Topological Line-Line Relations

Kostas Nedas, Max Egenhofer, and Dominik Wilmsen
International Journal of Geographical Information Science 21(1): 21-48, 2007.


Many real and artificial entities in geographic space, such as transportation networks and trajectories of movement, are typically modeled as lines in geographic information systems. In a similar fashion, people also perceive such objects as lines and communicate about them accordingly as evidence from research on sketching habits suggests. To facilitate new modalities like sketching that rely on the similarity among qualitative representations, oftentimes multi-resolution models are needed to allow comparisons between sketches and database scenes through successively increasing levels of detail. Within such a setting, topology alone is sufficient only for a coarse estimate of the spatial similarity between two scenes, whereas metric refinements may help extract finer details about the relative positioning and geometry between the objects. The 9-intersection is a topological model that distinguishes 33 relations between two lines based on the content invariant (empty-nonempty intersections) among boundaries, interiors, and exteriors of the lines. This paper extends the 9-intersection model by capturing metric details for line-line relations through splitting ratios and closeness measures. Splitting ratios, which apply to the 9-intersectionÍs non-empty values, are normalized values of lengths and areas of intersections. Closeness measures, which apply to the 9-intersection's empty values, are normalized distances between disjoint object parts. Both groups of measures are integrated into compact representations of topological relations, thereby addressing topological and metric properties of arbitrarily complex line-line relations.