通過計算確定順時針方向與逆時針方向

何向榮 ，李敬兆

（1.安徽理工大學 計算機科學與工程學院,安徽 淮南 232001；2.池州學院 數學計算機科學系，安徽 池州 247000）

通過計算確定順時針方向與逆時針方向

何向榮1，2，李敬兆1

（1.安徽理工大學 計算機科學與工程學院,安徽 淮南 232001；2.池州學院 數學計算機科學系，安徽 池州 247000）

無論是在計算機圖形圖像學科還是在數學以及物理學等學科中，人們經常會談到某對象是順時針方向旋轉還是逆時針方向旋轉。當我們在討論這一問題時又幾乎都是論述性地講解，甚至于以手勢來比劃，而從來沒有給出其數學的或者幾何的定義，但是實際上這是非常重要的，特別是在編程處理圖形圖像過程中顯得尤為重要。文中從一般幾何學的基礎知識出發，給出最基本也是最原始的數學解釋，且給出相應的計算公式，并應用于一般計算機學科的圖形與圖像研究。

圖形區域；邊界方向；坐標變換；聚類方法

1 引言

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

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

本文試圖使用一般數學和幾何學上的簡單變換的方法來定性定量地獲取圖形的方向及圖像區域邊界的方向，并且給出相應的計算方法。

2 逆時針方向與順時針方向的幾何精確定義

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

圖1 順時針與逆時針示意圖

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

圖2 在坐標變換下逆時針的幾何意義

圖2中新坐標系(O’X’Y’)是經平移到P處且再旋轉α角后而得到。

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

從圖2可以看出，所謂PQR呈逆時針是因為：旋轉方向的幾何精確定義：1）設平面上有三個不共線的點，從第1個點向第2個點引直線作為新的坐標系的X'軸，且以由第1個點指向第2個點為X'軸的正向，從第1個點處引前一直線的垂線作為Y'軸，建立新坐標系O'X'Y'，第3點在新坐標系O'X'Y'下的新坐標為(x2'，y2')，則當 y2'＞0，這 3 個點為逆時針方向，反之如果y2'＜0時為順時針方向。

2）當三點共線時，從第1個點向第2個點引射線，如果第3個點在第2個點的右方，則為順時針方向，否則為逆時針方向；

3）如果這3個點至少有2個點共點（重合），則無法判定其方向；

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

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

顯然，可以定義如下的一個檢測函數：

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

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

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

圖3 一般多邊形的邊界點驗證

其邊界方向設定為：沿邊界點序列每3個點為1組，分別為

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

因此，一般多邊形的邊界方向為

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

以下以數學歸納法逐步證明定律。

證明1當k=3時，首先考察圖4中的三角形：

圖4 三邊形的邊界點驗證

圖4中左邊的三角形

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

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

證明2當k=4時，實際上是對三角形增加1個頂點，成為4邊形如下：

圖5 一般4邊形邊界點驗證

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

新的和S僅僅是在原有的基礎上加1或者減1，具體對應是：

(A)如果原來是順時針方向，增加1個內凹點時，S 增 1，但 S＜－1；

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

(C)如果原來為逆時針方向，增加1個外凸點時，S 增 1，仍然 S＞1；

(D)如果原來為逆時針方向，增加1個內凹點時，S 減 1，但 S＞1；

原因是：每當增加1個點時，是將某一點（比如Pi）撕開，拉到另一位置處形成新的頂點P，其原來的邊PiPi+1就變為兩條邊：PiP，PPi+1，或者是將某條邊斷開增加兩條邊，因此其和的算式中其對應的頂點 的 3 項 Direct(Pi－2,Pi－1,Pi)、Direct(Pi－1,Pi,Pi+1)，Direct(Pi,Pi+1,Pi+2)變化4項為：

針 對 Direct(Pi－1,Pi,Pi+1)與 Direct(Pi,Pi+1,Pi+2)的 正負號（逆時針與順時針）可以確定其增1還是減1。證明N：假定以上結論對于一般的k=N已經成立，如下是其某一種情形：

圖6 N邊形時原型

且 SNL＜－1，SNR＞1

則以下考慮K=N+1

證明N+1：當K=N+1時，設新增點為PN，也就是在N個頂點的多邊形中增加1點，必為以下4種情形之一（見圖7）

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

由于每一條內凹邊的出現都會產生出一條外凸邊以回到原來的路線，且每一條外凸邊的產生都會同時產生一條內凹邊以回到原來的路線，因此類似地有

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

至此，定律證明完畢。

由于在計算機領域內全部圖像區域都可以看成是多邊形區域，因此可以應用此定律計算一般圖像區域的邊界方向。

4 結語

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

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

[2]侯慶，王茵，陳孝威.基于GDI+技術的物體識別系統[J].貴州工業大學學報:自然科學版,2006，35（2）： 40－43.

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

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

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

TP3

A

1674-1102(2011)06-0035-03

2011-09-20

何向榮（1958-），男，安徽池州人，池州學院數字計算系教師，研究方向網絡應用；李敬兆（1963-），男，安徽淮南人，安徽理工大學計算機科學與工程學院教授，研究方向為嵌入系統互聯網。

[責任編輯：曹懷火]