Polyline simplification using quadric error metric with bounded error

Abstract

We study the problem of polygonal line simplification. The objective is to seek a polygonal line of smaller size that approximates the original one well. We present an algorithm that is based on edge contraction. An edge contraction merges two adjacent vertices into a new vertex and this new vertex will be made the new endpoint of the uncontracted edges incident to the two vertices merged. Thus, repeated applications naturally yield a simplification algorithm. We implemented three algorithms QG, QGG, and based on this approach. QGG and QG support each edge contraction in O(log m) time, where m is the size of the current polygonal line, whereas QLG supports each edge contraction in O(1) time. The selection of the edge to be contracted is based on the quadric error produced, which was introduced by Garland and Heckbert in simplifying 3D polygonal surfaces. We use and improve their algorithm in 2D. If the quadric error of each edge contracted is at most ε2, we can guarantee that the directed Hausdorff distance from the simplified line to the original one is within ε. We can supply an error tolerance ε to QG, QGG and QLG and let edges be contracted repeatedly until the current minimum quadric error exceeds ε2. On the other hand QGG and QG can also allow the user to directly and interactively reduce the number of edges in the simplified line when deemed necessary. We have conducted some experiments to measure the approximation error of the simplified lines produced by our algorithms.

Date of Award	1999
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology