浏览量:93

7.1. 旋转测径简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

7.1. 旋转测径简介

在1978年,Shamos[1]提出了一种求凸多边形直径的算法,标志了旋转测径法(Rotating Cliper)的诞生。到1983年,Toussaint[2]泛化了该算法的基本思想,使它还能够解决求凸多边形最小面积包围矩形、凸多边形之间的最大距离等问题,并把它命名为旋转测径法。旋转测径法,不单单是一种算法,它提供了一种解决一类问题的通用的方法,本章只涉及旋转测径法在二维下的应用,Pirzadeh[3]对它的应用进行了较详细的总结。

若一条直线L与凸多边形\({\rm P}\)相交且凸多边形的内部在直线的一侧,则称直线L为凸多边形\({\rm P}\)支撑线。显然,凸多边形\({\rm P}\)与它的支撑线L的相交部分只能是凸多边形的顶点或边,称该顶点为支撑线L的接纳点,称该边为支撑线L的接纳边,接纳边上的两个端点也是接纳点。

2015-3-23 21-39-44

图7.1 三种对踵对

若两个点p,q是多边形\({\rm P}\)上的顶点,且是\({\rm P}\)上互相平行的支撑线的接纳点,则称点对(p,q)是-点对踵对(Antipodal Pair)。类似,还存在-边对踵对-边对踵对,如图7.1所示,可以把它们统称为对踵对。例如,计算凸多边形的直径,计算凸多边形的直径就是找到距离最远的点-点对踵对,这里说的直径是指凸多边形上最远的两点之间的距离。

 

2015-3-23 21-39-57

图7.2 旋转测径法

旋转测径法的核心思想就在于旋转互相平行的支撑线。以如图7.2所示为例,设多边形是逆时针顺序的,初始的支撑线为X轴线方向,找到凸多形边\({\rm P}\)上Y分量最小和最大的点对作为初始点-点对踵对,即初始点-点对踵是\(({p_0},{p_3})\),这一子步骤需要O(n)的时间复杂度。计算两条平行的支撑线与边\({p_0}{p_1}\)、边\({p_3}{p_4}\)的夹角,分别是\({\theta _0},{\theta _3}\),设\({\theta _0} \prec {\theta _3}\),则将支撑线沿逆时针方向旋转\({\theta _0}\),现在点对\(({p_1},{p_3})\)成为了新的点-点对踵对,重复这个过程,直至循环一周,算法的复杂度是O(n)。

在具体的实例应用中,并不一定会计算支撑线与边的夹角,并选择夹角最小的角度进行旋转,但旋转互相平行的支撑线始终是它的基本操作,根据互相平行的支撑线的性质来达到算法的目的,是旋转测径法的精髓所在。

spacer

Leave a reply