二维平面点集环绕方向判断

核心方法

使用鞋带公式（有向面积法），根据公式结果的符号判断多边形顶点环绕方向：结果为正表示逆时针（CCW），为负表示顺时针（CW）。

适用场景

该方法适用于任意简单多边形，包括凸多边形和凹多边形。

鞋带公式原理

本质是利用向量叉乘的累加，计算多边形的“有向面积”。

公式：

其中，(xi​,yi​) 为多边形顶点的坐标，且 (xn​,yn​)=(x0​,y0​)。

几何含义：从最小单元理解，两个点 A(x1​,y1​) 和 B(x2​,y2​) 与原点 (0,0) 构成一个三角形，该三角形的有向面积为 1/2(x1​y2​−x2​y1​)。

• ∣x1​y2​−x2​y1​∣ 表示由向量 OA 和 OB 张成的平行四边形的面积，正好是三角形面积的两倍。
• x1​y2​−x2​y1​ 的正负号，表示从 OA 旋转到 OB 的方向：正为逆时针，负为顺时针。

鞋带公式就是将多边形“三角化”，把每个小三角形的有向面积（关键在于符号）累加起来。累加结果的符号就代表了整个多边形的环绕方向。

方向判断的底层逻辑：

• 每一项本质是相邻两边向量的叉乘。
• “叉乘结果 > 0”：表示从当前边到下一条边是朝逆时针方向旋转。
• “叉乘结果 < 0”：表示从当前边到下一条边是朝顺时针方向旋转。
• 将所有边的这种局部方向累加，其总和的符号就决定了整体的环绕方向。

C++ 代码实现

std::string JudgePolygonDirection(const std::vector<Point2D>& polygon) { if (polygon.size() < 3) { return "点数量不足（<3），无法构成多边形"; } double signed_area_2 = 0.0; // 存储 2 * 有向面积 const size_t n = polygon.size(); for (size_t i = 0; i < n; ++i) { const Point2D& p1 = polygon[i]; // 自动闭合：最后一个点衔接第一个点 const Point2D& p2 = polygon[(i + 1) % n]; // 鞋带公式核心计算：累加 (x_i*y_{i+1} - x_{i+1}*y_i) signed_area_2 += (p1.x * p2.y) - (p2.x * p1.y); } // 浮点精度容错，设置 1e-9 精度阈值 const double EPS = 1e-9; if (signed_area_2 > EPS) { return "逆时针(CCW)"; } else if (signed_area_2 < -EPS) { return "顺时针(CW)"; } else { return "共线（非多边形）"; } }