本文介绍两种多边形（简单多边形）的顺逆时针顺序判断算法，其中一种算法就是通过计算多边行的面积(带符号)来判断。另一种方法是根据最左侧点前后边的转向(叉积)判断。有意思的是，网上有一些文章并没有就这种方法的特殊情况进行讨论。

1.多边形的面积算法

多边形的面积算法可以由三角形的面积算法引出。先看三角形的面积计算

$$Area(\Delta) = \frac {\vec v_0 \times \vec v_1}{2}$$

实际上，向量的叉积为向量，在二维几何情况下，我们将其当做标量时，指的是向量的Z维。叉积是由符号的，当三角形位于向量的左侧时，任意两边求解的面积均为正号。

多边形的面积即将多变形分解为若干三角形的面积加和: $$\begin{equation*}
s = \sum_{i=1}^{n-3}{Area(\Delta c_0c_ic_{i+1})}
\end{equation*}$$

其中，n值多边形boundary节点个数，按照惯例尾点与首点重复，即三角形有4个节点。当多边形环序为逆时针顺序时，面积为正，反之为负号。因此，当多边形存在“洞”时，面积公式只需要将洞的环构成的面积加入即可。洞的顺序与外环顺序是想反的，因此形成的面积会相减。

1.1对比：

一种相似的方案如上图所示。$$\begin{equation*}
s = \sum_{i=0}^{n-2}{Area(\Delta c_0c_ic_{i+1})}
\end{equation*}$$ 你能知道这个方法最大的问题么？其实，这个方法的问题在于，如果多边形位于原点位置较远，而坐标存储精度不够大的情况下(如使用float保存)，容易出现比较大的摄入误差，因为由原点与边构成的多边形面积过大，计算叉积的时候还有可能因为溢出而计算不正确。所以不推荐使用。其实第一种方法就是为了避免这样的情况发生，从而将原点移动到了多边形第一个节点处。

1.2 实现代码

 

2 多边形的顺逆时针顺序判断

2.1 面积法

根据第一节描述，如果多边形为逆时针顺序，面积为正；反正面积为负；

2.2 根据最左侧点上下边的走向判断

据上图，如果从最左侧点(leftmost)看，其前一条边与后一条边的转向关系为右转，那么多边形为顺时针顺序。反之，如果转向关系为左转，则多边形为逆时针顺序。转向关系可以用两条边的向量的叉积判断。

wait a minute……  我们还漏掉了某种特殊情况，如果说面的最左侧点的x坐标与prev，next 点的坐标相同，即两条边共线呢？ 这种情况是一种特殊情况(“degenerate case”)。

因为三个点的x值是相同的，因此完全有可能出现 中间的点被选为leftmost point从而引发判断问题的。

解决方案就是判断 prev ,next 点的上下关系(y值)。若 \(y_{prev} < y_{next}\)则多边形为顺时针顺序。反正为逆时针顺序。

综上，依据最左侧上下边走向判断多边形顺序的算法是：

找到最左侧点\(P_i\)。

计算 向量叉积 \(\vec{P_{i-1}P_{i}} \times \vec {P_iP_{i+1}}\)。若 叉积<0,多边形为顺时针顺序；若叉积>0 ，多边形为逆时针顺序；

若叉积等于0: 若 \(P_{i-1}.y < P_{i+1}.y \) 则 多边形为顺时针顺序，否则多边形为逆时针顺序。

实现代码：

3.参考文献：

1.Berg M D, Cheong O, Kreveld M V, et al. Computational Geometry: Algorithms and Applications[M]. Springer Publishing Company, Incorporated, 2000. 第三版 第36页

2.geos 中 geos::algorithm::CGAlgorithms::IsCCW(.)函数的实现；