Computational Geometry

浏览量:439

前言

前言 版权说明 本作品版权归TwinklingStar所有,允许你自由的下载、打印、复制、转载本作品,但需要注明来源,禁止用于任何商业目的。 版本说明 Beta版 内容概要 本作品提供网页版和PDF版: 网页版:http://www.twinklingstar.cn/category/computational-geometry PDF版:https://github.com/twinklingstar20/Programmers_Computational_Geometry 本作品中介绍的绝大部分算法,都有与之相对应的C++源码实现: 源码:https://github.com/twinklingstar20/Programmers_Computational_Geometry 本作品包括九个章节,第1章主要介绍计算几何相关的数学概念,主要涉及向量和矩阵,例如在计算凸包的最小包围盒中就应用了矩阵的特征向量。第2、3、4、5章,分别介绍了几何中的四种基础图元:面、线、三角形和矩形,以及与之相关的计算几何算法。第6章介绍更复杂的图元:多边形,涉及点与多边形的关系判定、多边形类型判定等。第7章介绍旋转测径法,它能高效地解决计算凸多边形的宽、凸多边形间距离等问题。第8、9章分别介绍三维空间下的凸包算法和包围体相关的算法。 修改记录 由于作者能力有限,作品中定有缺点和错误,欢迎读者的批评指正,可以在个人网站留言或者发电子邮件,不胜感激。 网页版将会实时的更进并修改发现的错误,但PDF版的错误修改将需要较长的时间周期。 2016.10.06    发布Beta版,未经过严格校正的不稳定版本 个人信息 电子邮箱:zhangjianlong20@gmail.com 个人网站:www.twinklingstar.cn github:https://github.com/twinklingstar20 致谢 感谢胡凯博对第1章的审校,王莹对第3章的审校。 推荐书籍 推荐几本与计算几何相关的书籍: Philip J. Schneider, and David H. Eberly. Geometric Tools for Computer Graphics. Morgan Kaufmann,

spacer
浏览量:150

参考

       Joseph O'Rourke. "Finding minimal enclosing boxes." International journal of computer & information sciences, vol.14, no.3, pp.183-199, 1985.        David H. Eberly. 3D game engine design: a practical approach to real-time computer graphics. CRC Press, 2006.        Gill Barequet, and

spacer
浏览量:591

9.3. 包围球

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.3. 包围球 9.3.1. 最小包围球的创建 问题描述:给定一个点集\(S = \left\{ {{P_0},{P_1}, \cdots ,{P_{n - 1}}} \right\}\),求包围该点集的最小包围球。 早在1982年,Megiddo提出了第一个在三维空间下求最小包围球的线性算法,但是该算法实现难度较大。 Ritter(1990)提出了一种估计算法,该算法非常简单,但并不能得到最小包围球。主要思想是从点集\(S\)中,找到\(x\)值、\(y\)值、\(z\)值最小和最大的点,从这三组点对中找出距离最大的一组点对,取这组点对的中心作为球体的中心\(c\),取点对距离的一半作为球的半径\(r\)。接着,再次遍历点集\(S\),检查点\({{p}_{k}}\)与中心的距离\(d\),如果\(d\succ r\),说明点在球外,将半径更新为\(r'=(d+r)/2\),并将球心向该点移动\((d-r)/2\),即新的球心为\(c'=c+({{p}_{k}}-c)\cdot (d-r)/(2d)\),重复这个过程,直至点集\(S\)中所有的点都包含在球内。 Welzl(1991)提出了一种通过使用随机化的方法来解决问题,算法复杂度的期望是线性的,且算法相对简单、易实现。该算法不仅能得到二维、三维的最小包围球,而且能扩展到更高维的情况,通过“重要点前移”的优化步骤,能显著的提高算法的效率。Gärtner详细地描述了该算法的实现,并提供了C++的代码实现,在CGAL也有该算法的实现,本节将介绍该算法。 以三维空间下的最小包围球为例,定义\(\text{MB}\left( S \right)\)表示点集\(S\)的最小包围球,显然,\(\text{MB}\left( S \right)\)是唯一的。设\({{D}_{1}}\)和\({{D}_{2}}\)是点集\(S\)的两个最小包围球,半径都是\(r\),球心分别是\({{c}_{1}}\)和\({{c}_{2}}\)。有\(S\subset {{D}_{1}}\)且\(S\subset {{D}_{2}}\),所以有\(S\subset {{D}_{1}}\bigcap {{D}_{2}}\),\({{D}_{1}}\bigcap {{D}_{2}}\)被包含在以\(({{c}_{1}}+{{c}_{2}})/2\)为球心,\(\sqrt{{{r}^{2}}-{{a}^{2}}}\)为半径的球内,其中\(a\)表示两个球心距离的一半。若\(a\ne 0\),则存在半径更小的、包含点集\(S\)的球,与假设条件矛盾,因此\(a=0\),\({{D}_{1}}\)和\({{D}_{2}}\)是重合的。 设\(P,R\)是点集\(S\)的两个子集,且满足\(P \cup R = S,P \cap R = \emptyset

spacer
浏览量:925

9.2. 包围盒

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.2. 包围盒 9.2.1. 最小有向包围盒的创建 问题描述:给定一个点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),求包围该点集的最小有向包围盒。 通常这个问题可以简化为求凸多面体的最小有向包围盒问题,关于最小有向包围盒的创建方法有很多,O'Rourke在1985年提出了一种复杂度是\(O({{n}^{3}})\)的精确算法。包围盒在碰撞检测中有很重要的应用,为了提高效率,可以采用更高效的有向包围盒估计算法,评价最小有向包围盒估计算法有两个非常重要的指标:效率和紧密度,即要在尽可能短的时间内,创建出尽可能紧密的拟合点集的包围盒。Barequet和Har-Peled(2001)提出了两种估计算法,一种实现难度较大、复杂度是\(O(n+1/{{\varepsilon }^{4.5}})\)的算法(其中\(0\prec \varepsilon \le 1\)),另外一种相对较容易实现、复杂度是\(O(n\log n+n/{{\varepsilon }^{4.5}})\)的算法。而Gottschalk则提出了一种线性的估计算法,虽然不是最优拟合,但是紧密度上也表示很好,本节将介绍该算法。 首先计算出点集的三维凸包,参见第九章,可以得到\(n\)个三角形,记为\(\Delta {{p}^{k}}{{q}^{k}}{{r}^{k}},0\le k\prec n\),其中\({{p}^{k}}\)、\({{q}^{k}}\)、\({{r}^{k}}\)分别是三角形的3个顶点,三角形的面积记为\({{A}^{k}}\),凸包的整个面积就记作 \ 此外,三角形的质心记为\({{m}^{k}}=({{p}^{k}}+{{q}^{k}}+{{r}^{k}})/3\),也就是3个顶点的平均值,整个凸多面体的质心的加权平均值记为 \

spacer
浏览量:275

9.1. 包围体简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 9.1. 包围体简介 在计算机图形学与计算几何领域,包围体(Bounding Volume)就是指把自然物体包容起来的密闭空间。如图9.1所示,就是两类包围体:包围球和包围盒。通常,物体的空间结构比较复杂,需要有上百个顶点组成。如果需要判断两个物体是否发生碰撞,直接采用物体的结构来检测,会使计算量非常的大,而采用包围体,则可以有效的排除不相交的不重叠的情况,降低计算机的开销。 图9.1 包围体 包围体最主要的用途是降低碰撞检测的开销,评价包围体性能的好坏,可以依据如下几个指标: 创建开销; 紧密度; 相交测试; 内存占用性况; 是否容易旋转和变换; 如果一个包围体的创建开销越低,紧密度越好,相交测试简单,内存占用低,容易做旋转和变换,那么这种类型的包围体性能就越好。 常用的包围体有,轴对齐包围盒(AABB),有向包围盒(OBB),包围球,k-离散有向多面体(k-DOP)。其中,轴对齐包围盒创建较为简单,只要将物体的顶点沿着三维空间的3个坐标轴做投影,取得最小值和最大值即可。k-离散有向多面体是轴对齐包围盒的扩展,只要将物体的顶点沿着面的法向量\({{\vec{n}}_{i}}\)做投影,取得最小值和最大值即可创建出k-离散有向多面体。

spacer
浏览量:151

参考

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

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

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

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

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