基于细化和最小生成树的多边形主骨架线提取  

The extraction of main skeleton line of polygon based on thinning and minimum spanning tree

作　　者：杨雨雪 王红艳 张玲玲 景莹 姚欣赟 马燕[1] YANG Yuxue;WANG Hongyan;ZHANG Lingling;JING Ying;YAO Xinyun;MA Yan(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 201418,China)

机构地区：[1]上海师范大学信息与机电工程学院,上海201418

出　　处：《上海师范大学学报（自然科学版）》2022年第2期204-209,共6页Journal of Shanghai Normal University(Natural Sciences)

基　　金：国家自然科学基金(61373004);国家级大学生创新创业训练项目(202110270135)。

摘　　要：现有的不规则多边形主骨架线提取方法存在设计复杂、执行效率低等缺点,对此提出一种基于细化和最小生成树的多边形主骨架线提取方法.首先,确定多边形的最小包围盒,并在其中生成均匀分布、数值分别为0或1的点,运用细化算法提取多边形骨架;再利用Prim算法生成最小生成树;最后,计算最小生成树上的两个叶子节点间的路径长度,将长度最长的路径定义为主骨架线.实验结果表明:本方法提取出的主骨架线效果较好,具有一定的实用性.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.

关 键 词：主骨架线 细化 最小生成树 最小包围盒 路径 

分 类 号：P208[天文地球—地图制图学与地理信息工程]