浏览量:111

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

参考

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

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

6.8. 线性对象与凸多边形的交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.8. 线性对象与凸多边形的交 Cyrus&Beck(1978)提出了一种判断直线与凸多边形相交测试的算法,该算法还可以解决三维空间上直线与凸多面体的相交测试问题,称之为Cyrus-Beck裁剪算法,Hill& Kelley(2008)中也有算法的描述,算法的复杂度为\(O(n)\)。 此外,针对凸多边形,可以应用二分查找,得到复杂度为\(O(\log n)\),判断直线与凸多边形的相交测试。 6.8.1. Cyrus-Beck裁剪算法 问题描述:线性对象\(L(t) = P + t\vec d\)与凸多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)的相交测试,设凸多边形逆时针顺序的。 如图6.42所示,线性对象不仅可以用参数方程的形式表示,而且还可以用法线形式来表示。设凸包上的一条边是,边上指向外侧的法向量是\(\vec n\),边所在的直线可用法线形式表示为: \ 把参数方程\(L(t)\)代入等式(6.13),得到: \

spacer
浏览量:304

6.7. 直线与凸多边形的距离

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.7. 直线与凸多边形的距离 问题描述:计算直线\(L(t) = Q + t \cdot \vec d\)与凸多边形\({\rm P} = \{ {V_0},{V_1}, \cdots ,{V_{n – 1}}\} \)的距离,设\({\rm P}\)是逆时针顺序且不存在连续的三个顶点共线的情况。 计算直线与多边形的距离,需要遍历多边形的每个顶点,时间复杂度是\(O(n)\),但对于凸多边形这种特殊情况,存在复杂度是\(O(\log n)\]的算法。 设\(d(L,{{V}_{i}})\)表示凸多边形上点\({{V}_{i}}\)与直线\(L\)的距离,其中\(0\le i\le n-1\),那么\({\rm P}\)与直线\(L\)的距离就可以表示为\(d(L,P)=\underset{0\le i\le n-1}{\mathop{min}}\,\left\{ d(L,{{V}_{i}}) \right\}\),就是找到\({\rm P}\)上与直线\(L\)距离最近的顶点。设与直线\(L\)垂直的方向是\(\vec{n}\),确保\({\rm P}\)上至少有一个顶点不在直线\(L\)由\(\vec{n}\)指向的一侧,那么与直线\(L\)最近的顶点,就是凸多边形\({\rm P}\)沿着方向\(\vec{n}\)的极点,如图6.41所示,\({{V}_{\max }}\)就是沿着方向\(\vec{n}\)的极点。将向量\(\vec{d}\)沿着逆时针方向旋转90。,就得到与它垂直的向量\(\vec{n}=\left( -{{{\vec{d}}}_{y}},{{{\vec{d}}}_{x}} \right)\)。若\(\vec{n}\cdot \left( {{V}_{0}}-Q

spacer
浏览量:197

6.6. 凸多边形的极点

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.6. 凸多边形的极点 问题描述:给定一个凸多边形\(P=\{{{V}_{0}},{{V}_{1}},\cdots ,{{V}_{n-1}}\}\),求\(P\)沿着方向\(\vec{d}\)上的极点,设\(P\)是逆时针顺序且不存在连续的三个顶点共线的情况。 对于任意一个点集和方向,通过测试每个点,可以在线性时间内得到。但对于凸多边形这种特殊的情况,它沿着任意一个方向,都是一个单调多边形,可以分成两条单调的多边形链,可以应用二分搜索的思想,在时间内找到极点。 图6.38 凸多边形上的顶点投影到方向是\(\vec{d}\)的直线上 为了后面的算法论述,先对一些概念进行介绍。如图6.38所示,直线\(L\)所在的方向是\(\vec{d}\),把\(P\)上的顶点都投影到直线上,所有的投影点都介于\(\left\)之间,则顶点\({{V}_{\min }}\)和顶点\({{V}_{\max }}\)分别称为凸多边形沿着方向\(\vec{d}\)的最小极点和最大极点。若点\(,\({{V}_{a}}\)在\({{V}_{b}}\)的下方。图6.38中,相对于\(\vec{d}\),\({{V}_{i}}\)在\({{V}_{j}}\)的上方,\({{V}_{i}}\)在\({{V}_{i+1}}\)的下方。若凸多边形\(P\)上的边\(e={{V}_{a+1}}-{{V}_{a}}\),有\(\vec{d}\cdot e\succ 0\),就称\({{V}_{a}}\)相对于方向\(\vec{d}\)是正向延伸;相反,若\(\vec{d}\cdot e\prec 0\),就称\({{V}_{a}}\)相对于方向\(\vec{d}\)是负向延伸的,在不会引起歧义的情况下,可以简称为正向延伸和负向延伸。图6.38中,顶点\({{V}_{i}}\)是正向延伸的。 针对这个问题,最容易想到的一种算法是测试每个顶点到方向\(\vec{d}\)上的投影距离,取得距离最小的顶点和最大的顶点,算法复杂度是\(O(n)\),这种朴素算法的伪码如下所示: 给定一个凸多边形\(P=\{{{V}_{0}},{{V}_{1}},\cdots ,{{V}_{n-1}}\}\),求\(P\)沿着方向\(\vec{d}\)上的最大极点,设\(P\)是逆时针顺序。 1.    min = max = 0; 2.    for( i = 0 ; i < n

spacer
浏览量:334

6.5. 点与多边形的关系

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.5. 点与多边形的关系 Haines Eric(1994) 详细地总结各种点与简单多边形关系的判定算法,并测试了不同算法的性能。判定点与一般的简单多边形关系的算法,有交叉法(Crossings Test),角度累积法(Angle Summation),增量角度法(Incremental Angle),三角扇法(Triangle Fan),栅格法(Grid Method),基于像素的测试法(Pixel Based Test)。其中,速度最快的是栅格法,但是它需要预处理操作,并且对内存的需求特别大。 判定点与凸多边形关系,同样有很多种方法,最容易想到的一种方法就是判断点是否在凸多边形每条边的外侧,只要存在一条这样的边,就可知点就在凸多边形外,否则,在凸多边形内。这种方法的复杂度是\(O(n)\),而Schneider et al(1985)描述了一种基于二分查找的算法,时间复杂度是\(O(\log n)\),是最快的判定算法。 对于点与简单多边形关系的判定问题,本小节将重点介绍交叉法和增量角度法,两种算法的思路完全不同,但是性能相当。对于点与凸多边形关系的判定问题,本小节将介绍基于二分查找的算法。 6.5.1. 交叉法 问题描述:判定点\(Q\)与简单多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)的关系,其中\({{V}_{i}}=({{x}_{i}},{{y}_{i}})\),设简单多边形是逆时针顺序。 它是基于射线与边交点个数的奇偶性来判定的,基本思想是:由待判定点\(Q\),沿任意一个方向做一条射线,求出射线与多边形的交点个数,若交点个数是奇数,则点在多边形内,若是偶数,则在多边形外。如图6.30所示,点\({{Q}_{1}}\)在多边形外,由它引出的射线与多边形边有4个交点,交点个数是偶数;点\({{Q}_{2}}\)在多边形内,由它引出的射线与多边形边有1个交点,交点个数是奇数。为了算法的简便,射线的方向通常取(1,0)或者是(0,1)。 图6.30 根据射线和多边形边交点个数的奇偶性,判定点与多边形的关系 由待检测点引出的射线,可能经过多边形的顶点,或者与多边形的边发生重合。如图6.30所示,若\({{Q}_{2}}\)引出的射线经过顶点\({{V}_{3}}\),则计算交点时,射线与边\(\overline{{{V}_{2}}{{V}_{3}}}\)和边\(\overline{{{V}_{3}}{{V}_{4}}}\)都相交,交点个数是2,由此得出的结论“点\({{Q}_{2}}\)在多边形外”是错误的。O’Rourke (1998)介绍了一种解决方案,以待测试点为原点,方向是(1,0)作一条射线,求它与多边形的交点个数。对相交点的计数作如下限制:(1)若多边形一条边的一个端点严格位于射线之上,另一个端点严格位于射线之下,相交点个数加1;(2)与射线重合的边,直接忽略不计;(3)一条边位于射线之上,它的一个端点在射线上,相交点个数不变;(4)一条边位于射线之下,它的一个端点在射线上,相交点个数加1。 如图6.31所示,初始情况下,相交点计数值\(n=0\),经过点\({{V}_{15}}\),边\(\overline{{{V}_{15}}{{V}_{16}}}\)在射线上,计数值不变;边\(\overline{{{V}_{14}}{{V}_{15}}}\)与射线重合,忽略;经过点\({{V}_{14}}\),边\(\overline{{{V}_{13}}{{V}_{14}}}\)在射线下方,计数值加1,得\(n=1\);经过点\({{V}_{11}}\),边\(\overline{{{V}_{11}}{{V}_{12}}}\)在射线下方,计数值加1,得\(n=2\);依次类推,最终得到的计数值为\(n=5\),是一个奇数,判定点\(Q\)在多边形内。 设射线的原点是\(Q\)、方向是(1,0),边为\(\overline{{{V}_{i}}{{V}_{i+1}}}\),如何判断射线与边的关系呢?若边\(\overline{{{V}_{i}}{{V}_{i+1}}}\]的两个端点在\(Y\)轴上的分量大于\({{Q}_{y}}\)或者小于\({{Q}_{y}}\),则射线与边\({{V}_{i}}{{V}_{i+1}}\)一定不相交。否则,射线与边可能相交。边可以用参数方程表示为\(L(t)={{V}_{i}}+t({{V}_{i+1}}-{{V}_{i}}),0\le t\le 1\)。射线与边相交,设交点是\(T\],则交点\(Y\)轴上的分量是\({{T}_{y}}={{Q}_{y}}\),则有\({{Q}_{y}}={{y}_{i}}+t({{y}_{i+1}}-{{y}_{i}})\),因此可以解得 \

spacer
浏览量:273

6.4. 多边形的面积

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.4. 多边形的面积 本节介绍二维和三维多边形面积的计算公式和几何推导方法,针对三维多边形的面积计算,有多种算法,比如三角形分解法、四边形分解法、投影法,本节只介绍三角形分解的方法,并给出相应的计算公式。 6.4.1. 二维空间 问题描述:求二维空间上的多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)的面积,其中,\({{V}_{i}}=({{x}_{i}},{{y}_{i}})\)。 二维空间上的多边形\({\rm P}\)的面积通过等式(6.3)计算: \ 图6.26 逆时针方向排序的多边形 接下来,推导下等式(6.3),从几何的角度考虑,设多边形是按照逆时针方向进行排序的,如图6.26所示,\(O\)表示原点,则多边形的面积可以表示为: \

spacer
浏览量:598

6.3. 多边形判定

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.3. 多边形判定 判断一个多边形是否是简单的,关键在于怎么判断多边形的边是否存在自相交,Shamos-Heoy(1976)提出了一种复杂度为\(O(n\log n)\)判断线段集是否存在相交的算法,可应用于判定一个多边形是否是简单的,可以采用第四章的Shamos-Hoey算法。判断一个简单多边形是否是单调的,Preparata&Supowit(1981)提出一种最优的性线复杂度的算法。判断一个多边形是否是凸的,如果先判断多边形是否是简单的,再判断是否存在大于180度的内角,算法需要\(O(n\log n)\)的时间,但Schorn& Fisher (1994)提出了一种最优的线性算法。 本小节将会介绍简单多边形的单调性和多边形的凸性判定算法。 6.3.1. 简单多边形的单调性 问题描述:判定二维空间上的简单多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)是否是单调的,设简单多边形是逆时针顺序的。 图6.20 边与边的夹角 我们这里规定,边\({{e}_{0}}\)与边\({{e}_{1}}\)的夹角记为\(({{e}_{0}},{{e}_{1}})\),它的绝对值小于180度,如图6.20所示(a),边\({{e}_{1}}\]在边\({{e}_{0}}\)的逆时针方向,则边\({{e}_{0}}\)与边\({{e}_{1}}\)的夹角大于0度,即\(({{e}_{0}},{{e}_{1}})\succ 0\);如图(b)所示,边\({{e}_{1}}\)在边\({{e}_{0}}\)的顺时针方向上,夹角小于0度,即\(({{e}_{0}},{{e}_{1}})\prec 0\)。 设多边形的边\({{e}_{i}}=\overline{{{V}_{i}}{{V}_{i+1}}}\),令\({{C}_{0}}=\left( (1,0),{{e}_{0}} \right)\),\({{C}_{k}}=\sum\limits_{i=1}^{k}{({{e}_{i-1}},{{e}_{i}})},1\le k\le n-1\),称\({{C}_{k}}\)就是边\({{e}_{k}}\)的极角坐标,在极角坐标\({{C}_{i}}\)与\({{C}_{j}}\)之间会形成一个扇形区域,极角坐标\({{C}_{i}}\)沿着逆时针方向旋转至\({{C}_{j}}\)的扇形区域记为\(({{C}_{i}},{{C}_{j}})\)。 图6.21 简单多边形和它对应的极角坐标图 如图6.21示,图(a)是多边形\({\rm P}\),图(b)是它对应的极角坐标图。对于极角坐标图,我们可以想像为初始情况下有一条边\({{e}_{0}}\),把它看成类似于手表上的指针一样的有向向量,将它沿逆时针旋转角度\(\left\| ({{e}_{0}},{{e}_{1}}) \right\|\)至边\({{e}_{1}}\)的极角坐标\({{C}_{1}}\),再顺时针旋转角度\(\left\| ({{e}_{1}},{{e}_{2}}) \right\|\)至边\({{e}_{2}}\)的极角坐标\({{C}_{2}}\),依次类推,直至完成所有夹角的旋转,形成完整的极角坐标图。也可以换一个角度理解极角坐标图,它相当于把多边形上的每条边看成向量,将它们的起始位置移至顶点\({{V}_{0}}\)。显然,极角坐标将\(

spacer
浏览量:1,141

6.2. 多边形生成算法

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 6.2. 多边形生成算法 6.2.1. 生成算法综述 随机多边形的生成主要有两个应用:a)测试算法的正确性;b)评估算法耗费的CPU时间。为了能评估算法的正确性,输入的数据应尽可能的分散,使得算法的每一个分支都得到执行,这也有利于算法效率的有效评估。但实际上,我们经常很难获得大量有效的输入数据来测试,因此随机多边形的生成算法就显得非常的必要。 给定一个点集,求由它们组成的均匀分布的简单多边形是一个NP难问题,至今还没有找到多项式级别的算法,但对某些特殊的多边形,存在有多项式级别的算法。我们也可以采用启发式的方法,在可以接受的时间范围内生成丰富多样的非均匀分布的简单多边形。这里先介绍下非均匀分布的概念,设存在\(n\)个点的点集,总共能生成\(m\)种简单多边形,均匀分布的简单多边形生成算法是指这\(m\)种简单多边形都会有一定概率被生成,但非均匀分布的生成算法,只能生成其中的\(k(k\prec m)\)种。 针对随机星状多边形的生成算法,早在1988就Linda&hute就提出了一种\(O({{n}^{5}})\)的生成算法,Sohler(1999)提出了另一种时间复杂度更低的生成算法,达到\(O({{n}^{2}}\log n)\),Auer& Held(1996)提出了两种星状多边形的生成算法,一个算法复杂度是\(\text{O(}{{\text{n}}^{5}}\log n)\),和前面两种算法类似,实现难度较大,另外一个算法简单易实现,但不能保证生成的星状多边形可能是非退化的,称它为快速星状生成算法,复杂度是\(O(n\log n)\),本节将会详细地描述快速星状生成算法。 针对随机单调多边形的生成算法,Zhu et al(1996)提出了一种通过上顶点链表和下顶点链表,生成随机的X单调多边形,算法的复杂度是\(O(n)\),但是需要\(O({{n}^{2}})\)的预处理时间。本小节将会详细地描述另外一种更简单的生成算法,可以生成任意直线方向上的单调多边形。 针对随机凸多边形的生成算法,一种很简单的方法,就是随机生成一组点,通过凸包算法,求出包围点集的凸多边形。但是,这种方法会造成的一个问题是:随机生成10000个点数据,最终得到的凸包可能只有100个顶点,甚至于更少。Devillers et al(2014)提出了一种生成在同一个圆盘上的凸多边形,本节将介绍一种更简单的基于圆盘的凸多边形生成算法。 针对随机简单多边形的生成算法,由于无法在多项式时间内生成均匀分布的简单多边形,但是我们可以通过启发式的方法,生成非均匀分布的简单多边形。Auer&Held(1996)提出了多种启发式的方法,包括稳定增长法(Steady Growth)、空间分割法(Space Partition)、两步移动法(2-opt Moves),复杂度分别是\(O({{n}^{2}})\)、\(O(n\log n)\)和\(\text{O(}{{\text{n}}^{4}}logn)\)。此外,Dailey& Whitfield(2008)提出了一种\(O({{n}^{2}}\log n)\),类似于Koth曲线的构造,使用到多边形三角剖分算法。本节将介绍稳定增长法、两步移动法、和空间分割生成算法。 6.2.2. 星状多边形的生成算法 问题描述:随机生成不重合的\(n\)个点的点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),由该点集生成一个逆时针顺序的星状多边形。 随机确定一个点\(P\),要求点\(P\)在点集\(S\)所确定的凸包内,可知点集\(S\)的中心,一定在凸包内,即 \

spacer