类双曲壳的概念及算法

陈述平， 汪 扬， 宋萃娥

（1. 东北大学机械学院，辽宁 沈阳 110004；2. 辽宁石油化工大学机械学院，辽宁 抚顺 113001）

凸壳是计算几何研究的对象[1]。迄今为止，已有很多凸壳算法被提出来，并被广泛地应用于其它学科领域[2-3]。凸集和凸壳的扩展问题，有人曾在非欧几何的有关流形的研究中提到过[4-5]。通过使任意两点的“直线段”都在集合内的定义，凸壳和凸集很自然的被拓展到非欧几何中[6]。J. de Groot 和H. de Vries 曾对射影空间中RPn的凸集问题作过研究[4]，暗示射影平面RP2中的凸壳是有可能通过无穷远直线L∞。在有向射影几何的提法出现后[7]，Matthew T. Mason 明确的提出外部线作为通过无穷远直线L∞的凸性[8]。而Jorge Stolfi 认为在经典射影空间当中，由于不可定向平面和含糊的线段定义，凸是没有意义的[7]。为了更好的在齐次坐标系中分析从经典凸壳到类双曲壳的射影变换就要避免Jorge Stolfi 提到的不利条件。运用拓扑同胚同时借助于在有向射影几何的正平面T2上可定向的优势，来帮助提出射影凸集和凸壳的概念[9]。对于类双曲壳研究的初衷就是为了研究凸壳外部同时在两个方向都可视的区域[10]。并且，将提出一个在欧氏平面E2上的实时凸壳构造算法，它的复杂度不一定是最低，但是它提供了一种在两个区域中间寻找直线簇的可能性。

1 射影平面中的类双曲壳

1.1 射影平面中的凸集

为了提出射影平面中的凸的概念，提出下列定义框架[4-5]：

定义1 RP2的子集B 被称为半凸，如果满足任意给出子集B 中两个点P1和P2，存在以P1和P2为端点的线段Ls(P1, P2)，且Ls(P1, P2)也被包含于子集B 中[4]。

定义2 RP2的子集B 被称为凸，如果满足任意给出子集B 是半凸，并且B 不包含一条直线L(P1, P2)=P1∨P2。也可以这样定义：RP2的子集B 被称为凸，有且只有子集B 中任意两点P1和P2唯一被以P1和P2为端点且也被包含于子集B的线段Ls(P1, P2)所连接[4]。

定义3 RP2的子集B 的凸壳是在RP2上包含B 的最小凸集。

定义4 RP2上凸壳CH(B)中的点P 被称为顶点，当且仅当它不是凸壳CH(B)中任意线段的内点。这个线段有可能穿过无穷远直线L∞。

定义5 RP2上凸壳的边界∂CH(B)是包含子集B 最小的凸区域的边缘。

1.2 射影平面中类双曲壳的概念

在实平面R2上点集B 的凸壳可以被想象成为包围住给定物体的皮筋。而在射影平面RP2上，如果凸壳本身不通过无穷远直线L∞，它在形态上依旧如同在实平面R2上的凸壳。在本文当中，类双曲壳的概念是想象点集B 穿越无穷远直线L∞的情形。

定义6 类双曲壳(PHH(B))是通过无穷远直线L∞的子集B 的凸壳。

定义7 RP2上PHH(B)的内部是同胚于R2上的圆，且被凸壳边界∂PHH(B)所包围的区域[9]。

定义8 RP2上PHH(B)的外部是同胚于不可定向的默比乌斯带，且被凸壳边界∂PHH(B)所包围的区域[9]。

在实射影平面上，平面是双连通的。因此，一条线不能分割平面；需要两条线才能把平面分割为Region I 和Region II[11]（见图1）。根据上面的定义，Region I 不是凸而是半凸，因为存在通过P1的完整的直线。比较图2 中的Region I不只是凸，也是RP2上最简单的类双曲壳。

图1 两直线分割平面为Region I 和Region II

图2 Region I 和顶点P1, P2, P3 简单的类双曲壳

定义9 PHH(B)临界支撑线是两条直线，满足：把RP2平面分割为Region I 和 Region II（见图2），并且PHH(B)属于Region I；同时Region I不包含不于PHH(B)有任何交点的完整直线。

在图2 中，临界支撑线是P1P2和P1P3。图2中Region I 中的∂PHH(B)是一个被L∞分割成两半的闭环。因为，每一对无穷远对跖点都是同一个点，类双曲壳的内部是一个拓扑圆，而图2 中没有灰色的部分同胚于默比乌斯带[9]。同时，凸壳边界同调于0，因此包围了一个区域。注意到类双曲壳的边界∂PHH(B)也是默比乌斯带的边缘。

2 有向射影空间中的类双曲壳

类双曲壳和经典凸壳的等价问题在图3 中表示出来：类双曲壳可以通过将通过经典凸壳内的直线L 投影到无穷远直线L∞得到。

图3 将通过无穷远直线L∞的经典凸壳 投影到有向射影平面T2 的正平面

T2上的射影变换φ，对应于3×3 射影变换矩阵A，并且满足等式

等式gx+hy+1=0 是将被映射到无穷远直线L∞的直线L。所有点都表示成齐次坐标：Pi=[xi, yi, 1]T。有向射影平面T2的一个优点就是它允许永久性的定义平面上一条直线的两边[7]。δi=gxi+hyi+1 的正负号表示了直线的左右边。

为了简化符号，表示对角矩阵为diag，计算行列式为det，表示正负性为sign。三种关系记为

对于任意实数x：若x=0, sign(x)=0; 若x＞0, sign(x)=1; 若x＜0, sign(x)=-1。

2.1 变换矩阵A

矩阵A 有8 个变量，所以它应该能够匹配四对点。在图4 中给出8 个点P1, P2, P3, P4, P1′, P2′, P3′, P4′。其中P1, P2, P3, P4是经典凸壳在正平面上逆时针方向且没有三点共线的顶点；P1′, P2′, P3′, P4′满足P1′=P1, P2′=P2, P3′=P4, P4′=P3，是类双曲壳在正平面上没有三点共线的顶点。P1和P2是两个相邻顶点，P3和P4也是两个相邻顶点。

命题1 存在唯一3×3 的射影变换矩阵A 将无三点共线的逆时针排列点P1, P2, P3, P4映射到满足P1′= P1, P2′=P2, P3′=P4, P4′=P3关系的P1′, P2′, P3′, P4′

A=δ4[P1, P2, P4]•diag[1/(λ1+λ2-1), 1/(λ1+λ2-1),

其中 λ1, λ2|0＜λ1＜1, λ2＜0。同时可以推演出

图4 以在正平面上逆时针方向 P1, P2, P3, P4 为顶点的经典凸壳

证 明建立方程组

∵等式(1) δiPi′=APi成立，同时∵P1, P2, P3, P4逆时针排列，且无三点共线

∴ λ1, λ2|0＜λ1＜1, λ2＜0表示为方程(4)的唯一解

∵等式(4)成立

∴AP4=A•[P1, P2, P3]•[λ1, λ2, 1-λ1-λ2]T=[P1, P2, P4]•

∴δ4P3=δ4[P1, P2, P4]•[λ1/(λ1+λ2-1),

∵等式(1),等式(5)和等式(6)成立

∴diag[δ1, δ2, δ3]•[λ1, λ2, 1-λ1-λ2]T=

∵等式(1)和等式(7)成立

假设布尔函数具有n个输入变量{xi|1in}、m个输出变量{fo|1om}，输入变量xi也被称为原始输入(Primary Input,PI)和PI信号，输出变量fo也被称为原始输出(Primary Output,PO)和PO信号.其关于PI的MPRM逻辑表达式如式(1)所示.

同时∵P1, P2, P3, P4逆时针排列，且无三点共线

∴det([P1, P2, P4])＞0 and det([P1, P2, P3]-1)＞0

∵等式(2)成立

∴det(A)=δ4•det([P1, P2, P4])•det(diag(1/(λ1+λ2-1), 1/(λ1+λ2-1), 1/(λ1+λ2-1)2))•det([P1, P2, P3]-1)

∴sign(det(A))=sign(δ4)

证毕，命题1 中等式(2), 式(3)成立。

2.2 无穷远直线的反象

命题2 上述讨论的矩阵A和从P1, P2, P3, P4到P1′, P2′, P3′, P4′的映射关系，唯一决定L∞的反象L，L与线段P4P1和P2P3内部相交。见图5和图6。

证 明∵已知等式(2)唯一决定射影变换矩阵A，同时等式gx+hy+1=0指示将被映射到无穷远直线L∞的直线L。注意到直线法向量系数[g, h, 1]正是射影变换矩阵A第三行元素。

∵不失一般性对A•[P1, P2, P3]讨论δi的正负关系：

∵等式(8)成立

∵前 面 已 知0＜λ1＜1, λ2＜0, 简 单 加 减 有：

因为δi=gxi+hyi+1的正负性表示了直线L的左右不同边。所以P3和P4在直线L同一边，P1和P2在L不同于P3和P4的另一边。因此，能够判断出直线L通过线段P4P1和P2P3内部，命题2证毕。

图5 L 将经典凸壳分割为Region I 和II

图6 Region I 和II 的以P1′P4′和P2′P3′ 为临界支撑线的类双曲壳

2.3 顶点序列的走向

命题3 L∞的反象L 将经典凸壳分为Region I和Region II。对于邻接顶点Pi, Pj, Pk一开始在经典凸壳的Region I 逆时针方向排列，在射影后其相应点Pi′, Pj′, Pk′仍然为逆时针排列。相反，对于邻接顶点Pr, Ps, Pt一开始在经典凸壳的Region II 逆时针方向排列，在射影变换后其相应点Pr′, Ps′, Pt′为顺时针排列。

证 明自明的，∵Pi, Pj, Pk逆时针排列，∴det([Pi, Pj, Pk])＞0；同时Pi, Pj, Pk都和P4一样在Region I, ∴sign(Pi)=sign(Pj)=sign(Pk)=sign(δ4)≠0。

∵等式(1) δiPi′=APi成立

∴[Pi′, Pj′, Pk′]•diag[δi, δj, δk]= A•[ Pi, Pj, Pk]

∵等式(3) sign(det(A))=sign(δ4)成立

∴sign(det[Pi′, Pj′, Pk′]) = sign(det(A•[ Pi, Pj, Pk] •[1/δi, 1/δj,1/ δk]))=sign(δ4) •1•sign(δ4)＞0

上式说明，Pi′, Pj′, Pk′逆时针排列。

同理证明Pr, Ps, Pt在Region II, 必然存在det([Pr, Ps, Pt])＞0同时sign(Pr)=sign(Ps)=sign(Pt)= -sign(δ4)≠0

sign(det[Pr′, Ps′, Pt′]) = sign(det(A•[Pr, Ps, Pt] •[1/δr, 1/δs,1/ δt]))=sign(δ4) •1•(－sign(δ4))＜0。

上式说明，Pr′, Ps′, Pt′顺时针排列。命题3证毕。

2.4 区域的投影

命题4 射影变换φ把经典凸壳中的Region I和Region II 相应的映射到类双曲壳的Region I和Region II（如图5 和图6 所示）。

证 明对于经典凸壳Region I 中任意逆时针邻接顶点Pi和Pj以及Region I 中任意点PI，必然满足

同时∵Pi, Pj, PI和P4一样都在Region I 中。

∴sign(Pi)=sign(Pj)=sign(PI)=sign(δ4)≠0

下面着重讨论det[Pi′, Pj′, PI′]的正负性：

∵等式(1) δiPi′=APi成立

∴[Pi′, Pj′, PI′]•diag[δi, δj, δI]= A•[ Pi, Pj, PI]

∵等式(3) sign(det(A))=sign(δ4)成立

∴(det[Pi′, Pj′, PI′]) = sign(det(A•[Pi, Pj, PI] •[1/δi, 1/δj, 1/δI]))=sign(δ4) •sign(det[Pi′, Pj′, PI′])• sign(δ4)≥0

也就说，任何经典凸壳Region I中的点将被映射到类双曲壳PHH(B)的Region I中。

同理可证，对于经典凸壳Region II中任意逆时针邻接顶点Pm, Pn以及Region II中任意点PII, 有类似结论。所有任意Region II中点将被映射到PHH(B)的Region II中。

所以命题4 证毕。

综上所述，可以得出另一个结论，由于一对一的射影变换，PHH(B)是最小的凸区域。

3 类双曲壳边界的实时构造算法

3.1 顶点的性质

假设∂PHH(B)被存储在双向链表当中，DL_I和DL_II 分别保存了Region I 中逆时针方向的顶点序列和Region II 中顺时针方向的顶点序列。则可以按照两个原则增量添加类双曲壳中的点：

（1） 任意Region I 中的点都在直线DL_ I[i]→DL_I[i+1]的左边，且在直线DL_II[i]→ DL_ II[i+1]左边；

（2） 任意Region II 中的点都在直线DL_ I[i]→DL_I[i+1]的右边，且在直线DL_II[i]→ DL_ II[i+1]右边。

3.2 确定类双曲壳边界步骤

利用3.1 的原则，确定∂PHH(B)步骤如下：

（1） 输入代插入点的P(Belong)的坐标和归属区域(I 或II)。判定P(Belong)实际所在图7中所在区域。

图7 ∂PHH(B)和支撑线分割平面为 Region I, II, III, IV, V, and VI

1） If P(I) ∈Region I, goto Step 10;

2） If P(I) ∈Region II, return failure;

3） If P(I) ∈Region III, goto Step 2;

4） If P(I) ∈Region IV, goto Step 3;

5） If P(I) ∈Region V, goto Step 4;

6） If P(I) ∈Region VI, goto Step 5;

7） If P(II) ∈Region I, return failure;

8） If P(II) ∈Region II, goto Step 10;

9） If P(II) ∈Region III, goto Step 6;

10） If P(II) ∈Region IV, goto Step 7;

11） If P(II) ∈Region V , goto Step 8;

12） If P(II) ∈Region VI, goto Step 9。

（2） 在DL_I 中向前搜索到位置i 满足：det[DL_I[i], DL_I[i+1], P(I)]≤0，同时继续向前搜索到位置 j 满足 det[DL_I[j], DL_I[j+1], P(I)]＞0。然后，在DL_I[i]后插入P(I)，同时删除从DL_I[i+1]到DL_I[j-1]的节点。返回第10 步。

（3） 删除DL_I 中所有的现存数据，同时使P(I)作为DL_I[first]；在DL_II 中向前搜索到位置i 满足：det[DL_II[i], DL_II[i+1], P(I)]≥0，同时向前搜索到位置 j 满足 det[DL_II[j], DL_II[j+1], P(I)]＜0。然后，删除DL_II[i]前和DL_II[j]后的节点。返回第10 步。

（4） 在DL_I 中向前搜索到位置i 满足：det[DL_I[i], DL_I[i+1], P(I)]＞0，同时在DL_II 向后搜索到位置j 满足det[DL_II[j], DL_II[j+1], P(I)]≥0。然后，删除DL_I[i]前和DL_II[j+1]后的节点。同时在 DL_I[i]前插入P(I)。返回第10步。

（5） 在DL_I 中向后搜索到位置i 满足：det[DL_I[i], DL_I[i+1], P(I)]≥0，同时在DL_II向前搜索到位置j 满足det[DL_II[j], DL_II[j+1], P(I)]≥0。然后，删除DL_I[i]后和DL_II[j+1]前的节点。同时在DL_I[i]后插入P(I)。返回第10步。

（6） 在DL_II 中向前搜索到位置i 满足：det[DL_II[i], DL_II[i+1], P(II)]≥0 同时继续向前搜索到位置 j 满足 det[DL_II[j], DL_II[j+1], P(II)]＜0。然后，在DL_II[i]后插入P(II)，同时删除从DL_II[i+1]到DL_II[j-1]的节点。返回第10步。

（7） 删除DL_II 中所有的现存数据，同时使P(II)作为DL_II[first]；在DL_I 中向前搜索到位置i 满足：det[DL_I[i], DL_I[i+1], P(II)] ≤0，同时向前搜索到位置 j 满足 det[DL_I[j], DL_I[j+1], P(II)]＞0。然后，删除DL_I[i]前和 DL_I[j]后的节点。返回第10 步。

（8） 在DL_II 中向前搜索到位置i 满足：det[DL_II[i], DL_II[i+1], P(II)]＜0，同时在DL_I向后搜索到位置j 满足det[DL_I[j], DL_I[j+1], P(II)]≤0。然后，删除DL_II[i]前和DL_I[j+1]后的节点。同时在DL_II[i]前插入P(II)。返回第10步。

（9） 在DL_II 中向后搜索到位置i 满足：det[DL_II[i], DL_II[i+1], P(II)]≤0，同时在DL_I向前搜索到位置j 满足det[DL_I[j], DL_I[j+1], P(II)]≤0。然后，删除DL_II[i]后和DL_I[j+1]前的节点。同时在DL_II[i]后插入P(II)。返回第10步。

（10） 如果还要插入其它点，返回第一步；否则return successful。

如果算法returns failure，就意味着不可能建立出∂PHH(B)。同时单次插入的时间复杂度为O(n)。

4 结 论

根据类双曲壳的定义，PHH(B)是RP2上的几何封闭凸集，提出了一种新的凸壳模型——类双曲壳，对该模型进行了论证，并提出建立类双曲壳的实时算法。该类双曲壳模型将提供解决上下域问题，包括碰撞检测、路径规划、特征分类的新代数几何工具。同时笔者认为该模型可以在任意维空间中拓展。

[1] Chand D R, Kapur S S. On convex polyhedra [J]. Mathematics Magazine, 1970, 43(4)： 202-209.

[2] Marian Orlowski. A convex hull algorithm for planar simple polygons [J]. Pattern Recognition, 1985, 18(5)： 361-366.

[3] Chadnov R V, Skvortsov A V. Convex hull algorithms review [C]//Proceedings of The 8th Russian-Korean International Symposium. Tomsk, Russia, 2004： 112-115.

[4] de Groot J, de Vries H. Convex sets in projective space [J]. Compositio Mathematica, 1956, 13： 113-118.

[5] Dekker D. Convex regions in projective space [J]. The Amer. Monthly, 1955, 62(6)： 430-431.

[6] Michel Schmitt, Juliette Mattioli. Strong and weak convex hulls in non-Euclidean metric： theory and application [J]. Pattern Recognition Letters, 1994, 15(9)： 943-947.

[7] Stolfi J. Oriented projective geometry [M]. Boston： Academic Press, 1991. 76-85.

[8] Matthew T Mason. Mechanics of robotic manipulation [M]. Cambridge, Mass.： MIT Press, 2001. 105-108.

[9] Aleksandrov A D. Mathematics, Its essence, methods and role [M]. Moscow： Publishers of the USSR Academy of Sciences, 1956. 190-194.

[10] Sven Schuierer, Derich Wood. Visibility in semi-convex spaces [J]. Journal of Geometry, 1997, 60(1-2)： 160-187.

[11] Edwin Bidwell Wilson. Projective and metric geometry [J]. The Annals of Mathematics, 1904, 5(3)： 145-150.