Between the Lines: Measuring Areal Displacement in Line Simplification

Abstract. Quantitative measures of error are needed to complement subjective characterization of shape characteristics in the assessment of line simplication algorithms. Areal displacement is one of six metrics recommended for this purpose by McMaster in 1986. However, previous cartographers have failed to notice semantic ambiguities that obfuscate its meaning. This paper discusses semantic and computational aspects of areal displacement. Three distinct semantic definitions are identified. A simple definition derived from topological enclosure is shown to produce unintuitive results in certain regularly encountered situations. A more intuitively valid measure of areal displacement as a dynamic process is captured by the topological concept of minimum homotopy area, but robust, practical and efficient computation remains an active area of research. A third definition, referred to as shift displacement, is proposed that derives from the perspective of external regions that “shift sides” during the transformation of a line to its simplified form. A simple yet robust and computationally efficient algorithm is presented for computing displacement under the proposed definition.