各位同学，下午好！
今天，我们将深入探讨计算机图形学和计算几何领域中一个既基础又至关重要的概念：多边形填充的“绕数规则”（Winding Rules），特别是“奇偶规则”（Even-Odd Rule）与“非零规则”（Non-Zero Rule）之间的差异。我们将聚焦于它们在处理复杂几何体，尤其是像叶轮（Impeller）路径这样的工业应用场景中的实际影响与选择考量。作为编程专家，我们不仅要理解这些规则的理论，更要掌握其实现细节，以及它们如何塑造我们最终的计算结果。
引言：为何需要绕数规则？
在CAD/CAM、3D打印路径规划、游戏引擎渲染等众多领域，我们经常需要判断一个点是否位于一个二维多边形的内部。这个看似简单的问题，在多边形变得复杂——例如包含孔洞、自相交时——就变得不那么直观了。特别是对于叶轮这样的复杂零件，其横截面可能由多个相互嵌套、甚至自相交的区域构成。在为叶轮生成加工路径时，我们需要精确地知道哪些区域是材料，哪些是空腔，哪些是需要铣削的区域。这就是绕数规则发挥作用的地方。
绕数规则本质上是一种“点在多边形内”测试（Point-in-Polygon, PIP）的算法，它定义了多边形“内部”和“外部”的概念。不同的规则对“内部”的定义有所不同，导致在处理特定类型的多边形时产生截然不同的结果。
我们将从最基础的几何概念和辅助函数开始，逐步构建两种规则的实现，并通过具体案例和代码演示它们的行为差异。
基础几何概念与辅助函数
在深入探讨填充规则之前，我们需要一些基础的几何结构和函数来表示点、线段和执行基本几何运算。
1. Point2D 结构
我们首先定义一个二维点结构，用于表示多边形的顶点和待测试的点。
#include <vector>
#include <cmath>
#include <limits> // For numeric_limits
#include <iostream>
#include <iomanip> // For std::fixed and std::setprecision
// 定义一个小的浮点数容差，用于比较
const double EPSILON = 1e-9;
// 二维点结构
struct Point2D {
double x, y;
// 默认构造函数
Point2D() : x(0.0), y(0.0) {}
// 参数化构造函数
Point2D(double _x, double _y) : x(_x), y(_y) {}
// 运算符重载，方便比较和输出
bool operator==(const Point2D& other) const {
return std::abs(x - other.x) < EPSILON && std::abs(y - other.y) < EPSILON;
}
bool operator!=(const Point2D& other) const {
return !(*this == other);
}
};
// 方便输出Point2D
std::ostream& operator<<(std::ostream& os, const Point2D& p) {
os << "(" << std::fixed << std::setprecision(6) << p.x << ", " << p.y << ")";
return os;
}2. 几何方向判断 (Orientation)
判断三个点 p, q, r 的方向（顺时针、逆时针或共线）是计算几何中的一个基本操作。这通常通过计算向量 pq 和 pr 的叉积来完成。
> 0: 逆时针 (Counter-Clockwise, CCW)< 0: 顺时针 (Clockwise, CW)= 0: 共线 (Collinear)
enum class Orientation {
Collinear,
Clockwise, // 顺时针
CounterClockwise // 逆时针
};
// 判断三个点p, q, r的相对方向
Orientation getOrientation(const Point2D& p, const Point2D& q, const Point2D& r) {
// 叉积 (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)
double val = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
if (std::abs(val) < EPSILON) return Orientation::Collinear; // 共线
return (val > 0) ? Orientation::CounterClockwise : Orientation::Clockwise; // 逆时针或顺时针
}3. 点在线段上判断 (OnSegment)
判断一个点 q 是否在线段 pr 上。前提是 q 必须与 p, r 共线，并且 q 的坐标在 p, r 的包围盒内。
// 检查点q是否在线段pr上
bool onSegment(const Point2D& p, const Point2D& q, const Point2D& r) {
if (getOrientation(p, q, r) != Orientation::Collinear) {
return false;
}
// 检查q的x和y坐标是否在p和r之间
return (q.x >= std::min(p.x, r.x) - EPSILON && q.x <= std::max(p.x, r.x) + EPSILON &&
q.y >= std::min(p.y, r.y) - EPSILON && q.y <= std::max(p.y, r.y) + EPSILON);
}4. 线段交点判断 (doSegmentsIntersect)
判断两条线段 p1q1 和 p2q2 是否相交。这个函数对于后续处理射线与多边形边的交点至关重要。它利用了方向判断来确定线段的相对位置。
// 判断两条线段(p1, q1)和(p2, q2)是否相交
bool doSegmentsIntersect(const Point2D& p1, const Point2D& q1, const Point2D& p2, const Point2D& q2) {
// 计算四个方向
Orientation o1 = getOrientation(p1, q1, p2);
Orientation o2 = getOrientation(p1, q1, q2);
Orientation o3 = getOrientation(p2, q2, p1);
Orientation o4 = getOrientation(p2, q2, q1);
// 一般情况：线段跨越
if (o1 != Orientation::Collinear && o1 != o2 && o3 != Orientation::Collinear && o3 != o4) {
return true;
}
// 特殊情况：共线且重叠
// p1, q1, p2 共线，且 p2 在 p1q1 上
if (o1 == Orientation::Collinear && onSegment(p1, p2, q1)) return true;
// p1, q1, q2 共线，且 q2 在 p1q1 上
if (o2 == Orientation::Collinear && onSegment(p1, q2, q1)) return true;
// p2, q2, p1 共线，且 p1 在 p2q2 上
if (o3 == Orientation::Collinear && onSegment(p2, p1, q2)) return true;
// p2, q2, q1 共线，且 q1 在 p2q2 上
if (o4 == Orientation::Collinear && onSegment(p2, q1, q2)) return true;
return false; // 不相交
}奇偶规则（Even-Odd Rule）
1. 规则原理
奇偶规则是最直观和常见的点在多边形内测试方法。其核心思想是：
- 从待测试点
P发出一条射线（通常是水平向右的）。 - 计算这条射线与多边形所有边的交点数量。
- 如果交点数量为奇数，则点
P在多边形内部。 - 如果交点数量为偶数，则点
P在多边形外部。
这个规则的直观解释是：每当射线穿过多边形的边界时，它就从内部进入外部，或者从外部进入内部。
2. 行为特点
- 简单多边形: 对于没有孔洞的简单多边形，奇偶规则工作良好。
- 带孔洞的多边形: 奇偶规则能够正确识别孔洞。如果一个点在一个外环内部但在一个内环（孔洞）内部，射线将穿过两次（一次外环，一次内环），总交点数为偶数，因此被视为在外部。这符合我们对“孔洞”的直观理解。
- 自相交多边形: 这是奇偶规则表现出独特行为的地方。在自相交多边形中，某些区域可能会被视为外部，即使它们在视觉上看起来是“被包围”的。例如，一个“星形”多边形的中心区域，如果射线穿过边界两次，它将被视为外部。
3. 实现细节与挑战
- 射线选择: 通常选择水平向右的射线，因为它简化了交点计算：只需要比较
y坐标。 - 交点处理:
- 顶点: 如果射线恰好穿过多边形的顶点，需要小心处理。一种常见的做法是，如果顶点是某条边的终点，并且这条边的另一个顶点在射线的另一侧，则只计数一次。如果射线经过一个“水平”顶点（即，顶点两侧的边都在射线同一侧），则不计数。更精确的策略是，如果射线经过一个顶点，并且该顶点两侧的边分别位于射线的不同侧，则计为一个交点。
- 水平边: 如果射线与多边形的一条水平边重合，这条边不应计为交点，因为射线没有“穿过”多边形。
- 点在边上/顶点上: 如果待测试点
P恰好位于多边形的一条边或一个顶点上，通常将其视为在内部。
4. 代码实现 (isPointInPolygonEvenOdd)
我们将采用一个鲁棒的射线投射算法，处理上述特殊情况。
// 点在多边形内测试：奇偶规则
bool isPointInPolygonEvenOdd(const Point2D& p, const std::vector<Point2D>& polygon) {
int n = polygon.size();
if (n < 3) return false; // 多边形至少需要3个顶点
bool inside = false;
// 构造一条从p点向右的水平射线，终点在无穷远处
// 假设x坐标足够大，不会与任何多边形边平行
Point2D extreme = {std::numeric_limits<double>::max(), p.y};
// 遍历多边形的每条边
for (int i = 0; i < n; ++i) {
Point2D p1 = polygon[i];
Point2D p2 = polygon[(i + 1) % n];
// 1. 检查点P是否在多边形的边上
if (onSegment(p1, p, p2)) {
return true; // 如果点在边上，则视为在内部
}
// 2. 检查射线 (p, extreme) 是否与当前边 (p1, p2) 相交
// 这里需要一个更精细的交点检测，避免重复计数和处理特殊情况
// 如果边是水平的，且其y坐标与射线相同，不计入交点
if (std::abs(p1.y - p2.y) < EPSILON && std::abs(p1.y - p.y) < EPSILON) {
continue;
}
// 检查射线是否与边相交的条件：
// a) 射线的y坐标必须在边的两个端点的y坐标之间
// b) 边的x坐标必须在射线的右侧
// c) 避免顶点处的重复计数：如果交点是p1或p2，则需要特殊处理
// 确保p1.y <= p2.y，方便后续判断
if (p1.y > p2.y) {
std::swap(p1, p2);
}
// 如果射线在边的Y范围之外，不相交
if (p.y < p1.y - EPSILON || p.y > p2.y + EPSILON) {
continue;
}
// 计算射线与边的交点的X坐标
// 方程：y = p.y
// 边方程：(x - p1.x) / (p2.x - p1.x) = (y - p1.y) / (p2.y - p1.y)
// x_intersect = p1.x + (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y)
double intersect_x = p1.x + (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y);
// 如果交点在射线的左侧，不计数
if (intersect_x < p.x - EPSILON) {
continue;
}
// 处理交点在顶点上的情况
// 如果交点是p1 (下端点)，且p2在p的上方，则计数。
// 这是为了避免水平射线经过"凸"顶点时，只计数一次。
// 例如，对于一个V形，射线经过V的底部顶点，两侧的边都向上，此时只计数一次。
// 如果射线经过一个"凹"顶点，两侧的边一上一下，则分别计数。
// 但更精确的方法是：只有当边的一个端点在射线之上，另一个在射线之下时才计数。
// 并且，如果点p恰好在顶点上，我们已经在上面通过onSegment处理了。
// 这里的处理是简化版本，仅对严格的穿过进行计数。
// 如果当前边不是水平的，并且射线严格穿过该边
if (std::abs(p1.y - p2.y) > EPSILON) { // 边不是水平的
// 确保交点X坐标大于等于p.x (即交点在p的右侧)
if (intersect_x > p.x - EPSILON) {
// 如果 p.y 和 p1.y 几乎相等，且 p.y 和 p2.y 不相等 (即p点在p1点上，且p2在p的上方或下方)
// 这是一种处理射线穿过顶点的情况，避免重复计数或漏计数
// 核心思想是：只在射线“真正穿过”多边形边界时计数一次
// 这里的条件是：p.y在p1.y和p2.y之间（或等于其中一个）
// 并且交点X坐标在p.x的右侧
// 并且不是水平线
// 正确的逻辑应该是：
// 如果p.y == p1.y (或p2.y)，并且这条边是该顶点处所有边中y值最大的那条，则不计数
// 或者更简单：只有当射线严格穿过边时才计数，不包括射线与顶点重合的情况
// 以下是一个常见的更鲁棒的处理方法：
// 统计射线与多边形边的交点。如果射线经过顶点，
// 并且该顶点的y坐标是射线穿过的所有y坐标中较小的一个，则计数。
// 这种被称为“左下规则”或“半开区间”的计数方法能避免重复。
// 简化为：如果射线穿过边，且不是水平边，则翻转inside状态
// 对于顶点：如果射线恰好经过一个顶点，并且这个顶点不是边p1p2的下端点，则不计数
// 或者更准确：如果射线经过一个顶点，且这个顶点是当前边y值较小的那个点，则计数
// 避免对共享顶点重复计数，例如一条边向上，一条边向下。
// 这里的逻辑是如果p.y == p1.y 或者 p.y == p2.y，则需要判断。
// 如果p.y == p1.y && p.y == p2.y (水平线)，上面已经跳过
// 更通用的处理射线与顶点相交：
// 如果射线经过p1或p2，并且p1或p2的y坐标与p.y相同，
// 则检查其相邻边的y坐标，如果相邻边在p.y的另一侧，则计数。
// 但这种方式复杂，通常简化为以下：
// 只有当边的两个端点一个在射线y之上，一个在射线y之下时才计数
// 或者当一个端点在射线上，另一个端点在射线之上时计数 (视为向上穿过)
// 并且交点X坐标在p.x的右侧
// 考虑 p.y 严格在 p1.y 和 p2.y 之间，或者与其中一个相等但不是水平线
if (p.y > p1.y - EPSILON && p.y < p2.y + EPSILON) { // 射线y在边的y范围内
// 如果交点X在p的右侧，则翻转inside状态
if (intersect_x > p.x - EPSILON) {
// 避免水平边的情况
if (std::abs(p1.y - p2.y) > EPSILON) {
// 避免对顶点处重复计数
// 规则：只对边的“下端点”或“左下端点”进行处理，或者更简单：
// 如果边是向上穿过射线，且p.y和p1.y相等，并且p2.y > p.y，则计数
// 或者如果边是向下穿过射线，且p.y和p2.y相等，并且p1.y > p.y，则计数
// 这是一个常用的简化方法：
// 只有当边的其中一个端点y坐标高于射线y，另一个低于射线y时，才算作穿过
// 并且避免计数水平边
if ((p1.y < p.y && p2.y >= p.y) || (p2.y < p.y && p1.y >= p.y)) {
inside = !inside;
}
}
}
}
}
}
}
return inside;
}这段 isPointInPolygonEvenOdd 代码包含了一些对浮点数比较和特殊情况（如射线穿过顶点）的复杂处理。为了简化和提高可读性，我们可以采用一个更标准的、基于 doSegmentsIntersect 的方法，但需要对射线进行特殊处理。
更简洁和鲁棒的奇偶规则实现（基于射线交点数）：
这里的关键在于如何定义“交点”。一个常见的策略是：
- 射线与水平线段不相交。
- 射线与顶点相交时，如果该顶点是其所在边y坐标的最小值（即该边从该顶点向上延伸），则计数。这通常称为“左开右闭”或“半开区间”规则。
- 如果点在边上，直接返回true。
// 改进版：点在多边形内测试：奇偶规则
bool isPointInPolygonEvenOdd_Robust(const Point2D& p, const std::vector<Point2D>& polygon) {
int n = polygon.size();
if (n < 3) return false;
int intersect_count = 0;
// 构造一条从p点向右的水平射线，终点在无穷远处
Point2D extreme = {std::numeric_limits<double>::max(), p.y};
for (int i = 0; i < n; ++i) {
Point2D p1 = polygon[i];
Point2D p2 = polygon[(i + 1) % n];
// 1. 检查点P是否在多边形的边上
if (onSegment(p1, p, p2)) {
return true; // 如果点在边上，则视为在内部
}
// 2. 检查射线 (p, extreme) 是否与当前边 (p1, p2) 相交
// 确保p1.y <= p2.y，方便后续判断
if (p1.y > p2.y) {
std::swap(p1, p2);
}
// 射线与边不相交的情况：
// a) 边是水平的，且p.y与边共线（已在onSegment中处理或不需计数）
// b) 射线Y坐标完全在边的Y范围之外
if (std::abs(p1.y - p2.y) < EPSILON) continue; // 水平边不计数
if (p.y < p1.y - EPSILON || p.y >= p2.y - EPSILON) continue; // 射线Y在边Y范围外，或在上方顶点上
// 计算射线与边的交点的X坐标
// x_intersect = p1.x + (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y)
double intersect_x = p1.x + (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y);
// 如果交点在射线的右侧，则计数
if (intersect_x > p.x - EPSILON) {
intersect_count++;
}
}
return (intersect_count % 2 == 1);
}解释上述鲁棒实现中的关键点：
p.y < p1.y - EPSILON || p.y >= p2.y - EPSILON: 这个条件很重要。p.y < p1.y - EPSILON表示射线低于边的最低点，不相交。p.y >= p2.y - EPSILON表示射线高于或恰好在边的最高点，不相交。这里使用>=而不是>是为了实现“半开区间”原则，即如果射线恰好穿过一个顶点，我们只在它作为“下端点”时计数，而当它作为“上端点”时不计数，避免重复。std::abs(p1.y - p2.y) < EPSILON: 水平边不计入交点，因为射线是水平的，与水平边重合不能算作穿过。intersect_x > p.x - EPSILON: 只有当交点在测试点p的右侧时才计数。
5. 奇偶规则示例
假设我们有一个星形多边形，其顶点按以下顺序排列：
(0,0), (10,0), (2,8), (5,-3), (8,8), (0,0) (闭合)
如果点 P 在星形的中心，奇偶规则可能会将其判断为外部。
考虑一个简单的多边形和一个带孔洞的多边形：
例1：简单正方形
顶点: (0,0), (10,0), (10,10), (0,10)
测试点: P(5,5)
射线从(5,5)向右。
- 与 (10,0)-(10,10) 相交一次。
交点数 = 1 (奇数) -> 内部。 (正确)
例2：带孔洞的正方形
外环: (0,0), (10,0), (10,10), (0,10)
内环 (孔洞): (3,3), (7,3), (7,7), (3,7)
测试点: P(5,5)
射线从(5,5)向右。
- 与 外环边 (10,0)-(10,10) 相交一次。
- 与 内环边 (7,3)-(7,7) 相交一次。
交点数 = 2 (偶数) -> 外部。 (正确，因为在孔洞里)
例3：自相交星形
顶点: (0,0), (10,0), (2.5,10), (5,-2), (7.5,10) (简化五角星，实际自相交)
测试点: P(5,2) (星形中心区域)
射线从(5,2)向右。
假设星形的中心区域由多边形边缘交叉形成。射线可能穿过两次，交点数为偶数，被判断为外部。这可能不是用户期望的“填充”效果。
// 测试奇偶规则
void testEvenOdd() {
std::cout << "n--- 奇偶规则 (Even-Odd Rule) 测试 ---" << std::endl;
// 1. 简单正方形
std::vector<Point2D> square = {{0,0}, {10,0}, {10,10}, {0,10}};
Point2D p1_inside = {5,5};
Point2D p1_outside = {12,5};
Point2D p1_on_edge = {10,5};
std::cout << "多边形: 正方形 (0,0)-(10,10)" << std::endl;
std::cout << "点 " << p1_inside << " 内部? " << (isPointInPolygonEvenOdd_Robust(p1_inside, square) ? "是" : "否") << std::endl; // 预期: 是
std::cout << "点 " << p1_outside << " 内部? " << (isPointInPolygonEvenOdd_Robust(p1_outside, square) ? "是" : "否") << std::endl; // 预期: 否
std::cout << "点 " << p1_on_edge << " 内部? " << (isPointInPolygonEvenOdd_Robust(p1_on_edge, square) ? "是" : "否") << std::endl; // 预期: 是
// 2. 带孔洞的正方形
std::vector<Point2D> square_with_hole = {
{0,0}, {10,0}, {10,10}, {0,10}, // 外环
{3,3}, {3,7}, {7,7}, {7,3} // 内环 (注意这里是逆时针，通常外环是逆时针，内环是顺时针，但奇偶规则不关心方向)
// 实际上，为了让它成为一个多边形，需要连接。在图形库中通常分开处理。
// 这里为了演示，我们假设这是一个自相交的多边形，形成一个“洞”。
// 但更准确地说，这是多个路径的组合。
// 对于单个自相交多边形，形成孔洞的效果：
// 例如一个八字形 (自相交)
};
// 为了模拟孔洞，我们构造一个自相交的八字形
std::vector<Point2D> figure_eight = {
{0,0}, {10,0}, {10,10}, {0,10}, // 大正方形
{0,0} // 回到起点
};
// 假设我们想测试一个被外边界包围，但被内边界包围的区域 (即孔洞内部)
// 对于奇偶规则，一个点在“洞”里会被判为外部
// 我们可以通过一个更复杂的自相交多边形来模拟孔洞行为
std::vector<Point2D> complex_shape = {
{0,0}, {10,0}, {10,10}, {0,10}, // 外部矩形 CCW
{3,3}, {7,3}, {7,7}, {3,7}, {3,3} // 内部矩形 CW
};
// 如果将它们组合成一个单一的自相交多边形，例如：
std::vector<Point2D> polygon_with_internal_hole = {
{0,0}, {10,0}, {10,10}, {0,10}, // 外环的一部分
{0,0}, // 闭合外环
{3,3}, {7,3}, {7,7}, {3,7}, // 内环 (顺时针)
{3,3} // 闭合内环
};
// 这种直接连接的方式，会形成连接线，导致行为复杂。
// 在实际应用中，带孔多边形通常是多路径结构。
// 但是，我们可以通过一个简单的自相交来模拟奇偶规则对“孔洞”的看法
std::vector<Point2D> self_intersecting_figure = {
{0,0}, {10,0}, {10,10}, {0,10}, // 外框
{5, -5}, // 从底部连到外部
{5, 15}, // 穿过中心
{0,10} // 重新连接到外框
};
// 这是一个更典型的例子来展示奇偶规则对自相交的解释
std::vector<Point2D> star_polygon_eo = {
{0, 5}, {5, 0}, {10, 5}, {7.5, 10}, {2.5, 10}
}; // 这是一个简单的五角星，内凹部分会被视为外部
std::cout << "n多边形: 简单五角星 ({0,5}, {5,0}, {10,5}, {7.5,10}, {2.5,10})" << std::endl;
Point2D star_center = {5, 5};
Point2D star_tip = {5, 12};
Point2D star_inner_point = {5, 3}; // 尖角之间的凹陷区域
Point2D star_outer_point = {1, 1};
std::cout << "点 " << star_center << " 内部? " << (isPointInPolygonEvenOdd_Robust(star_center, star_polygon_eo) ? "是" : "否") << std::endl; // 预期: 是
std::cout << "点 " << star_tip << " 内部? " << (isPointInPolygonEvenOdd_Robust(star_tip, star_polygon_eo) ? "是" : "否") << std::endl; // 预期: 否
std::cout << "点 " << star_inner_point << " 内部? " << (isPointInPolygonEvenOdd_Robust(star_inner_point, star_polygon_eo) ? "是" : "否") << std::endl; // 预期: 是 (在尖角内部)
std::cout << "点 " << star_outer_point << " 内部? " << (isPointInPolygonEvenOdd_Robust(star_outer_point, star_polygon_eo) ? "是" : "否") << std::endl; // 预期: 否 (在外部)
// 真正的自相交五角星（内部区域被“挖空”）
std::vector<Point2D> self_intersecting_star = {
{0.0, 5.0}, {5.0, 0.0}, {10.0, 5.0}, {0.0, 5.0}, // 形成一个三角形 (0,5)-(5,0)-(10,5)
{2.0, 10.0}, {8.0, 10.0}, {5.0, 0.0}, {2.0, 10.0} // 再形成一个三角形
};
// 更标准的自相交五角星
std::vector<Point2D> star_polygon_self_intersecting = {
{0.0, 3.0}, // p0
{1.0, 0.0}, // p1
{4.0, 0.0}, // p2
{1.5, 2.5}, // p3
{3.0, 5.0}, // p4
{2.0, 2.5}, // p5
{0.0, 5.0}, // p6
{2.5, 3.0} // p7
};
// 简化为标准的五角星顶点序列：
// (0,3), (1,0), (4,0), (1.5,2.5), (3,5), (2,2.5), (0,5), (2.5,3)
// 这是为了演示自相交行为，但通常五角星是 (0,3), (1.5,1), (3,3), (0.5,5), (2.5,5) 这种
// 我们用一个简单的交叉线段来模拟自相交
std::vector<Point2D> cross_shape = {
{0,0}, {10,10}, {10,0}, {0,10}
};
std::cout << "n多边形: 交叉形状 ({0,0}, {10,10}, {10,0}, {0,10})" << std::endl;
Point2D cross_center = {5,5};
Point2D cross_side = {1,1};
std::cout << "点 " << cross_center << " 内部? " << (isPointInPolygonEvenOdd_Robust(cross_center, cross_shape) ? "是" : "否") << std::endl; // 预期: 否 (奇偶规则中心是外部)
std::cout << "点 " << cross_side << " 内部? " << (isPointInPolygonEvenOdd_Robust(cross_side, cross_shape) ? "是" : "否") << std::endl; // 预期: 是
}非零规则（Non-Zero Rule）
1. 规则原理
非零规则，也称为“绕数规则”（Winding Number Rule），其核心思想是：
- 从待测试点
P发出一条射线（通常是水平向右的）。 - 对于射线与多边形每条边的交点，根据边的方向（相对于射线）计算一个“绕数”贡献值。
- 如果边从射线的下方穿向上方（向上穿过），绕数加
+1。 - 如果边从射线的上方穿向下方（向下穿过），绕数减
-1。
- 如果边从射线的下方穿向上方（向上穿过），绕数加
- 对所有交点的贡献值求和，得到最终的“绕数”。
- 如果绕数不为零，则点
P在多边形内部。 - 如果绕数为零，则点
P在多边形外部。
这个规则的直观解释是：如果一个点被多边形“包围”了多少圈，以及这些圈的方向。
2. 行为特点
- 简单多边形: 与奇偶规则一样，非零规则对简单多边形工作良好。
- 带孔洞的多边形: 非零规则也能正确识别孔洞。通常，外环是逆时针（贡献正绕数），内环（孔洞）是顺时针（贡献负绕数）。如果一个点在孔洞内部，它会得到一个正绕数（来自外环）和一个负绕数（来自内环），两者抵消后，总绕数可能为零，从而被视为外部。如果内外环方向相同，则孔洞会被填充。
- 自相交多边形: 这是非零规则的强大之处。对于自相交多边形，即使射线穿过边界多次，只要绕数不为零，该区域就会被视为内部。这意味着，一个星形的中心区域，即使奇偶规则会将其视为外部，非零规则通常会将其视为内部，因为它被多边形“绕”了几圈。
3. 实现细节与挑战
- 边的方向: 这是非零规则的关键。我们需要知道每条边是向上还是向下穿过射线。这需要比较边的两个端点的
y坐标。 - 贡献值:
- 如果边
(v1, v2)向上穿过射线（即v1.y < p.y且v2.y > p.y），且交点在射线右侧，则绕数加+1。 - 如果边
(v1, v2)向下穿过射线（即v1.y > p.y且v2.y < p.y），且交点在射线右侧，则绕数减-1。
- 如果边
- 特殊情况: 与奇偶规则类似，需要处理射线穿过顶点和水平边的情况。通常采用与奇偶规则类似的“半开区间”原则，以避免重复计数。
4. 代码实现 (isPointInPolygonNonZero)
实现非零规则需要更精细地处理边的方向。
// 点在多边形内测试：非零规则（绕数规则）
bool isPointInPolygonNonZero(const Point2D& p, const std::vector<Point2D>& polygon) {
int n = polygon.size();
if (n < 3) return false;
int winding_number = 0;
for (int i = 0; i < n; ++i) {
Point2D p1 = polygon[i];
Point2D p2 = polygon[(i + 1) % n];
// 1. 检查点P是否在多边形的边上
if (onSegment(p1, p, p2)) {
return true; // 如果点在边上，则视为在内部
}
// 处理水平线段：它们不改变绕数
if (std::abs(p1.y - p.y) < EPSILON && std::abs(p2.y - p.y) < EPSILON) {
continue;
}
// 2. 检查边 (p1, p2) 是否跨越了射线 (p.y)
// 向上穿过射线 (从下到上)
if (p1.y <= p.y - EPSILON && p2.y > p.y + EPSILON) { // p1在射线之下或之上，p2在射线之上
// 计算射线与边的交点X坐标
// x_intersect = p1.x + (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y)
double intersect_x = p1.x + (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y);
// 如果交点在p的右侧，则增加绕数
if (intersect_x > p.x - EPSION) {
winding_number++;
}
}
// 向下穿过射线 (从上到下)
else if (p1.y > p.y + EPSILON && p2.y <= p.y - EPSILON) { // p1在射线之上，p2在射线之下或之上
// 计算射线与边的交点X坐标
double intersect_x = p1.x + (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y);
// 如果交点在p的右侧，则减少绕数
if (intersect_x > p.x - EPSILON) {
winding_number--;
}
}
// 考虑p点与顶点共线的情况，例如 p.y == p1.y
else if (std::abs(p1.y - p.y) < EPSILON) { // p的y坐标与p1的y坐标相同
// 如果p1在p的右侧，并且p2在p的上方，则视为向上穿过
if (p1.x > p.x - EPSILON && p2.y > p.y + EPSILON) {
winding_number++;
}
// 如果p1在p的右侧，并且p2在p的下方，则视为向下穿过 (这里可能与上面一个分支重复计数)
// 这种处理顶点的方式可能导致重复。更安全的做法是，当射线穿过顶点时，
// 只有当该顶点是边的“下端点”时才计数。
}
}
return winding_number != 0;
}对 isPointInPolygonNonZero 的修正和优化：
上述 isPointInPolygonNonZero 的处理方式在处理顶点和浮点数时可能不够鲁棒。一个更简洁和标准的实现方式是避免直接比较 p.y 与 p1.y 和 p2.y 的相等性，而是使用 p.y 严格在 p1.y 和 p2.y 之间，并结合叉积判断交点是否在射线右侧。
// 改进版：点在多边形内测试：非零规则（绕数规则）
bool isPointInPolygonNonZero_Robust(const Point2D& p, const std::vector<Point2D>& polygon) {
int n = polygon.size();
if (n < 3) return false;
int winding_number = 0;
for (int i = 0; i < n; ++i) {
Point2D p1 = polygon[i];
Point2D p2 = polygon[(i + 1) % n];
// 1. 检查点P是否在多边形的边上
if (onSegment(p1, p, p2)) {
return true; // 如果点在边上，则视为在内部
}
// 2. 判断边 (p1, p2) 对绕数的影响
// 核心思想：当且仅当边跨越了射线 (p, extreme) 且交点在p的右侧时，才计算绕数贡献。
// 这里的逻辑是：
// - 如果 p1.y <= p.y 且 p2.y > p.y：边向上穿过射线
// - 如果 p1.y > p.y 且 p2.y <= p.y：边向下穿过射线
// 同时需要保证交点在p的右侧。
// 为了避免浮点数误差和处理顶点问题，可以使用叉积来判断点p相对于边的位置。
// Cross product: (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x)
// 如果大于0，p在边(p1,p2)的左侧。
// 如果小于0，p在边(p1,p2)的右侧。
// 如果等于0，p在边(p1,p2)上。
if (p1.y <= p.y - EPSILON) { // P1在射线下方或与射线y坐标相同
if (p2.y > p.y + EPSILON) { // P2在射线上方，向上穿过
// 判断P点是否在边(p1,p2)的左侧，即交点在射线右侧
// (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x)
// 计算 x 坐标的交点，并检查它是否在 p 的右侧
double cross_product_val = (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x);
if (cross_product_val > EPSILON) { // P在边左侧 (交点在射线右侧)
winding_number++;
}
}
} else if (p1.y > p.y + EPSILON) { // P1在射线上方
if (p2.y <= p.y - EPSILON) { // P2在射线下方或与射线y坐标相同，向下穿过
// 判断P点是否在边(p1,p2)的右侧，即交点在射线右侧
double cross_product_val = (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x);
if (cross_product_val < -EPSILON) { // P在边右侧 (交点在射线右侧)
winding_number--;
}
}
}
}
return winding_number != 0;
}解释上述鲁棒实现中的关键点：
p1.y <= p.y - EPSILON和p2.y > p.y + EPSILON：这两个条件定义了边向上穿过射线的情况。EPSILON的使用确保了浮点数比较的鲁棒性，并且隐式处理了顶点情况（避免当p.y恰好等于p1.y或p2.y时多次计数）。cross_product_val > EPSILON和cross_product_val < -EPSILON：这里是关键。cross_product_val实际上计算的是点p相对于向量(p1, p2)的位置。- 当边向上穿过 (
p1.y<p.y<p2.y)，如果p在边(p1, p2)的左侧（即cross_product_val > 0），则说明射线(p, extreme)会与该边相交，并且交点在p的右侧，因此winding_number++。 - 当边向下穿过 (
p1.y>p.y>p2.y)，如果p在边(p1, p2)的右侧（即cross_product_val < 0），则说明射线(p, extreme)会与该边相交，并且交点在p的右侧，因此winding_number--。
- 当边向上穿过 (
- 这种方法比直接计算交点
x_intersect再与p.x比较更加稳定，因为它避免了潜在的除以零错误（当p2.y - p1.y接近零时）和复杂的x_intersect比较。
5. 非零规则示例
继续使用奇偶规则的示例。
例1：简单正方形
顶点: (0,0), (10,0), (10,10), (0,10) (逆时针)
测试点: P(5,5)
射线从(5,5)向右。
- 与 (10,0)-(10,10) 向上穿过，
winding_number++-> 1。
绕数 = 1 (非零) -> 内部。 (正确)
例2：带孔洞的正方形
外环: (0,0), (10,0), (10,10), (0,10) (逆时针)
内环 (孔洞): (3,3), (7,3), (7,7), (3,7) (顺时针)
测试点: P(5,5)
射线从(5,5)向右。
- 与 外环边 (10,0)-(10,10) 向上穿过，
winding_number++-> 1。 - 与 内环边 (7,3)-(7,7) 向下穿过，
winding_number---> 0。
绕数 = 0 (零) -> 外部。 (正确，因为在孔洞里)
例3：自相交星形
顶点: (0,0), (10,0), (2.5,10), (5,-2), (7.5,10) (简化五角星，实际自相交)
测试点: P(5,2) (星形中心区域)
射线从(5,2)向右。
非零规则会计算该点被多边形“绕”了多少圈。对于一个典型的自相交五角星，中心区域的绕数通常为1，因此被判断为内部。这符合大多数人对“填充”自相交形状的期望。
// 测试非零规则
void testNonZero() {
std::cout << "n--- 非零规则 (Non-Zero Rule) 测试 ---" << std::endl;
// 1. 简单正方形 (逆时针)
std::vector<Point2D> square_ccw = {{0,0}, {10,0}, {10,10}, {0,10}};
Point2D p1_inside = {5,5};
Point2D p1_outside = {12,5};
Point2D p1_on_edge = {10,5};
std::cout << "多边形: 正方形 (CCW)" << std::endl;
std::cout << "点 " << p1_inside << " 内部? " << (isPointInPolygonNonZero_Robust(p1_inside, square_ccw) ? "是" : "否") << std::endl; // 预期: 是 (绕数1)
std::cout << "点 " << p1_outside << " 内部? " << (isPointInPolygonNonZero_Robust(p1_outside, square_ccw) ? "是" : "否") << std::endl; // 预期: 否 (绕数0)
std::cout << "点 " << p1_on_edge << " 内部? " << (isPointInPolygonNonZero_Robust(p1_on_edge, square_ccw) ? "是" : "否") << std::endl; // 预期: 是
// 2. 带孔洞的正方形 (外环CCW, 内环CW)
// 实际实现中，通常会用多路径表示带孔多边形。
// 在这里，为了演示非零规则对方向的敏感性，我们构造一个自相交的多边形，
// 其内部区域行为类似孔洞。
// 例如，一个外环逆时针，内环顺时针的多边形：
// Path1: (0,0)-(10,0)-(10,10)-(0,10) (CCW)
// Path2: (3,3)-(3,7)-(7,7)-(7,3) (CW)
// 我们可以通过一个复杂的单路径来模拟，但这不是一个好的实践。
// 更准确的演示是：假设一个外框是CCW，一个内框是CW。
// 对于非零规则，如果内外框方向相反，内部区域的绕数会抵消为0。
// 这与奇偶规则对孔洞的处理结果一致。
std::vector<Point2D> outer_ccw_inner_cw_polygon = {
{0,0}, {10,0}, {10,10}, {0,10}, // 外环 CCW
{5,10}, {5,0}, // 连接线 (穿过)
{7,3}, {7,7}, {3,7}, {3,3}, // 内环 CW
{5,0}, {5,10} // 连接线 (穿过)
};
// 这种直接连接的方式，会形成连接线，导致行为复杂。
// 我们用一个更简单的自相交例子来展示非零规则对自相交的看法
// 这是一个典型的五角星，中心区域会被视为内部
std::vector<Point2D> star_polygon_nz = {
{0.0, 3.0}, // p0
{5.0, 0.0}, // p1
{10.0, 3.0}, // p2
{8.0, 8.0}, // p3
{2.0, 8.0} // p4
};
// 这是一个标准的非自相交五角星，内部区域为内部。
// 如果是自相交的五角星，它的中心区域在奇偶规则下可能为外部，但在非零规则下通常为内部。
std::vector<Point2D> self_intersecting_star_nz = {
{0.0, 3.0}, {5.0, 0.0}, {10.0, 3.0}, {2.0, 8.0}, {8.0, 8.0}
}; // 这是一个自相交的五角星，中心区域在非零规则下是内部
std::cout << "n多边形: 自相交五角星 ({0,3}, {5,0}, {10,3}, {2,8}, {8,8})" << std::endl;
Point2D star_center_nz = {5, 5};
Point2D star_inner_point_nz = {5, 3}; // 尖角之间的凹陷区域
Point2D star_outer_point_nz = {1, 1};
std::cout << "点 " << star_center_nz << " 内部? " << (isPointInPolygonNonZero_Robust(star_center_nz, self_intersecting_star_nz) ? "是" : "否") << std::endl; // 预期: 是 (绕数 != 0)
std::cout << "点 " << star_inner_point_nz << " 内部? " << (isPointInPolygonNonZero_Robust(star_inner_point_nz, self_intersecting_star_nz) ? "是" : "否") << std::endl; // 预期: 是
std::cout << "点 " << star_outer_point_nz << " 内部? " << (isPointInPolygonNonZero_Robust(star_outer_point_nz, self_intersecting_star_nz) ? "是" : "否") << std::endl; // 预期: 否
// 交叉形状
std::vector<Point2D> cross_shape = {
{0,0}, {10,10}, {10,0}, {0,10}
};
std::cout << "n多边形: 交叉形状 ({0,0}, {10,10}, {10,0}, {0,10})" << std::endl;
Point2D cross_center = {5,5};
Point2D cross_side = {1,1};
std::cout << "点 " << cross_center << " 内部? " << (isPointInPolygonNonZero_Robust(cross_center, cross_shape) ? "是" : "否") << std::endl; // 预期: 是 (非零规则中心是内部)
std::cout << "点 " << cross_side << " 内部? " << (isPointInPolygonNonZero_Robust(cross_side, cross_shape) ? "是" : "否") << std::endl; // 预期: 是
}奇偶规则与非零规则的差异比较
我们通过一个表格来清晰地对比这两种规则在不同场景下的行为：
| 特性/规则 | 奇偶规则 (Even-Odd Rule) | 非零规则 (Non-Zero Rule) |
|---|---|---|
| 基本原理 | 射线与多边形边的交点数量的奇偶性。 | 射线与多边形边的方向性交点（绕数）的总和是否为零。 |
| 简单多边形 | 行为一致，都正确判断内部。 | 行为一致，都正确判断内部。 |
| 带孔洞多边形 | 能够正确识别孔洞（孔洞内部为外部）。 | 能够正确识别孔洞（通常通过内外环方向相反来实现）。 |
| 自相交多边形 | 可能会将某些“被包围”的区域视为外部 (例如星形中心)。 | 通常会将所有“被包围”的区域视为内部 (例如星形中心)。 |
| “内部”定义 | 更接近“拓扑学”上的内部，即仅通过简单边界区分内外。 | 更接近“几何学”上的内部，考虑多边形如何“缠绕”点。 |
| 实现复杂度 | 相对简单，主要处理射线与边的交点计数。 | 略复杂，需要判断边的方向和绕数贡献。 |
| 典型应用 | 图形渲染、填充（如CSS的fill-rule: evenodd）、简单区域填充。 |
CAD/CAM、矢量图形处理、复杂几何体建模、路径规划（如SVG的fill-rule: nonzero）。 |
| 对顶点方向敏感度 | 不敏感。 | 敏感。 |
执行测试函数：
int main() {
testEvenOdd();
testNonZero();
return 0;
}叶轮路径填充算法中的应用
现在，让我们将这些理论知识带入实际的叶轮（Impeller）路径填充算法中。叶轮是涡轮机械的核心部件，其三维形状复杂，通常包含多个叶片、轮毂和盖板。在进行数控加工（CNC machining）时，我们需要将三维模型切片成一系列二维横截面，然后为每个横截面生成刀具路径。
1. 叶轮几何特征与挑战
- 复杂截面: 叶轮的横截面可能包含多个独立区域（例如，叶片厚度、轮毂），也可能有自相交的轮廓（例如，由于复杂曲面投影到2D平面时产生）。
- 孔洞与凹陷: 叶轮设计中可能包含冷却孔、减重孔或复杂的流道结构，这些在2D截面上表现为孔洞。
- 重叠区域: 多个叶片或叶片与轮毂的交叠投影可能产生复杂的重叠区域。
- 粗加工与精加工: 不同的加工阶段对“内部”的定义可能有细微差别。
2. 奇偶规则在叶轮路径中的应用
- 场景: 如果我们希望严格按照多边形的拓扑边界进行填充，例如，将所有“孔洞”都明确视为不填充区域。
- 优点:
- 直观: 对于没有自相交的叶轮截面，奇偶规则的行为非常直观，能够很好地识别孔洞。
- 避免过度填充: 它不会填充自相交区域中的“内部空腔”，这在某些情况下可能是期望的行为，例如，如果这些区域被视为设计上的非材料区域。
- 缺点:
- 自相交处理: 如果叶轮的2D投影或横截面存在自相交轮廓，奇偶规则可能会将一些视觉上应被填充的区域（例如，自相交星形的中心）视为外部，从而导致刀具路径遗漏这些区域，造成加工不完整。
3. 非零规则在叶轮路径中的应用
- 场景: 在大多数CAD/CAM场景中，尤其是处理复杂或自相交的几何体时，非零规则是更常用和推荐的选择。
- 优点:
- 鲁棒的“内部”定义: 非零规则能够更稳定地定义自相交多边形的“内部”。对于叶轮的复杂截面，它能确保所有被多边形“包围”的材料区域都被识别出来，即使这些区域在奇偶规则下可能被跳过。
- 处理重叠区域: 对于多个叶片投影产生的重叠区域，非零规则通常能正确识别这些区域为需要加工的“实体”部分。
- 适应复杂流道: 在处理叶轮内部的复杂流道（可能在2D投影中产生自相交）时，非零规则能更准确地识别流道壁的实体部分。
- 缺点:
- 孔洞方向敏感: 如果孔洞的轮廓方向与外部轮廓方向相同，非零规则可能会错误地将孔洞内部视为需要填充的区域。因此，在实际应用中，处理带孔洞的多边形时，需要确保孔洞轮廓的方向与外部轮廓方向相反。这通常通过几何处理库来保证。
4. 实际应用中的考量与组合策略
在叶轮的加工路径生成中，单一的绕数规则可能不足以应对所有复杂情况。通常会采取以下策略：
- 几何预处理: 在应用绕数规则之前，对叶轮的2D截面进行几何预处理是至关重要的。这包括：
- 轮廓分解: 将复杂的自相交多边形分解为一系列简单的（非自相交）多边形。
- 孔洞识别: 明确区分外轮廓和内轮廓（孔洞），并确保它们的方向性（例如，外轮廓逆时针，内轮廓顺时针）。
- 布尔运算: 利用布尔运算（并集、差集、交集）来组合和简化复杂的几何区域。这些布尔运算的底层实现也依赖于绕数规则。
- 分层填充: 叶轮的加工通常是分层的。每一层都需要精确的内外判断。
- 混合使用:
- 粗加工: 在粗加工阶段，可能更倾向于使用非零规则，以确保清除所有“实体”材料，避免遗漏。
- 精加工: 在精加工阶段，可能需要更精细的控制，此时可能根据具体区域的拓扑结构选择性地应用奇偶规则或非零规则。
- CAD/CAM系统内置功能: 现代的CAD/CAM软件（如NX CAM, Mastercam, Catia）通常在其刀具路径生成模块中内置了对这些绕数规则的鲁棒实现。用户通常不需要直接选择规则，而是通过定义几何特征（如“口袋”、“岛屿”）来间接应用这些规则。
性能优化与数值稳定性
无论采用哪种绕数规则，性能和数值稳定性都是实际应用中不可忽视的因素。
1. 性能优化
- 包围盒测试 (Bounding Box Test): 在进行详细的射线交点计算之前，首先检查待测试点是否位于多边形的包围盒（Axis-Aligned Bounding Box, AABB）内。如果不在，则点肯定在外部，可以快速排除。
- 空间划分结构 (Spatial Partitioning Structures): 对于包含大量顶点或多个多边形的复杂场景，可以构建如K-D树、四叉树或R树等空间划分结构。这允许我们只检查与射线可能相交的那些多边形边，而非所有边，从而显著减少计算量。
- 扫描线算法 (Scanline Algorithm): 对于需要填充整个区域而不是单个点的场景，扫描线算法更为高效。它沿着一个方向（通常是Y轴）扫描，维护与当前扫描线相交的边列表，并直接生成填充区域。
2. 数值稳定性
- 浮点数比较: 在所有几何计算中（如判断点是否共线、是否相等），都必须使用一个小的容差
EPSILON来代替直接的==比较。这能有效处理浮点数精度问题。 - 退化情况:
- 水平边: 射线与水平边重合。
- 顶点相交: 射线恰好穿过一个或多个顶点。
- 共线段: 多边形边是共线的。
- 零长度边: 多边形包含重复的顶点。
- 鲁棒的实现需要细致地处理这些情况，确保它们不会导致错误计数或除以零。我们前面展示的改进版实现已经考虑了这些因素。
总结
奇偶规则和非零规则是计算几何中用于定义多边形内部区域的两种核心算法。它们在处理简单多边形时行为一致，但在面对带孔洞和自相交的复杂多边形时展现出显著差异。奇偶规则提供了一种更“拓扑”的内部定义，而非零规则则提供了一种更“几何”的、考虑缠绕方向的内部定义。
在叶轮路径规划等CAD/CAM应用中，非零规则通常是处理复杂几何体，尤其是有自相交区域时的首选，因为它能更鲁棒地识别所有被包围的材料区域。然而，具体的选择和实现策略需要结合几何预处理、孔洞方向管理以及对数值稳定性的细致考量。理解这些规则的底层原理和实现细节，是构建高效、精确的几何处理系统不可或缺的基础。