浏览量:199

8.3. Graham扫描算法

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 8.3. Graham扫描算法 Graham扫描算法会先将点按照极角的大小顺序排列,接着按顺序遍历每个点,通过夹角的大小判断哪些点在凸包上,算法的伪码如下所示: 求给定二维点集\(S=\{{{p}_{0}},{{p}_{1}},...,{{p}_{n-1}}\}\)的凸包 1.    求出最左下角的点,即\(X\)分量的值最小点,若\(X\)分量值最小的点有多个,取\(Y\)分量最小的点,设为\({{p}_{0}}\); 2.    剩下的点集,根据极角大小,逆时针排序,得到\(\{{{p}_{1}},...,{{p}_{m-1}}\}\); 3.    令栈\(Stack\)为空,用\(Stack\)表示栈中第\(i+1\)个元素,用\(k\)表示栈中的元素个数;若栈中有\(k\)个元素,则\(Stack\)即为栈顶元素;每一次\(\text{PUSH}\)操作,栈元素个数\(k\)加1;每次\(\text{POP}\)操作,栈元素个数\(k\)减1; 4.    \(\operatorname{PUSH}(Stack,{{p}_{0}})\); 5.    \(\operatorname{PUSH}(Stack,{{p}_{1}})\); 6.    for(\(i=2\) ; \(i\prec m\) ; \(i=i+1\)) 7.           while (\(k\ge 2\) && 由\(Stack\),\(Stack\)和\({{p}_{i}}\)的夹角\(\theta \ge 180\)) 8.                  \(POP(Stack)\); 9.           end while; 10.   end for; 11.  

spacer
浏览量:595

8.2. 凸包算法综述

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 8.2. 凸包算法综述 8.2.1. 二维凸包 解决二维凸包问题,主要有Jarvis步进算法(Jarvis March),增量算法(Incremental Method),快速凸包算法(Quick Hull),分而治之算法(Divide and Conquer),Graham扫描算法,单调链算法(Monotone Chain),Kirkpatrick–Seidel算法,chan算法。 图8.4 Jarvis步进法 Jarvis步进法是由Jarvis(1973)提出的,但是它只是比它更早的Chand&Kapur(1970)提出的礼物包裹(Gift Wrapping)算法在二维情况下的特例,Preparata&Shamos(1985),O'Rourke(1998)和Cormen el(2001)都有该算法更详细的描述。直观上,可以把Jarvis步进法看做是在集合Q的外面紧紧地包了一条线,线的一端固定在左下角的点上。把线向右拉使其绷紧,再拉高些,直到碰到一个点,这个点一定在凸包上。使线继续处于绷紧状态,查到下一个顶点,直至回来原点。更形式化的表示,是通过判断极角的大小,来确定下一个顶点,如图8.4(a)所示,先找到最左下角的点\({{p}_{0}}\)(点的X分量最小,若多个点X分量相同,选择其中Y分量最小的点,它一定是凸包的一个顶点,搜索过程需要\(O(n)\)的时间。接着相对于\({{p}_{0}}\),如图(b)所示,找到极角最小的点\({{p}_{1}}\),这一步搜索过程需要遍历点集中其它所有的点,算法复杂度是\(O(n)\)。接着是分别搜索\({{p}_{2}}\)、\({{p}_{3}}\),直至回到起始点\({{p}_{0}}\),算法复杂度与输出的凸包的顶点相关。 图8.5 增量凸包算法 增量算法另外一种求解凸包问题的算法,由Kallay(1984)提出,在O'Rourke(1998)中有该算法详细的描述,增量算法的复杂度是\(O({{n}^{2}})\)。它的基本思想是,随机选择若干个不共线的点,作为初始凸包,初始凸包可以是三角形也可以是四边形,为了使初始的凸包尽可能多的囊括非极点,可以选择最左、最右、最上、最下的四个点构成的四边形作为初始凸包。每次增加一个点,若该点在当前凸包内,则移除该点;否则,移除对该点可见的边,连接该点与当前凸包上和该点相切的点,产生新的凸包;重复上述步骤,直至点集中所有的点都处理为止。这里介绍两个重要的概念:可见与相切。若一个点\(p\)在凸多边形的边\(e\)指向外的法向量的一侧,称点\(p\)对边\(e\)可见或者称边\(e\)对点\(p\)可见。若点\(p\)在凸多边形外,那么对点\(p\)可见的边必然是连续的,它们可以表示为\(\overline{{{p}_{i}}{{p}_{i+1}}},\cdots ,\overline{{{p}_{j-1}}{{p}_{j}}}\),称点\({{p}_{i}},{{p}_{j}}\)为凸多边形上与点\(p\)相切的两个点。注意,这里的可见和相切的概念只限于点在凸多边形的情况。设凸多边形上一条边\(\overline{{{p}_{i}}{{p}_{i+1}}}\),该边指向外的法向量为\(\vec{n}\),若一个点\(p\)满足不等式\(\left( p-{{p}_{i}} \right)\cdot \vec{n}\succ 0\),则点\(p\)对边\(\overline{{{p}_{i}}{{p}_{i+1}}}\)可见,否则,不可见。以如图8.5(a)所示为例来解释下增量算法的基本过程,求点集 \(\left\{ {{p}_{0}},{{p}_{1}},{{p}_{2}},{{p}_{3}},{{p}_{4}} \right\}\)构成的凸包。首先随机选择三个不共线的点\(\left\{ {{p}_{0}},{{p}_{1}},{{p}_{4}} \right\}\),作为初始的凸包,如图(b)所示。接着,如图(c)所示,增加一个点\({{p}_{5}}\),\({{p}_{5}}\)在当前凸包内,是非极点,直接排除。如图(d)所示,增加一个点\({{p}_{2}}\),点\({{p}_{2}}\)对边\(\overline{{{p}_{4}}{{p}_{0}}}\)和边\(\overline{{{p}_{0}}{{p}_{1}}}\)不可见,但点\({{p}_{2}}\)对边\(\overline{{{p}_{1}}{{p}_{4}}}\)可见,与点\({{p}_{2}}\)相切的点就是\({{p}_{1}}\)和\({{p}_{4}}\),移除\({{p}_{1}}\)和\({{p}_{4}}\)之间的边,连接\({{p}_{1}}\)、\({{p}_{2}}\)与\({{p}_{2}}\)、\({{p}_{4}}\),生成新的凸包。按照相同的方法处理点\({{p}_{3}}\),最后得到点集的凸包。搜索凸多边形上与点相切的两个顶点的暴力算法的复杂度是\(O(n)\),但是可以采用二分查找的方法进行优化,搜索的算法复杂度降低到\(O(logn)\),因此增量算法的复杂度可以从\(O({{n}^{2}})\)降低到\(O(nlogn)\)。 图8.6 快速凸包算法 快速凸包算法的思想,很早是由多个研究者独立提出的,由于该算法与快速排序的思想很相似,因此Preparata&Shamos(1985)把它命名为快速凸包算法,并做了详细地描述,在O'Rourke(1998)中也有该算法的伪码表述。快速凸包算法在最好情况下,复杂度能达到\(O(nlogn)\),但是在最坏情况下复杂度是\(O({{n}^{2}})\),平均复杂度为\(O(nlogn)\)。以图8.6(a)所示为例,求点集\(\{{{p}_{0}},...,{{p}_{10}}\}\)的凸包。首先,找到点集中最左、最右、最上、最下的四个点,作为初始的凸包,尽可能多地舍弃初始凸包内的非极点,即舍弃点\({{p}_{8}}\)和点\({{p}_{9}}\)。现在考虑当前凸包外侧还未处理的点,先考虑边\(\overline{{{p}_{2}}{{p}_{3}}}\),从边的外侧点集中,找到与边距离最远的点,如图(b)所示,边\(\overline{{{p}_{2}}{{p}_{3}}}\)的外侧点集\(\{{{p}_{4}},{{p}_{5}},{{p}_{6}},{{p}_{7}}\}\)中,点\({{p}_{4}}\)与边的距离最远,找到当前凸包上与点\({{p}_{4}}\)相切的两个顶点,即顶点\({{p}_{2}}\)和\({{p}_{3}}\),删除当前凸包上\({{p}_{2}}\)和\({{p}_{3}}\)之间的边,连接\({{p}_{2}}\)、\({{p}_{4}}\)与\({{p}_{4}}\)、\({{p}_{3}}\),生成新的凸包。如图(c)所示,舍弃在新的凸包内的点,即舍弃点\({{p}_{5}}\)和点\({{p}_{6}}\)。接着,只有边..和\({{p}_{3}}{{p}_{0}}\)的外侧还存在未处理的点集,按照前面的操作进行处理,如图(d)和(e)所示,最终得到由\({{p}_{0}},{{p}_{1}},{{p}_{2}},\)\({{p}_{4}},{{p}_{7}},{{p}_{3}},{{p}_{10}}\)共7个点构成的凸包,如图(f)所示。 图8.7 分而治之凸包算法 分而治之算法最早是由Preparata&Hong(1977)提出的,它的基本思想,就是把点集分割成左右或者上下两半,分别求出两半点集的凸包,再把它们合并,合并操作的算法复杂度是\(O(n)\),用\(T(n)\)表示算法的复杂度,则有\(T(n)=2T(n/2)+O(n)\),因此分而治之算法的复杂度是\(O(nlogn)\)。以图8.7(a)所示为例,求点集\(\{{{p}_{0}},...,{{p}_{9}}\}\)的凸包。可以把点集分成左右两半,如图(b)所示,左半点集产生一个子凸包\(C{{H}_{1}}\),右半点集产生另一个凸包\(C{{H}_{2}}\);接着,需要把这两个子凸包合并成一个大凸包,找到两个凸包的切线\(\overline{{{p}_{4}}{{p}_{8}}}\)和\(\overline{{{p}_{2}}{{p}_{5}}}\),删除切线之间两个子凸包相对可见的边,连接两个子凸包的切线,完成子凸包的合并。相对于其它算法来说,分而治之算法的实现难度较大,Schneider& Eberly (2002)对二维分而治之凸包算法的实现有详细的表述。 Graham扫描算法最早是由Graham在1972年提出的,该算法最好和最坏的算法复杂度都是\(O(nlogn)\),实现也比较简单,能有效地处理各种退化情况,能有效的解决二维凸包问题,但是它无法扩展到三维,甚至于更高维的情况,因此对其它凸包算法的研究还是很有必要的,在后面的章节中将详细介绍该算法的思想和实现伪码。

spacer
浏览量:239

8.1. 凸包简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 8.1. 凸包简介 二维的多边形的英文表示是Polygon,二维的凸包称为凸多边形,三维的多面体英文表示是Polyhedron,三维的凸包称为凸多面体。二维的多边形和三维的多边形都可以称为多胞体,多胞体的英文表示是Polytope,多胞体是任意维度上的几何对象的泛化表述。 凸多胞体有很多重要的应用,比如碰撞避免、计算最小包围盒等问题,在不同的应用背景下也会有不同的定义方法,这里提供两种凸多胞体的定义:顶点定义法和半空间交定义法。此外,也简单介绍些与凸包问题相关的概念。 概念一. 顶点定义法 给定\({{R}^{n}}\)空间上的有限点集\(S\),由点集中有限个极点(Extreme Point)构成的凸对象(Convex Object),就称为凸多胞体。 极点就可以看成是多胞体的顶点,以二维多边形为例,极点就相当于凸多边形的顶点。使用严格的数学定义来说,极点是指那些不能由凸多胞体内的其它点的凸组合(Convex Combination)表示出来的点。给定点\({{x}_{1}},\cdots ,{{x}_{k}}\)共\(k\)个点,它的凸组合可以用下面的等式表示: \ 一条线段就是它的端点的所有的凸组合,三角形就是它的三个顶点的凸组合,一个四面体是它的四个顶点的凸组合。 图8.1 凸多边形和非凸多边形 换句话,对于\({{R}^{n}}\)空间中的对象\(K\),如果对象中的任意两个点构成的线段,也包含在对象\(K\)内,则称对象\(K\)是凸的。如图8.1所示的两个多边形\({{\rm P}_1}\)和\({{\rm P}_2}\),多边形\({{\rm P}_1}\)中的任意两点连成的线段也在多边形内,因此多边形\({{\rm P}_1}\)是凸的;但是多边形\({{\rm P}_2}\)中,存在两点的连成的线段不存多边形内的情况,如图中的线段\(\overline {{A_2}{B_2}} \),因此多边形\({{\rm P}_2}\)不是凸的。

spacer
浏览量:27

参考

      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
浏览量:40

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
浏览量:63

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
浏览量:170

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
浏览量:39

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
浏览量:124

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
浏览量:39

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