類雙曲殼的概念及算法

陳述平， 汪 揚， 宋萃娥

（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.