7. 旋转测径

浏览量:47

参考

      M.I. Shamos. "Computational geometry." PhD thesis, Yale University, 1978.       Godfried T. Toussaint. "Solving geometric problems with the rotating calipers." Proc. IEEE Melecon, 1983.       Hormoz Pirzadeh. "Computational geometry with the rotating calipers." PhD diss., McGill University, 1999.      

spacer
浏览量:63

7.6. 凸多边形间的距离

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 7.6. 凸多边形间的距离 问题描述:给定两个互不相交的凸多边形\(P = \{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \)和\({\mathop{\rm Q}\nolimits} = \{ {q_0},{q_1}, \cdots ,{q_{m - 1}}\} \),求它们之间的最小距离,设两个凸多边形都是逆时针顺序的。 两个凸多边形上的最小距离,可以用等式表示为 \ 图7.13 凸多边形间的最小距离

spacer
浏览量:180

7.5. 最小周长包围矩形

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 7.5. 最小周长包围矩形 问题描述:给定一组点集\(\{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \),求一个矩形,满足条件:(1)点集在矩形内部;(2)矩形的周长最小。 很多情况下,多边形的包围矩形的面积减小,对应的周长也会减小,但对于所有的多边形,这个规律是否还成立呢?这里,用一个具体的实例证明:这个规律是不成立的。 图7.12 多边形和包围矩形,(a)多边形,(b)最小面积包围矩形,(c)最小周长包围矩形 如图7.12所示,图(a)是多边形的最小面积包围矩形,图(c)是最小周长包围矩形,设图(b)和图(c)的面积和周长分别表示为\({{A}_{A}},{{P}_{A}}\)和\({{A}_{P}},{{P}_{P}}\),多边形的边a和b满足约束条件\(\frac{a}{2}\prec b\prec \frac{a}{\sqrt{2}}\),易知\(c=\frac{b}{\sqrt{2}},d=\frac{a}{\sqrt{2}}\),因此可以得到等式 \

spacer
浏览量:269

7.4. 最小面积包围矩形

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 7.4. 最小面积包围矩形 问题描述:给定一组点集\(\{{{p}_{0}},{{p}_{1}},\cdots ,{{p}_{n-1}}\}\),求一个矩形,满足条件:(1)点集在矩形内部;(2)矩形的面积最小。 首先求点集的凸多边形,易知,包围凸多边形的矩形一定包含整个点集,这一子步骤的复杂度是\(O(n\log n)\)。接着,可以利用旋转测径法,计算凸包的最小面积包围矩形,这一子步骤的复杂度是\(O(n)\)。显然,整个算法的复杂度受凸包算法的限制。 现在考虑最小面积包围矩形与凸多边形的关系,可以得出结论: 定理7.4.   最小面积的包围矩形的一条边与凸多边形的一条边是重合的。 图7.10 包围矩形的例子 证明:用反证法来证明,给定一个凸多边形\({\rm P}\),若包围矩形的任意一条边与多边形都不重合,它仍可能是最小面积矩形。令矩形与多边形相切的四个顶点分别是\({{p}_{i}},{{p}_{j}},{{p}_{k}},{{p}_{l}}\),如图7.10所示。令包围矩形的面积是\(A\),则有\(A={{l}_{0}}{{l}_{1}}\)。进一步,令\({{p}_{i}}\)和\({{p}_{k}}\)的距离与\({{p}_{j}}\)和\({{p}_{l}}\)的距离分别用\({{d}_{i,k}},{{d}_{j,l}}\)表示,则有 \ 将矩形沿着逆时针方向旋转\(\eta \)角(\(\eta \)是正值,保证\({{p}_{i}},{{p}_{j}},{{p}_{k}},{{p}_{l}}\)仍是新的矩形的相切点),边长\({{l}_{0}},{{l}_{1}}\)会发生变化,这可以分成两种情况:(1)同时变长或变短;(2)一条边变长,另一条变短。 情况(1),若沿着逆时针方向旋转\(\eta \)角,得到新的边长\({{l}_{0}}',{{l}_{1}}'\) (\({{l}_{0}}'\prec {{l}_{0}},{{l}_{1}}'\prec {{l}_{1}}\))缩短,则面积\(A'={{l}_{0}}'{{l}_{1}}'\prec {{l}_{0}}{{l}_{1}}=A\),能得到面积更小的矩形;相反,若新边的长度都增加了,则将矩形沿顺时针方向旋转一定的角度,得到的新边一定变短,同样能得到面积更小的矩形。 情况(2),矩形的旋转,导致一条边变长,另一条变短,设矩形沿逆时针方向旋转\(\delta \)(\(\delta

spacer
浏览量:58

7.3. 凸多边形的宽

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 7.3. 凸多边形的宽 问题描述:给定一个凸多边形\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \),求凸多边形的宽。 凸多边形的宽由多边形上距离最近的、互相平行的两条支撑线确定,支撑线之间的距离就是凸多边形的宽,如图7.8所示。Houle&Toussaint(1988)提出了两种求点集宽的算法,本节将描述其中与旋转测径相关的算法。 图7.8 对互相平行的支撑线确定的宽 定理7.3.   多边形\({\rm P}\)的宽由\({\rm P}\)上距离最近的点-边对踵对确定。 证明:可以分成两种情况来分析。 1. 点-点对踵对 给定任意两点\(p\)和\(q\),通过它们的支撑线分别是\({{l}_{1}}\)和\({{l}_{2}}\),那么将支撑线分别沿着\(p\)和\(q\)绕着某个方向旋转,可以使得支撑线之间的距离降低。如图7.9所示,将两条支撑线沿着逆时针方向旋转,它们间的距离会减小,直至一条支撑线与\({\rm P}\)的一条边重合为止。因此,点-点对踵对不能确定多边形的宽。 图7.9 点-点对踵对的支撑线 2. 边-边对踵对 此时,宽表示为一条边上的一个顶点与另一条边所在的支撑线之间的距离,所以这可以看成是点-边对踵对的特殊情况。   通过旋转测径法,得到所有的点-边对踵对,其中距离最小的点-边对踵对确定凸多边形的宽,时间复杂度是\(O(n)\),算法伪码如下所示: 给定一个凸多边形\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n

spacer
浏览量:255

7.2. 凸多边形的直径

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 7.2. 凸多边形的直径 问题描述:给定一个凸多边形\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \),求凸多边形的直径。 凸多边形的直径是指凸多边形上相距最远的两点之间的距离,现在考虑如果确定凸多边形的直径呢?引入一个重要的理论: 定理7.1.  凸多边形\({\rm P}\)的直径可以由两条距离最远的、互相平行的支撑线来确定,该支撑线之间的距离等于\({\rm P}\)的直径大小。 证明:给定一个凸多边形\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \),设点对\(\{ {p_a},{p_b}\} \)可以确定凸多边形\({\rm P}\)的直径,则\({{d}_{ab}}=\operatorname{dist}({{p}_{a}},{{p}_{b}})\)。\({{C}_{a}}\)表示以\({{p}_{a}}\)为原点,\({{d}_{ab}}\)为半径的圆,\({{C}_{b}}\)表示以\({{p}_{b}}\)为原点,\({{d}_{ab}}\)为半径的圆,直线\({{L}_{a}}\)与\({{C}_{b}}\)相切于点\({{p}_{a}}\),直线\({{L}_{b}}\)与\({{C}_{a}}\)相切于点\({{p}_{b}}\),\(L\)表示为连接点\({{p}_{a}}\)和\({{p}_{b}}\)的线段,如图7.3所示。由直线与圆相切的性质,知\({{L}_{a}}\bot L,{{L}_{b}}\bot L\),因此直线\({{L}_{a}}\)与\({{L}_{b}}\)互相平行。随机选择一个点\(q \in {\rm P},q \ne {p_a}\),由直径的定义知\(\operatorname{dist}(q,{{p}_{b}})\le {{d}_{ab}}\),则\(q\)在圆\({{C}_{b}}\)上或者圆\({{C}_{b}}\)内,所以\(q\notin

spacer
浏览量:67

7.1. 旋转测径简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 7.1. 旋转测径简介 在1978年,Shamos提出了一种求凸多边形直径的算法,标志了旋转测径法(Rotating Cliper)的诞生。到1983年,Toussaint泛化了该算法的基本思想,使它还能够解决求凸多边形最小面积包围矩形、凸多边形之间的最大距离等问题,并把它命名为旋转测径法。旋转测径法,不单单是一种算法,它提供了一种解决一类问题的通用的方法,本章只涉及旋转测径法在二维下的应用,Pirzadeh对它的应用进行了较详细的总结。 若一条直线L与凸多边形\({\rm P}\)相交且凸多边形的内部在直线的一侧,则称直线L为凸多边形\({\rm P}\)的支撑线。显然,凸多边形\({\rm P}\)与它的支撑线L的相交部分只能是凸多边形的顶点或边,称该顶点为支撑线L的接纳点,称该边为支撑线L的接纳边,接纳边上的两个端点也是接纳点。 图7.1 三种对踵对 若两个点p,q是多边形\({\rm P}\)上的顶点,且是\({\rm P}\)上互相平行的支撑线的接纳点,则称点对(p,q)是点-点对踵对(Antipodal Pair)。类似,还存在点-边对踵对,边-边对踵对,如图7.1所示,可以把它们统称为对踵对。例如,计算凸多边形的直径,计算凸多边形的直径就是找到距离最远的点-点对踵对,这里说的直径是指凸多边形上最远的两点之间的距离。   图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