IMPROVEMENT AND ASSESSMENT OF LI-OPENSHAW ALGORITHM

K. Zhu, F. Wu, H. Wang, Q. Zhu

Institute of Surveying and Mapping, Information Engineering University, Zhengzhou, China

zhkp417@126.com

 

Li-Openshaw algorithm is a self-adapted linear features generalization algorithm based on impersonality generalized natural law, and it can get reasonable and genuine generalization results. On the basis of analyzing characteristics of Li-Openshaw algorithm, there are two flaws in the algorithm: without referring to save local maximum points, the algorithm doesnt keep the entire shape of curve well;abnormity happened easily in selection when there are more than one point of intersection between SVO circularity and curve, and coordinates of selected points need to be calculated, which will decrease the simplification efficiency. According to the principle and purpose of linear simplification, Li-Openshaw algorithm is improved as follow: a new method of identifying the bend using the relationship between point and line is proposed, in order to find all the local maximum points and save to keep the entire shape of curve before simplification; find the first approximate point of intersection according to lines index, then select the point to save after generalization, which is nearest to the midpoint between center point of circle and point of intersection on the curve. Whats more, evaluating figures such as simplification results, time for simplification and ratio of compressing points are given, especially, two algorithms are compared and assessed by the method of curves shape structure characteristic assessment based on fractal theory. According to experiments results, compared with original algorithm, improved algorithm can keep the entire shape of curve better and increase simplifying efficiency.