判断多边形的顺逆性_判断多边形的顺逆性_无序线段的形成的封闭多边形,如何找出顺序

前言

如果文中数学公式或符号出现乱码，可访问判断多边形的顺逆性

给定一个多边形的所有坐标，如何判断该多边形的点的排列的顺逆性呢？

本文将介绍两种方法解决该问题，并通过C++算法实现。

一、格林公式

设闭区域 D 由分段光滑的简单曲线 L 围成，函数 P(x,y)及 Q(x,y)在 D 上有一阶连续偏导数，则有

其中L是D的取正向的边界曲线。

在该公式中取$P(x,y)=y$, $Q(x,y)=0$，带入上式可得$-{\iint }_{D}dxdy=\iint ydx$，即${\iint }_{D}dxdy=-\iint ydx$，左边就代表区域D的面积(记为S)，右边$\iint ydx$代表沿着多边形一圈的曲线积分，注意有个负号。

考虑多变形的一条边$P_i(x_i,y_y),P_{i+1}(x_{i+1},y_{i+1})$，参数方程为：

{ x = ( x i + 1 − x i ) t + x i y = ( y i + 1 − y i ) t + y i

$$\begin{cases} x=(x_{i+1}-x_i)t+x_i \\ y=(y_{i+1}-y_i)t+y_i \\ \end{cases}$$ {x=(xi+1​−xi​)t+xi​y=(yi+1​−yi​)t+yi​​

带入 $S=-\iint {}_{x_i}^{x_{i+1}}ydx$ 可得 $S_i=-\frac{1}{2}(y_{i+1}+y_i)(x_{i+1}-x_i)$，每条边都可以求出一个 $S_i$，求和可以得出多边形的带符号面积，若为正，说明多边形的点为逆时针排列，为负，则说明为顺时针排列。

//自定义 MyPoint类
typedef struct MYPOINT {
	double x;
	double y;
	MYPOINT(double xx, double yy) :x(xx), y(yy) {}
} MyPoint;

bool IsClockwise_1(vector<MyPoint> pts) {
	double d = 0;
	const size_t size = pts.size();
	for (size_t i = 0; i < size - 1; i++) {
		d += -0.5 * (pts[i + 1].y + pts[i].y) * (pts[i + 1].x - pts[i].x);
	}
	
    // 注意，这个容易忽略！最后一个点与第一个点构成的边
	d += -0.5 * (pts[0].y + pts[size - 1].y) * (pts[0].x - pts[size - 1].x);

	if (d < 0)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、叉积法

两个向量的叉积具有正负性，可以判断由第一个向量旋转到第二个向量是顺时针还是逆时针(旋转角$\le 180^o$)。那么能不能用此方法判断多边形的正负性呢？

考虑下图的情形，多边形ABCDEFG和多边形A′B′C′D′E′F′G′。

1. 对于B点而言，向量$\overrightarrow{BA}$与$\overrightarrow{BC}$，$\overrightarrow{BA}\times \overrightarrow{BC}$结果为负数，多边形ABCDEFG的点为顺时针排列。

2. 对于B′点而言，向量$\overrightarrow{B\prime A\prime }\times \overrightarrow{B\prime C\prime }$的结果也为负数，但是四边形A′B′C′D′E′F′G′为逆时针排列。

因此判断B点与相邻两点构成向量的叉积的正负是不可行的，但是有没有哪个点（或者说，哪种类型的点）是符合要求的呢？

现在考虑多边形ABCDEFG最左侧的点F 和 多边形A′B′C′D′E′F′G′最左侧的点E′，

1. 对F点而言， $\overrightarrow{FE}\times \overrightarrow{FG}$，结果为正数，多边形的点为顺时针排列。

2. 对E′点而言， $\overrightarrow{E\prime D\prime }\times \overrightarrow{E\prime F\prime }$，结果为负数，多边形的点为逆时针排列。

可以证明，使用多变形的最左(右、上、下)侧的一个点，该点与前一个点构成的向量(记为$\vec{a}$)，与后一个点构成的向量(记为$\vec{b}$)，判断 $\vec{a}\times \vec{b}$ 的正负，若为正，说明多边形的点为顺时针排列，若为负则为逆时针排列。

bool IsClockwise_2(vector<MyPoint> pts)
{
	//1. 找到横坐标最小的点，该点一定是多边形的最左侧的点，且为凸点
	double min_x = pts[0].x;
	int min_idx = 0;
	size_t size = pts.size();
	for (size_t i = 1; i < size; i++) {
		if (pts[i].x < min_x) {
			min_x = pts[i].x;
			min_idx = i;
		}
	}

	//2. 判断该点与前一个点构成的向量 和 与后一个点构成的向量的叉积的正负
	//2.1 获取该点前一个点和后一个点的下标
	int prev_min_idx = 0, next_min_idx = 0;
	if (0 == min_idx) {		//如果该点是第一个点
		prev_min_idx = size - 1;
		next_min_idx = min_idx + 1;
	}
	else if (size - 1 == min_idx) {	//如果该点是最后一个点
		prev_min_idx = min_idx - 1;
		next_min_idx = 0;
	}
	else {
		prev_min_idx = min_idx - 1;
		next_min_idx = min_idx + 1;
	}

	//2.2 计算叉积
	double cross = (pts[prev_min_idx].x - pts[min_idx].x) * (pts[next_min_idx].y - pts[min_idx].y) -
		(pts[next_min_idx].x - pts[min_idx].x) * (pts[prev_min_idx].y - pts[min_idx].y);

	if (cross > 0)
		return true;
	else 
		return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

The End

如有任何疑问，可联系 leopard.c@outlook.com

Thanks for reading！