The extraction of main skeleton line of polygon based on thinning and minimum spanning tree
YANG Yuxue, WANG Hongyan, ZHANG Lingling, JING Ying, YAO Xinyun, Yan Ma · DOAJ (DOAJ: Directory of Open Access Journals) · 2022
It existed that the current methods for extracting main skeleton lines of irregular polygons had disadvantages such as complex design and low execution efficiency. To solve these issues, a novel algorithm to extract main skeleton lines of polygons based on thinning and minimum spanning tree was proposed. Firstly, the minimum bounding box of the polygon was determined, in which the points with values of 0 or 1 are uniformly distributed. Secondly, the skeleton of the polygon was extracted by the thinning algorithm, after which the minimum spanning tree was generated by Prim algorithm. Finally, the length of the path between the two leaf nodes in the minimum spanning tree was calculated and the path with the maximum length was taken as the main skeleton line. The experimental results showed that the proposed algorithm was effective and practical.