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

核心方法使用鞋带公式有向面积法根据公式结果的符号判断多边形顶点环绕方向结果为正表示逆时针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::vectorPoint2D 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_{i1} - x_{i1}*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 共线非多边形; } }