通過計(jì)算確定順時(shí)針方向與逆時(shí)針方向

何向榮 ，李敬兆

（1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,安徽 淮南 232001；2.池州學(xué)院 數(shù)學(xué)計(jì)算機(jī)科學(xué)系，安徽 池州 247000）

通過計(jì)算確定順時(shí)針方向與逆時(shí)針方向

何向榮1，2，李敬兆1

（1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,安徽 淮南 232001；2.池州學(xué)院 數(shù)學(xué)計(jì)算機(jī)科學(xué)系，安徽 池州 247000）

無論是在計(jì)算機(jī)圖形圖像學(xué)科還是在數(shù)學(xué)以及物理學(xué)等學(xué)科中，人們經(jīng)常會(huì)談到某對(duì)象是順時(shí)針方向旋轉(zhuǎn)還是逆時(shí)針方向旋轉(zhuǎn)。當(dāng)我們?cè)谟懻撨@一問題時(shí)又幾乎都是論述性地講解，甚至于以手勢來比劃，而從來沒有給出其數(shù)學(xué)的或者幾何的定義，但是實(shí)際上這是非常重要的，特別是在編程處理圖形圖像過程中顯得尤為重要。文中從一般幾何學(xué)的基礎(chǔ)知識(shí)出發(fā)，給出最基本也是最原始的數(shù)學(xué)解釋，且給出相應(yīng)的計(jì)算公式，并應(yīng)用于一般計(jì)算機(jī)學(xué)科的圖形與圖像研究。

圖形區(qū)域；邊界方向；坐標(biāo)變換；聚類方法

1 引言

計(jì)算機(jī)學(xué)科圖形與圖像的討論中，關(guān)于其圖形邊界或者圖像區(qū)域邊界的研究一般僅僅只限于其提取、變換及擬合等操作，關(guān)于其邊界的方向研究幾乎沒有涉及，但實(shí)際上這又是很重要的一個(gè)部分。由于對(duì)其人為的忽視，致使圖像處理時(shí)許多的理論敘述總是不太完善，不如數(shù)學(xué)中關(guān)于圖像的討論時(shí)嚴(yán)謹(jǐn)。

實(shí)際上，無論是在數(shù)學(xué)還是在計(jì)算機(jī)學(xué)科以及其他諸如物理等學(xué)科中，方向或者說運(yùn)動(dòng)的方向都是一個(gè)重要且基本的因素，在自動(dòng)化處理時(shí)，必須能夠正確地識(shí)別以利于進(jìn)一步處理。在計(jì)算機(jī)圖形圖像學(xué)中，圖形的邊界也應(yīng)該確定其方向，如果不進(jìn)行這樣的處理就會(huì)有缺陷。大名鼎鼎的PhotoShop也在這個(gè)問題上犯錯(cuò)，比如其中框選或者套索選取某個(gè)區(qū)域時(shí)其閃爍的邊界的閃爍方式不是真正沿邊界運(yùn)動(dòng)的，而是從左上角向右下一角逐段閃爍的，人工痕跡明顯，很生硬。

本文試圖使用一般數(shù)學(xué)和幾何學(xué)上的簡單變換的方法來定性定量地獲取圖形的方向及圖像區(qū)域邊界的方向，并且給出相應(yīng)的計(jì)算方法。

2 逆時(shí)針方向與順時(shí)針方向的幾何精確定義

在討論方向時(shí)，除了方位外一般地總是涉及到逆時(shí)針方向與順時(shí)針方向。但究竟什么是逆時(shí)針方向或順時(shí)針方向？往往總以為已經(jīng)形象化地解決了。但實(shí)際上從數(shù)學(xué)和幾何學(xué)上應(yīng)該怎樣定性、定量地予以精確定義而往往由于其直觀性而被人們忽略。首先請(qǐng)參考圖1:

圖1 順時(shí)針與逆時(shí)針示意圖

圖1中左右分別給出了3個(gè)點(diǎn)，其頂點(diǎn)分別為PQR及ABC，直觀上可以看出左邊的3點(diǎn)PQR是逆時(shí)針方向而右邊的ABC為順時(shí)針方向。但如何精確的給出幾何定義？請(qǐng)參看圖2：

圖2 在坐標(biāo)變換下逆時(shí)針的幾何意義

圖2中新坐標(biāo)系(O’X’Y’)是經(jīng)平移到P處且再旋轉(zhuǎn)α角后而得到。

注意：其中α角度是連接PQ后形成的直線與X軸的夾角。

從圖2可以看出，所謂PQR呈逆時(shí)針是因?yàn)椋盒D(zhuǎn)方向的幾何精確定義：1）設(shè)平面上有三個(gè)不共線的點(diǎn)，從第1個(gè)點(diǎn)向第2個(gè)點(diǎn)引直線作為新的坐標(biāo)系的X'軸，且以由第1個(gè)點(diǎn)指向第2個(gè)點(diǎn)為X'軸的正向，從第1個(gè)點(diǎn)處引前一直線的垂線作為Y'軸，建立新坐標(biāo)系O'X'Y'，第3點(diǎn)在新坐標(biāo)系O'X'Y'下的新坐標(biāo)為(x2'，y2')，則當(dāng) y2'＞0，這 3 個(gè)點(diǎn)為逆時(shí)針方向，反之如果y2'＜0時(shí)為順時(shí)針方向。

2）當(dāng)三點(diǎn)共線時(shí)，從第1個(gè)點(diǎn)向第2個(gè)點(diǎn)引射線，如果第3個(gè)點(diǎn)在第2個(gè)點(diǎn)的右方，則為順時(shí)針方向，否則為逆時(shí)針方向；

3）如果這3個(gè)點(diǎn)至少有2個(gè)點(diǎn)共點(diǎn)（重合），則無法判定其方向；

根據(jù)一般的幾何學(xué)知識(shí)(見[4])，可知(x2'y2')可以通過以下公式求得：

從上述定義公式(1)可知，1）y2'＞0 為逆時(shí)針方向；2）當(dāng)y2'=0時(shí)，如果x2'＞0則為逆時(shí)針方向；

顯然，可以定義如下的一個(gè)檢測函數(shù)：

3 一般多邊形的邊界方向的確定

對(duì)于一般具有K個(gè)頂點(diǎn)的多邊形，如果已經(jīng)給定其邊界序列，或者已經(jīng)根據(jù)某種方法（特別如平面圖像區(qū)域的邊界可以以邊界點(diǎn)間相鄰如否即距離為依據(jù)而聚類，見[5]）求得了其邊界點(diǎn)集序列為：

其中有P0,P1,…,PK－1為理想狀態(tài)沿著邊界順次分布如圖3：

圖3 一般多邊形的邊界點(diǎn)驗(yàn)證

其邊界方向設(shè)定為：沿邊界點(diǎn)序列每3個(gè)點(diǎn)為1組，分別為

共K組，每一組都求出其方向，然后作和如下：

因此，一般多邊形的邊界方向?yàn)?/p>

定律：如果 S＞0：則為逆時(shí)針方向。反之(即 S＜0)為順時(shí)針方向。

以下以數(shù)學(xué)歸納法逐步證明定律。

證明1當(dāng)k=3時(shí)，首先考察圖4中的三角形：

圖4 三邊形的邊界點(diǎn)驗(yàn)證

圖4中左邊的三角形

因此，左邊的三角形邊界為順時(shí)針的，而右邊的三角形邊界為逆時(shí)針的。

特別需要指出的是 S0L＜－1，而 S0R＞1

證明2當(dāng)k=4時(shí)，實(shí)際上是對(duì)三角形增加1個(gè)頂點(diǎn)，成為4邊形如下：

圖5 一般4邊形邊界點(diǎn)驗(yàn)證

共有 4 種類型：分別為(A)，(B)，(C)，(D)，可以類似地求出

新的和S僅僅是在原有的基礎(chǔ)上加1或者減1，具體對(duì)應(yīng)是：

(A)如果原來是順時(shí)針方向，增加1個(gè)內(nèi)凹點(diǎn)時(shí)，S 增 1，但 S＜－1；

(B)如果原來是順時(shí)針方向，增加1個(gè)外凸點(diǎn)時(shí)，S 減 1，仍然 S＜－1；

(C)如果原來為逆時(shí)針方向，增加1個(gè)外凸點(diǎn)時(shí)，S 增 1，仍然 S＞1；

(D)如果原來為逆時(shí)針方向，增加1個(gè)內(nèi)凹點(diǎn)時(shí)，S 減 1，但 S＞1；

原因是：每當(dāng)增加1個(gè)點(diǎn)時(shí)，是將某一點(diǎn)（比如Pi）撕開，拉到另一位置處形成新的頂點(diǎn)P，其原來的邊PiPi+1就變?yōu)閮蓷l邊：PiP，PPi+1，或者是將某條邊斷開增加兩條邊，因此其和的算式中其對(duì)應(yīng)的頂點(diǎn) 的 3 項(xiàng) Direct(Pi－2,Pi－1,Pi)、Direct(Pi－1,Pi,Pi+1)，Direct(Pi,Pi+1,Pi+2)變化4項(xiàng)為：

針 對(duì) Direct(Pi－1,Pi,Pi+1)與 Direct(Pi,Pi+1,Pi+2)的 正負(fù)號(hào)（逆時(shí)針與順時(shí)針）可以確定其增1還是減1。證明N：假定以上結(jié)論對(duì)于一般的k=N已經(jīng)成立，如下是其某一種情形：

圖6 N邊形時(shí)原型

且 SNL＜－1，SNR＞1

則以下考慮K=N+1

證明N+1：當(dāng)K=N+1時(shí)，設(shè)新增點(diǎn)為PN，也就是在N個(gè)頂點(diǎn)的多邊形中增加1點(diǎn)，必為以下4種情形之一（見圖7）

圖7 (N+1)邊形的驗(yàn)證

由于每一條內(nèi)凹邊的出現(xiàn)都會(huì)產(chǎn)生出一條外凸邊以回到原來的路線，且每一條外凸邊的產(chǎn)生都會(huì)同時(shí)產(chǎn)生一條內(nèi)凹邊以回到原來的路線，因此類似地有

因此，有 SN+1A＜0，SN+1B＜0，SN+1C＞1，SN+1D＞1

至此，定律證明完畢。

由于在計(jì)算機(jī)領(lǐng)域內(nèi)全部圖像區(qū)域都可以看成是多邊形區(qū)域，因此可以應(yīng)用此定律計(jì)算一般圖像區(qū)域的邊界方向。

4 結(jié)語

在一般計(jì)算機(jī)圖形圖像處理過程中，一個(gè)圖形或者圖像區(qū)域?qū)嶋H上是由一個(gè)曲邊多邊形所圍成的(見[1－3])，因此，本文中提出的多邊形的相關(guān)方向算法是有意義的。應(yīng)用到的數(shù)學(xué)知識(shí)比較粗淺，因此其算法比較簡單。不過，在實(shí)際應(yīng)用中，還應(yīng)該根據(jù)情況對(duì)一般圖形或者圖像進(jìn)行前期處理，比如正確提取邊界，按邊界順序規(guī)整，細(xì)化等，必須在提取邊界后再能討論圖形區(qū)域的邊界方向，以利后續(xù)處理，對(duì)諸如Photoshop或者Windows畫圖中曲邊邊界的框選時(shí)，可以直接按方向進(jìn)行規(guī)整，然后進(jìn)一步處理，比如閃爍等。

[1]和青芳.計(jì)算機(jī)圖形學(xué)原理及算法教程（Visual C++版）[M].北京：清華大學(xué)出版社,2006.

[2]侯慶，王茵，陳孝威.基于GDI+技術(shù)的物體識(shí)別系統(tǒng)[J].貴州工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2006，35（2）： 40－43.

[3]Rafael C.Gonzalez Richard E.Woods.Digital Image Processing[M].北京：電子工業(yè)出版社,2004.

[4]С.П.芬尼可夫.解析幾何 [M].葉述武,曾如阜,譯.北京：高等教育出版社，1953.

[5]毛國君,段立娟,王實(shí),等.數(shù)據(jù)挖掘原理與算法[M].北京:清華大學(xué)出版社,2005.

TP3

A

1674-1102(2011)06-0035-03

2011-09-20

何向榮（1958-），男，安徽池州人，池州學(xué)院數(shù)字計(jì)算系教師，研究方向網(wǎng)絡(luò)應(yīng)用；李敬兆（1963-），男，安徽淮南人，安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院教授，研究方向?yàn)榍度胂到y(tǒng)互聯(lián)網(wǎng)。

[責(zé)任編輯：曹懷火]