简单多边形间最大距离的求解算法  

An algorithm for computing the maximum distance between two simple polygons

作　　者：崔先国[1] 毛定山[2] 

机构地区：[1]山东科技大学测绘科学与工程学院,山东青岛266510 [2]北京山海经纬信息技术有限公司,北京100086

出　　处：《测绘科学》2008年第6期139-140,共2页Science of Surveying and Mapping

摘　　要：求解任意两个简单多边形间的最大距离,在几何图形计算中,一直是一个基本问题。在对多边形自身的特性以及两多边形间关系进行深入分析的基础上,提出了一个基于折线凸包的单调性的简单多边形间最大距离的求解算法。根据封闭折线内部所具有的特性,把封闭折线拆分成两个断开的折线,使一条折线在另一条折线左边。两个多边形分别被拆分成四条折线,两个分为一组。分别求出每组中两条折线的凸包,利用凸包的单调性可以快速地找出两个距离最远的顶点,其中较大的是两个简单多边形间的最大距离。算法的时间复杂度是线性的。In the computer graphics, spatial analysis of geographic information system （GIS） and computer aided design （ CAD）, it is a fundamental problem to compute the maximum distance between two polygons. A simple and fast algorithm is presented for computing the maximum distance between two polygons based on the monotonieity of convex hull. According to the interior relationship of closed polygonal line, a closed polygonal line is split to two open polygonal lines, so that one is at the left of the other one. Two polygons are split to four open polygonal lines, and they are grouped in two. Then the convex hulls of each group are constructed to find likely farthest two vertices which are on respective convex hull. So nearly half sum of polygon vertices is excluded by splitting closed polygonal lines, and many vertices which are on open polygonal line, are also excluded while constructing convex hulls, which results in an efficient algorithm. The algorithm＇ s time complexity is linear in the size of two polygons.

关 键 词：多边形 中轴线 凸包 单调性 

分 类 号：P28[天文地球—地图制图学与地理信息工程]