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

摘要：

求解任意两个简单多边形间的最大距离,在几何图形计算中,一直是一个基本问题.在对多边形自身的特性以及两多边形间关系进行深入分析的基础上,提出了一个基于折线凸包的单调性的简单多边形间最大距离的求解算法.根据封闭折线内部所具有的特性,把封闭折线拆分成两个断开的折线,使一条折线在另一条折线左边.两个多边形分别被拆分成四条折线,两个分为一组.分别求出每组中两条折线的凸包,利用凸包的单调性可以快速地找出两个距离最远的顶点,其中较大的是两个简单多边形间的最大距离.算法的时间复杂度是线性的.

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

所属期刊栏目：33

分类号：P28(地图制图学（地图学）)

在线出版日期：2009-02-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：139-140