Segmented Douglas-Peucker Algorithm Based on the Node Importance

• Xiaofei Wang,
• Wei Yang,
• Yan Liu,
• Rui Sun,
• Jun Hu,
• Longcheng Yang,
• Boyang Hou,

Vol. 14, No. 4, April 30, 2020
10.3837/tiis.2020.04.009, Download Paper (Free):

• Douglas-Peucker algorithm
• vertical chord ratio
• radial distance constraint
• node importance
• detection of critical points

Abstract

Vector data compression algorithm can meet requirements of different levels and scales by reducing the data amount of vector graphics, so as to reduce the transmission, processing time and storage overhead of data. In view of the fact that large threshold leading to comparatively large error in Douglas-Peucker vector data compression algorithm, which has difficulty in maintaining the uncertainty of shape features and threshold selection, a segmented Douglas-Peucker algorithm based on node importance is proposed. Firstly, the algorithm uses the vertical chord ratio as the main feature to detect and extract the critical points with large contribution to the shape of the curve, so as to ensure its basic shape. Then, combined with the radial distance constraint, it selects the maximum point as the critical point, and introduces the threshold related to the scale to merge and adjust the critical points, so as to realize local feature extraction between two critical points to meet the requirements in accuracy. Finally, through a large number of different vector data sets, the improved algorithm is analyzed and evaluated from qualitative and quantitative aspects. Experimental results indicate that the improved vector data compression algorithm is better than Douglas-Peucker algorithm in shape retention, compression error, results simplification and time efficiency.

Statistics

Cite this article