基于LR序列的简单多边形的中轴线计算方法

摘要

本发明公开了基于LR序列的简单多边形的中轴线计算方法。本发明首先初始化由边组成的序列，在初始化状态下包括简单多边形P内每个内角的角平分线，然后利用每条边与其正方向和逆方向的相邻边的相交情况和endPoint确定其L和R标记；对所有边进行分组，对每组内部的边运用生长算法；若对所有组都执行了生长算法且每一组都停止了生长，当发现剩下的边交于同一点的时候，算法结束，若不交于同一点，则回到步骤3。本发明利用中轴线自身树的结构，利用两条边每次生长变为一条边的特点，每次生长都会减少一条边，计算时间和边的数量成正比，本发明能够在线性时间内计算出多边形的中轴线，提高了计算多边形中轴线的效率。