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.