求解简单多边形间最小距离的一个线性时间算法

摘要

计算简单多边形间的最小距离,在所有与几何图形计算有关的领域中,一直以来都是一个基本问题.为了更快地求解简单多边形的最小距离.提出了一个基于关联多边形三角化分割的简单多边形间最小距离的求解算法.该算法的主要思想是:首先构造一个关联多边形把两个多边形联系起来,其目的是把最小距离限制在这个关联多边形内;然后根据两个多边形的最小边界矩形包嗣框间的不同位置关系,详细阐述了关联多边形的构造过程,同时论述了关联多边形是一个简单多边形.为了计算最小距离,首先要对关联多边形进行三角化分割,并使最小距离位于三角化分割结果中某一个三角形区域内,或者至多位于两个相邻三角形区域内;之后通过对所有三角形进行遍历来找出最小距离及其所在的位置.该算法的时间复杂度是线性的.