Computational Geometry

浏览量:726

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

参考

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

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

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

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

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

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

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

参考

      Peter Schorn, and Frederick Fisher. "Testing the convexity of a polygon." Graphics Gems IV. Academic Press Professional, Inc., 1994.       Eric Haines. "Point in polygon strategies." Graphics Gems IV. Academic Press Professional, Inc., 1994.       Franco P. Preparata, and

spacer
浏览量:205

6.9. 简单多边形的凸包化

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.9. 简单多边形的凸包化 问题描述:将给定的简单多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)凸包化。 求给定点集的凸包的算法下限是\(O(n\log n)\),但是将简单多边形凸包化的算法复杂度是线性的。McCallum&Avis (1979)提出了第一个正确的、线性复杂度的算法,后来的学者进一步对这个问题进行研究,提出了更为简单、高效、易懂的算法,其中Melkman 在1987年提出的线性算法是最好的,因为该算法不考虑简单多边形的朝向,实现简单、高效,只使用一个双端队列即可。 图6.48 简单多边形\({\rm P}\)的凸包化 如图6.48所示,就是由一个简单多边形\({\rm P}\)凸包化得到的凸多边形\(CH({\rm P})\),显然,多边形\({\rm P}\)在\(CH({\rm P})\)内部,而且构成\(CH({\rm P})\)的点集是构成\({\rm P}\)的点集的子集。 接下来,详细介绍Melkman算法,该算法主要用到的数据结构是双端队列,可以表示为\(deque=\{{{d}_{bott}},\cdots ,{{d}_{top}}\}\),\(bott\)表示队列的底部,\(top\)表示队列的顶部,而且有\({{d}_{top}}={{d}_{bott}}\)。对队列有4种操作: \(deque.\operatorname{push}\_back(v)\),将元素\(v\)存入队列顶部,执行的操作是:\(top=top+1,{{d}_{top}}=v\); \(deque.\operatorname{pop}\_back()\),将顶部的元素弹出,执行的操作是:\(top=top-1\); \(deque.\operatorname{push}\_front(v)\),将元素\(v\)存入队列底部,执行的操作是:\(bott=bott+1,{{d}_{bott}}=v\); \(deque.\operatorname{pop}\_front()\),将底部的元素弹出,执行的操作是\(bott=bott-1\)。 函数\(\operatorname{ORIENTATION}({{v}_{0}},{{v}_{1}},{{v}_{2}})\)实现的功能是判断点\({{v}_{2}}\)是否在由\({{v}_{0}},{{v}_{1}}\)确定的直线的右侧,如果在,返回1;如果三点\({{v}_{0}},{{v}_{1}},{{v}_{2}}\)共线,返回0;否则,返回-1,伪码如下所示: \(\operatorname{ORIENT}({{v}_{0}},{{v}_{1}},{{v}_{2}})\) /* \({{v}_{0}},{{v}_{1}},{{v}_{2}}\)表示三个点 */ 1.    \(d=({{v}_{2}}-{{v}_{0}})\times ({{v}_{1}}-{{v}_{0}})\);

spacer