陳述平， 汪 揚(yáng)， 宋萃娥

（1. 東北大學(xué)機(jī)械學(xué)院，遼寧 沈陽 110004；2. 遼寧石油化工大學(xué)機(jī)械學(xué)院，遼寧 撫順 113001）

凸殼是計(jì)算幾何研究的對象[1]。迄今為止，已有很多凸殼算法被提出來，并被廣泛地應(yīng)用于其它學(xué)科領(lǐng)域[2-3]。凸集和凸殼的擴(kuò)展問題，有人曾在非歐幾何的有關(guān)流形的研究中提到過[4-5]。通過使任意兩點(diǎn)的“直線段”都在集合內(nèi)的定義，凸殼和凸集很自然的被拓展到非歐幾何中[6]。J. de Groot 和H. de Vries 曾對射影空間中RPn的凸集問題作過研究[4]，暗示射影平面RP2中的凸殼是有可能通過無窮遠(yuǎn)直線L∞。在有向射影幾何的提法出現(xiàn)后[7]，Matthew T. Mason 明確的提出外部線作為通過無窮遠(yuǎn)直線L∞的凸性[8]。而Jorge Stolfi 認(rèn)為在經(jīng)典射影空間當(dāng)中，由于不可定向平面和含糊的線段定義，凸是沒有意義的[7]。為了更好的在齊次坐標(biāo)系中分析從經(jīng)典凸殼到類雙曲殼的射影變換就要避免Jorge Stolfi 提到的不利條件。運(yùn)用拓?fù)渫咄瑫r(shí)借助于在有向射影幾何的正平面T2上可定向的優(yōu)勢，來幫助提出射影凸集和凸殼的概念[9]。對于類雙曲殼研究的初衷就是為了研究凸殼外部同時(shí)在兩個(gè)方向都可視的區(qū)域[10]。并且，將提出一個(gè)在歐氏平面E2上的實(shí)時(shí)凸殼構(gòu)造算法，它的復(fù)雜度不一定是最低，但是它提供了一種在兩個(gè)區(qū)域中間尋找直線簇的可能性。

1 射影平面中的類雙曲殼

1.1 射影平面中的凸集

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

定義1 RP2的子集B 被稱為半凸，如果滿足任意給出子集B 中兩個(gè)點(diǎn)P1和P2，存在以P1和P2為端點(diǎn)的線段Ls(P1, P2)，且Ls(P1, P2)也被包含于子集B 中[4]。

定義2 RP2的子集B 被稱為凸，如果滿足任意給出子集B 是半凸，并且B 不包含一條直線L(P1, P2)=P1∨P2。也可以這樣定義：RP2的子集B 被稱為凸，有且只有子集B 中任意兩點(diǎn)P1和P2唯一被以P1和P2為端點(diǎn)且也被包含于子集B的線段Ls(P1, P2)所連接[4]。

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

定義4 RP2上凸殼CH(B)中的點(diǎn)P 被稱為頂點(diǎn)，當(dāng)且僅當(dāng)它不是凸殼CH(B)中任意線段的內(nèi)點(diǎn)。這個(gè)線段有可能穿過無窮遠(yuǎn)直線L∞。

定義5 RP2上凸殼的邊界?CH(B)是包含子集B 最小的凸區(qū)域的邊緣。

1.2 射影平面中類雙曲殼的概念

在實(shí)平面R2上點(diǎn)集B 的凸殼可以被想象成為包圍住給定物體的皮筋。而在射影平面RP2上，如果凸殼本身不通過無窮遠(yuǎn)直線L∞，它在形態(tài)上依舊如同在實(shí)平面R2上的凸殼。在本文當(dāng)中，類雙曲殼的概念是想象點(diǎn)集B 穿越無窮遠(yuǎn)直線L∞的情形。

定義6 類雙曲殼(PHH(B))是通過無窮遠(yuǎn)直線L∞的子集B 的凸殼。

定義7 RP2上PHH(B)的內(nèi)部是同胚于R2上的圓，且被凸殼邊界?PHH(B)所包圍的區(qū)域[9]。

定義8 RP2上PHH(B)的外部是同胚于不可定向的默比烏斯帶，且被凸殼邊界?PHH(B)所包圍的區(qū)域[9]。

在實(shí)射影平面上，平面是雙連通的。因此，一條線不能分割平面；需要兩條線才能把平面分割為Region I 和Region II[11]（見圖1）。根據(jù)上面的定義，Region I 不是凸而是半凸，因?yàn)榇嬖谕ㄟ^P1的完整的直線。比較圖2 中的Region I不只是凸，也是RP2上最簡單的類雙曲殼。

圖1 兩直線分割平面為Region I 和Region II

圖2 Region I 和頂點(diǎn)P1, P2, P3 簡單的類雙曲殼

定義9 PHH(B)臨界支撐線是兩條直線，滿足：把RP2平面分割為Region I 和 Region II（見圖2），并且PHH(B)屬于Region I；同時(shí)Region I不包含不于PHH(B)有任何交點(diǎn)的完整直線。

在圖2 中，臨界支撐線是P1P2和P1P3。圖2中Region I 中的?PHH(B)是一個(gè)被L∞分割成兩半的閉環(huán)。因?yàn)椋恳粚o窮遠(yuǎn)對跖點(diǎn)都是同一個(gè)點(diǎn)，類雙曲殼的內(nèi)部是一個(gè)拓?fù)鋱A，而圖2 中沒有灰色的部分同胚于默比烏斯帶[9]。同時(shí)，凸殼邊界同調(diào)于0，因此包圍了一個(gè)區(qū)域。注意到類雙曲殼的邊界?PHH(B)也是默比烏斯帶的邊緣。

2 有向射影空間中的類雙曲殼

類雙曲殼和經(jīng)典凸殼的等價(jià)問題在圖3 中表示出來：類雙曲殼可以通過將通過經(jīng)典凸殼內(nèi)的直線L 投影到無窮遠(yuǎn)直線L∞得到。

圖3 將通過無窮遠(yuǎn)直線L∞的經(jīng)典凸殼 投影到有向射影平面T2 的正平面

T2上的射影變換φ，對應(yīng)于3×3 射影變換矩陣A，并且滿足等式

等式gx+hy+1=0 是將被映射到無窮遠(yuǎn)直線L∞的直線L。所有點(diǎn)都表示成齊次坐標(biāo)：Pi=[xi, yi, 1]T。有向射影平面T2的一個(gè)優(yōu)點(diǎn)就是它允許永久性的定義平面上一條直線的兩邊[7]。δi=gxi+hyi+1 的正負(fù)號表示了直線的左右邊。

為了簡化符號，表示對角矩陣為diag，計(jì)算行列式為det，表示正負(fù)性為sign。三種關(guān)系記為

對于任意實(shí)數(shù)x：若x=0, sign(x)=0; 若x＞0, sign(x)=1; 若x＜0, sign(x)=-1。

2.1 變換矩陣A

矩陣A 有8 個(gè)變量，所以它應(yīng)該能夠匹配四對點(diǎn)。在圖4 中給出8 個(gè)點(diǎn)P1, P2, P3, P4, P1′, P2′, P3′, P4′。其中P1, P2, P3, P4是經(jīng)典凸殼在正平面上逆時(shí)針方向且沒有三點(diǎn)共線的頂點(diǎn)；P1′, P2′, P3′, P4′滿足P1′=P1, P2′=P2, P3′=P4, P4′=P3，是類雙曲殼在正平面上沒有三點(diǎn)共線的頂點(diǎn)。P1和P2是兩個(gè)相鄰頂點(diǎn)，P3和P4也是兩個(gè)相鄰頂點(diǎn)。

命題1 存在唯一3×3 的射影變換矩陣A 將無三點(diǎn)共線的逆時(shí)針排列點(diǎn)P1, P2, P3, P4映射到滿足P1′= P1, P2′=P2, P3′=P4, P4′=P3關(guān)系的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。同時(shí)可以推演出

圖4 以在正平面上逆時(shí)針方向 P1, P2, P3, P4 為頂點(diǎn)的經(jīng)典凸殼

證 明建立方程組

∵等式(1) δiPi′=APi成立，同時(shí)∵P1, P2, P3, P4逆時(shí)針排列，且無三點(diǎn)共線

∴ λ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)成立

假設(shè)布爾函數(shù)具有n個(gè)輸入變量{xi|1in}、m個(gè)輸出變量{fo|1om}，輸入變量xi也被稱為原始輸入(Primary Input,PI)和PI信號，輸出變量fo也被稱為原始輸出(Primary Output,PO)和PO信號.其關(guān)于PI的MPRM邏輯表達(dá)式如式(1)所示.

同時(shí)∵P1, P2, P3, P4逆時(shí)針排列，且無三點(diǎn)共線

∴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 無窮遠(yuǎn)直線的反象

命題2 上述討論的矩陣A和從P1, P2, P3, P4到P1′, P2′, P3′, P4′的映射關(guān)系，唯一決定L∞的反象L，L與線段P4P1和P2P3內(nèi)部相交。見圖5和圖6。

證 明∵已知等式(2)唯一決定射影變換矩陣A，同時(shí)等式gx+hy+1=0指示將被映射到無窮遠(yuǎn)直線L∞的直線L。注意到直線法向量系數(shù)[g, h, 1]正是射影變換矩陣A第三行元素。

∵不失一般性對A?[P1, P2, P3]討論δi的正負(fù)關(guān)系：

∵等式(8)成立

∵前 面 已 知0＜λ1＜1, λ2＜0, 簡 單 加 減 有：

因?yàn)棣膇=gxi+hyi+1的正負(fù)性表示了直線L的左右不同邊。所以P3和P4在直線L同一邊，P1和P2在L不同于P3和P4的另一邊。因此，能夠判斷出直線L通過線段P4P1和P2P3內(nèi)部，命題2證畢。

圖5 L 將經(jīng)典凸殼分割為Region I 和II

圖6 Region I 和II 的以P1′P4′和P2′P3′ 為臨界支撐線的類雙曲殼

2.3 頂點(diǎn)序列的走向

命題3 L∞的反象L 將經(jīng)典凸殼分為Region I和Region II。對于鄰接頂點(diǎn)Pi, Pj, Pk一開始在經(jīng)典凸殼的Region I 逆時(shí)針方向排列，在射影后其相應(yīng)點(diǎn)Pi′, Pj′, Pk′仍然為逆時(shí)針排列。相反，對于鄰接頂點(diǎn)Pr, Ps, Pt一開始在經(jīng)典凸殼的Region II 逆時(shí)針方向排列，在射影變換后其相應(yīng)點(diǎn)Pr′, Ps′, Pt′為順時(shí)針排列。

證 明自明的，∵Pi, Pj, Pk逆時(shí)針排列，∴det([Pi, Pj, Pk])＞0；同時(shí)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′逆時(shí)針排列。

同理證明Pr, Ps, Pt在Region II, 必然存在det([Pr, Ps, Pt])＞0同時(shí)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′順時(shí)針排列。命題3證畢。

2.4 區(qū)域的投影

命題4 射影變換φ把經(jīng)典凸殼中的Region I和Region II 相應(yīng)的映射到類雙曲殼的Region I和Region II（如圖5 和圖6 所示）。

證 明對于經(jīng)典凸殼Region I 中任意逆時(shí)針鄰接頂點(diǎn)Pi和Pj以及Region I 中任意點(diǎn)PI，必然滿足

同時(shí)∵Pi, Pj, PI和P4一樣都在Region I 中。

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

下面著重討論det[Pi′, Pj′, PI′]的正負(fù)性：

∵等式(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

也就說，任何經(jīng)典凸殼Region I中的點(diǎn)將被映射到類雙曲殼PHH(B)的Region I中。

同理可證，對于經(jīng)典凸殼Region II中任意逆時(shí)針鄰接頂點(diǎn)Pm, Pn以及Region II中任意點(diǎn)PII, 有類似結(jié)論。所有任意Region II中點(diǎn)將被映射到PHH(B)的Region II中。

所以命題4 證畢。

綜上所述，可以得出另一個(gè)結(jié)論，由于一對一的射影變換，PHH(B)是最小的凸區(qū)域。

3 類雙曲殼邊界的實(shí)時(shí)構(gòu)造算法

3.1 頂點(diǎn)的性質(zhì)

假設(shè)?PHH(B)被存儲在雙向鏈表當(dāng)中，DL_I和DL_II 分別保存了Region I 中逆時(shí)針方向的頂點(diǎn)序列和Region II 中順時(shí)針方向的頂點(diǎn)序列。則可以按照兩個(gè)原則增量添加類雙曲殼中的點(diǎn)：

（1） 任意Region I 中的點(diǎn)都在直線DL_ I[i]→DL_I[i+1]的左邊，且在直線DL_II[i]→ DL_ II[i+1]左邊；

（2） 任意Region II 中的點(diǎn)都在直線DL_ I[i]→DL_I[i+1]的右邊，且在直線DL_II[i]→ DL_ II[i+1]右邊。

3.2 確定類雙曲殼邊界步驟

利用3.1 的原則，確定?PHH(B)步驟如下：

（1） 輸入代插入點(diǎn)的P(Belong)的坐標(biāo)和歸屬區(qū)域(I 或II)。判定P(Belong)實(shí)際所在圖7中所在區(qū)域。

圖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，同時(shí)繼續(xù)向前搜索到位置 j 滿足 det[DL_I[j], DL_I[j+1], P(I)]＞0。然后，在DL_I[i]后插入P(I)，同時(shí)刪除從DL_I[i+1]到DL_I[j-1]的節(jié)點(diǎn)。返回第10 步。

（3） 刪除DL_I 中所有的現(xiàn)存數(shù)據(jù)，同時(shí)使P(I)作為DL_I[first]；在DL_II 中向前搜索到位置i 滿足：det[DL_II[i], DL_II[i+1], P(I)]≥0，同時(shí)向前搜索到位置 j 滿足 det[DL_II[j], DL_II[j+1], P(I)]＜0。然后，刪除DL_II[i]前和DL_II[j]后的節(jié)點(diǎn)。返回第10 步。

（4） 在DL_I 中向前搜索到位置i 滿足：det[DL_I[i], DL_I[i+1], P(I)]＞0，同時(shí)在DL_II 向后搜索到位置j 滿足det[DL_II[j], DL_II[j+1], P(I)]≥0。然后，刪除DL_I[i]前和DL_II[j+1]后的節(jié)點(diǎn)。同時(shí)在 DL_I[i]前插入P(I)。返回第10步。

（5） 在DL_I 中向后搜索到位置i 滿足：det[DL_I[i], DL_I[i+1], P(I)]≥0，同時(shí)在DL_II向前搜索到位置j 滿足det[DL_II[j], DL_II[j+1], P(I)]≥0。然后，刪除DL_I[i]后和DL_II[j+1]前的節(jié)點(diǎn)。同時(shí)在DL_I[i]后插入P(I)。返回第10步。

（6） 在DL_II 中向前搜索到位置i 滿足：det[DL_II[i], DL_II[i+1], P(II)]≥0 同時(shí)繼續(xù)向前搜索到位置 j 滿足 det[DL_II[j], DL_II[j+1], P(II)]＜0。然后，在DL_II[i]后插入P(II)，同時(shí)刪除從DL_II[i+1]到DL_II[j-1]的節(jié)點(diǎn)。返回第10步。

（7） 刪除DL_II 中所有的現(xiàn)存數(shù)據(jù)，同時(shí)使P(II)作為DL_II[first]；在DL_I 中向前搜索到位置i 滿足：det[DL_I[i], DL_I[i+1], P(II)] ≤0，同時(shí)向前搜索到位置 j 滿足 det[DL_I[j], DL_I[j+1], P(II)]＞0。然后，刪除DL_I[i]前和 DL_I[j]后的節(jié)點(diǎn)。返回第10 步。

（8） 在DL_II 中向前搜索到位置i 滿足：det[DL_II[i], DL_II[i+1], P(II)]＜0，同時(shí)在DL_I向后搜索到位置j 滿足det[DL_I[j], DL_I[j+1], P(II)]≤0。然后，刪除DL_II[i]前和DL_I[j+1]后的節(jié)點(diǎn)。同時(shí)在DL_II[i]前插入P(II)。返回第10步。

（9） 在DL_II 中向后搜索到位置i 滿足：det[DL_II[i], DL_II[i+1], P(II)]≤0，同時(shí)在DL_I向前搜索到位置j 滿足det[DL_I[j], DL_I[j+1], P(II)]≤0。然后，刪除DL_II[i]后和DL_I[j+1]前的節(jié)點(diǎn)。同時(shí)在DL_II[i]后插入P(II)。返回第10步。

（10） 如果還要插入其它點(diǎn)，返回第一步；否則return successful。

如果算法returns failure，就意味著不可能建立出?PHH(B)。同時(shí)單次插入的時(shí)間復(fù)雜度為O(n)。

4 結(jié) 論

根據(jù)類雙曲殼的定義，PHH(B)是RP2上的幾何封閉凸集，提出了一種新的凸殼模型——類雙曲殼，對該模型進(jìn)行了論證，并提出建立類雙曲殼的實(shí)時(shí)算法。該類雙曲殼模型將提供解決上下域問題，包括碰撞檢測、路徑規(guī)劃、特征分類的新代數(shù)幾何工具。同時(shí)筆者認(rèn)為該模型可以在任意維空間中拓展。

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