Searching for a Compressed Polyline with a Minimum Number of Vertices

摘要

There are many practical applications that require the simplification of polylines. Some of the goals are to reduce the amount of information, improve processing time, or simplify editing. Simplification is usually done by removing some of the vertices, making the resultant polyline go through a subset of the source polyline vertices. However, such an approach does not necessarily produce a new polyline with the minimum number of vertices. Using an algorithm that finds the compressed polyline with the minimum number of vertices is an improvement in memory and postprocessing time. However, when the resultant polyline is edited by an operator, having a polyline with the minimum number of vertices decreases the operator time, which reduces the cost of processing the data. The algorithm described in this paper is used for the reconstruction of orthogonal buildings. If the resultant closed polyline is required to pass through original vertices, it would often result in extra segments, and all segments are likely to be shifted due to fixed endpoints. A viable solution to finding a polyline within a specified tolerance with the minimum number of vertices is described in this paper.