通过计算确定顺时针方向与逆时针方向

何向荣 ，李敬兆

（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-），男，安徽淮南人，安徽理工大学计算机科学与工程学院教授，研究方向为嵌入系统互联网。

[责任编辑：曹怀火]