浏览量:726

8.1. 凸包简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

8.1. 凸包简介

二维的多边形的英文表示是Polygon,二维的凸包称为凸多边形,三维的多面体英文表示是Polyhedron,三维的凸包称为凸多面体。二维的多边形和三维的多边形都可以称为多胞体,多胞体的英文表示是Polytope,多胞体是任意维度上的几何对象的泛化表述。

凸多胞体有很多重要的应用,比如碰撞避免、计算最小包围盒[2]等问题,在不同的应用背景下也会有不同的定义方法,这里提供两种凸多胞体的定义:顶点定义法和半空间交定义法。此外,也简单介绍些与凸包问题相关的概念。

概念一. 顶点定义法

给定\({{R}^{n}}\)空间上的有限点集\(S\),由点集中有限个极点(Extreme Point)构成的凸对象(Convex Object),就称为凸多胞体。

极点就可以看成是多胞体的顶点,以二维多边形为例,极点就相当于凸多边形的顶点。使用严格的数学定义来说,极点是指那些不能由凸多胞体内的其它点的凸组合(Convex Combination)表示出来的点。给定点\({{x}_{1}},\cdots ,{{x}_{k}}\)\(k\)个点,它的凸组合可以用下面的等式表示:

\[{a_1}{x_1} + ... + {a_k}{x_k},{a_i} \ge 0,{a_1} + ... + {a_k} = 1 \tag{8.1}\]

一条线段就是它的端点的所有的凸组合,三角形就是它的三个顶点的凸组合,一个四面体是它的四个顶点的凸组合。

2015-3-24 9-44-27

图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}\)不是凸的。

概念二. 半空间交定义法

一个凸多胞体可以表示成有限个半空间(Half Space)相交的密闭空间。

先解释下什么叫半空间,例如在二维空间下,一条直线可以把平面分成两半,这两半就可以称为半空间,在三维空间下,一个平面可以把空间分成两半,这两半也就是两个半空间,在更高的维度下也可以有类似的表示。把\({{R}^{n}}\)空间分成两半的平面称为超平面,例如二维的直线和三维的平面,都可以称为超平面。超平面\(\Gamma \)可以表示成如下形式:

\[\Gamma :{a_1}{x_1} + {a_2}{x_2} + .... + {a_n}{x_n} = b \tag{8.2}\]

由超平面\(\Gamma \)划分成的半空间可以用线性不等式来表示,等式(8.3)就是其中一个半空间的公式表示:

\[{a_1}{x_1} + {a_2}{x_2} + .... + {a_n}{x_n} \le b \tag{8.3}\]

如果\(m\)个半空间形成一个封闭(Closed)的空间,该空间就是一个凸多胞体。\(m\)个半空间,用\(m\)个线性不等式表示,形成一个线性不等式组如下所示:

\[\left\{ \begin{array}{l}{a_{11}}{x_1} + {a_{12}}{x_2} + .... + {a_{1n}}{x_n} \le {b_1}\\{a_{21}}{x_1} + {a_{22}}{x_2} + .... + {a_{2n}}{x_n} \le {b_2}\\.............................................\\{a_{m1}}{x_1} + {a_{m2}}{x_2} + .... + {a_{mn}}{x_n} \le {b_m}\end{array} \right. \tag{8.4}\]

2015-3-24 9-44-39

图8.2 凸多边形\({\rm P}\)的空间交定义

二维空间下的超平面的几何表示就是一条直线,如图8.2所示,多边形\({\rm P}\)中的每一条边所在的直线可以把平面分成两个半空间,由5个超平面\({{\Gamma }_{i}},1\le i\le 5\)划分的半空间的交就形成凸多边形\({\rm P}\)

概念三. 面(Facet)的定义

\({\rm P}\)是在空间\({{R}^{n}}\)上的一个凸多胞体,凸多胞体可以表示成多个半空间的交,分割半空间的超平面可以用等式(8.2)表示,则凸多胞体\({\rm P}\)的面用数学形式可以表示为:

\[F = P \cap \{ x:a \cdot x = b\} \tag{8.5}\]

凸多胞体\({\rm P}\)的面的维度是\(n-1\),例如凸多面体的面是二维的。

概念四. 岭(Ridge)的定义

一个面的边界,就称为岭,岭表示的是两个面的邻接(Adjacency)部分,相当于是两个相邻面的交。对于空间\({{R}^{n}}\)上的面的维度是\(n-1\),那么岭的维度就是\(n-2\)。在三维空间上,多面体的面通常用三角形面片来表示,岭就是指三角形面片上的边。

概念五. 欧拉公式

在三维空间下,\(V,E,F\)分别表示多面体的顶点数、边数、面数,则有下面的等式成立,O'Rourke[1](1998)对欧拉公式的证明做了详细的论述。

\[V - E + F = 2 \tag{8.6}\]

概念六. 正则多胞体

正则多边形,指每个边长度一样,每个内角相等的多边形,例如等边三角形,正方形等,显然有无数个正则多边形。

2015-3-24 9-44-51

图8.3 五种正多面体,从左到右分别是正四面体、正六面体、正八面体、正十二面体、正二十面体

正则多面体,指各个面都一样且每个面有相同的内角的多面体,比如每个面都是正三角形、正五角形、五六角形等。正则多面体,也称为柏拉图立体(Platonic Solids),经证明只有5个这样的多面体,分别是正四面体、正六面体、正八面体、正十二面体、正二十面体,这些正则多面体的顶点、边、面信息如表8.1所示,它们的形状如图8.3所示,O'Rourke[1](1998)中详细证明了有且只有5个正则多面体。

正则多边形和正则多面体都可以统称为正则多胞体。

表8.1 五种正多面体的顶点、边和面信息

2015-3-24 9-45-07

spacer

Leave a reply