8. 凸包

浏览量:168

参考

      Joseph O'Rourke. Computational geometry in C. Cambridge university press, 1998.       Stefan Gottschalk. "Collision queries using oriented bounding boxes." PhD diss., The University of North Carolina, 2000.       Donald R. Chand, and Sham S. Kapur. "An algorithm for convex

spacer
浏览量:872

8.5. 快速凸包算法

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 8.5. 快速凸包算法 8.5.1. 基本思想 快速凸包算法也可以看成是增量算法的一种变种,与随机增量算法相比,它们的不同就在于每次迭代从面的外部点集中选择的点不同。随机增量算法从外部点集中随机的选择一个点,但是快速凸包算法是选择距离最远的一个点,著名的开源代码Qhull、 CGAL都有快速凸包算法的C++实现。 在介绍快速三维凸包算法前,先介绍算法中会频繁使用到的两个基本的几何操作: 1.     给定3个三维空间上的点,确定一个平面。 平面可以用方程\(\vec{n}\cdot P+d=0\)表示,设3个点分别是\(\{{{v}_{0}},{{v}_{1}},{{v}_{2}}\}\),则有\(\vec{n}=({{v}_{1}}-{{v}_{0}})\times ({{v}_{2}}-{{v}_{0}})\),\(d=-\vec{n}\cdot {{v}_{0}}\),叉积的顺序影响法向量的方向,若\(\vec{n}\)是零向量,说明\({{v}_{0}},{{v}_{1}},{{v}_{2}}\)三点共线。 2.     计算三维空间上的点到平面的有符号距离。 设三维点为\(P\),平面为\(\Gamma :\vec{n}\cdot P+d=0\),那么点\(P\)到平面\(\Gamma \)的有符号距离表示为\(dist(P)=(\vec{n}\cdot P+d)/\left\| {\vec{n}} \right\|\)。若\(dist(P)\succ 0\),称点P在平面上方(Above the Plane),;若\(dist(P)\prec 0\),称点P在平面下方(Below the Plane);若\(dist(P)\text{=}0\),称点P在平面上(On the Plane)。 快速凸包算法是基于Beneath Beyond理论,增量算法也同样基于该理论,该理论如下所示,这里只考虑三维空间下的凸包: 设\(H\)是一个\({{R}^{3}}\)空间上的凸包,\(p\)是\({{R}^{3}}-H\)上的一个点。\(F\)是凸包\(conv(p\bigcup H)\)上的面,当且仅当

spacer
浏览量:366

8.4. 礼物包裹算法

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 8.4. 礼物包裹算法 8.4.1. 基本思想 礼物包裹算法最早由Chand&Kapur (1970)提出的,它不仅可以实现二维、三维凸包,还可以实现更高维的凸包,算法复杂度是\(O(hn)\),\(h\)表示输出的面的数量,\(n\)表示点集的个数,算法复杂度跟输出面相关。直观上,三维的礼物包裹算法,可以看做是在点集的外面包围了一张纸,每次更新一个新的顶点,用纸覆盖住它,就像包裹礼物一样,直至覆盖整个点集。本小节只描述三维的礼物包裹算法,对于更高维的情况,可以参考Chand&Kapur (1970)以及Preparata&Shamos(1985)的描述。 礼物包裹算法基于一个简单的理论:任意一个三维凸包的每一条边有且只有两个相邻面。三维凸包上的每个面用三角形面片表示,若一个凸包有\(h\)个面,则凸包共有\(3h/2\)条边,根据欧拉公式可知,顶点的个数是\(n=h/2+2\)。 设三维凸包上的面用三角形面片表示,本节暂不考虑各种退化情况,三维凸包的礼物包裹算法的算法伪码如下所示: 三维空间下点集\(S=\{{{p}_{0}},{{p}_{1}},...,{{p}_{n-1}}\}\)的凸包 1.    面集合为Q,存储边的集合\(T\); 2.    \(Q \leftarrow \emptyset \); 3.    \(T \leftarrow \emptyset \); 4.    找到一个初始的凸包面\(F\); 5.    \(Q\leftarrow F\); 6.    \(T\leftarrow \)面\(F\)的每条边信息和计数器;   //计数器初始值为1 7.    while( \(Q\)非空 ) 8.          

spacer
浏览量:293

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

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

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