论文研究 基于单调链的简单多边形距离算法.pdf

简单多边形的距离问题是计算机图形学中的一个研究难点,为了能快速地获得距离信息,提出一种基于单调链的简单多边形距离算法。算法先对多边形边界进行关于坐标轴的单调链分割,然后根据可见性原则确定候选链对,再结合层次树理论和分支限界策略计算链对距离以求解多边形的最近距离。试验结果表明,该算法性能优于其他同类算法。