%0 Journal Article
%T An Algorithm for Computing the Minimal Distance Between Two Polygons in Linear Time<br>求解简单多边形间最小距离的一个线性时间算法
%A MAO Ding-shan
%A CUI Xian-guo
%A LI Xing
%A WU Zhe-hui
%A <br>毛定山
%A 崔先国
%A 李行
%A 吴哲辉
%J 中国图象图形学报
%D 2008
%I 
%X 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.
%K association polygon
%K minimum bound rectangle(MBR)
%K triangulation<br>关联多边形
%K 最小矩形包围框(MBR)
%K 三角化分割
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=D06194629680C940ACE75262F54B9D85&aid=4DD614081AE0A883FD04BA93F9D0FA2E&yid=67289AFF6305E306&vid=FC0714F8D2EB605D&iid=59906B3B2830C2C5&sid=55161FEDEF8BABB8&eid=219F34744F662FF5&journal_id=1006-8961&journal_name=中国图象图形学报&referenced_num=0&reference_num=10