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.