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

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

An Algorithm for Computing the Minimal Distance Between Two Polygons in Linear Time

In computer graphics,spatial analysis of geographic information system(GIS) and computer aided design(CAD),a fundamental problem is to compute the minimal distance of two polygons.An efficient algorithm is presented for computing the minimal distance between two polygons based on the triangulation of their association polygon.The main idea of the algorithm is that two polygons were linked by an association polygon constructed,so that the minimal distance between two polygons is restricted within the association polygon.According to three different relationships between two polygon-boxes,the approach of constructing the association polygon is described in detail and the association polygon is proved to be a simple polygon.The association polygon is triangulated to find the minimal distance.As a result,the distance between a vertex and an edge within one or two adjacent triangles is the minimum.The time complexity of the algorithm is linear related to the size of the two polygons.