``` 检查点是否在多边形内（射线法） bool containsPoint(const Point2D& point) const { if (size() < 3) return false; int intersections = 0; int n = size(); for (int i = 0; i < n; ++i) { int j = (i + 1) % n; Point2D p1 = at(i); Point2D p2 = at(j); if 1) && (point.x < (p2.x - p1.x) * (point.y - p1.y) / (p2.y - p1.y) + p1.x)) { intersections++; } } return (intersections % 2) == 1; } ``` 射线法（Ray Casting）的核心思想： 从待测点出发向右（或任意固定方向）画一条水平无限长射线，数它与多边形边的相交次数。 如果奇数次相交 → 点在内部；偶数次 → 点在外部。 1. 为什么“奇偶”能区分内外？ 想象站在多边形里往外走： 每“穿过”一条边就改变一次内外状态（里→外 或 外→里）。 最终状态只由穿越次数的奇偶性决定。 2. 代码逐行对照射线法 ``` bool containsPoint(const Point2D& point) const { if (size() < 3) return false; 少于3点不是多边形
int intersections = 0; // 交点计数器 int n = size();
for (int i = 0; i < n; ++i) {
int j = (i + 1) % n; // 下标循环，首尾闭合
Point2D p1 = at(i); // 当前边起点
Point2D p2 = at(j); // 当前边终点
// 1. 快速排除：边的两端 y 都在射线上方或下方 → 无交
if ((p1.y > point.y) != (p2.y > point.y)) {
// 2. 计算边与射线 x = point.x 的交点横坐标
double xIntersect = (p2.x - p1.x) * (point.y - p1.y) / (p2.y - p1.y) + p1.x;
// 3. 交点在射线右侧（>point.x）才计数
if (point.x < xIntersect)
intersections++;
}
}
// 奇数次 → 内；偶数次 → 外
return (intersections % 2) == 1;
} ``` 3. 特殊情形处理（代码已隐含） 水平边：p1.y == p2.y 时条件 (p1.y > point.y) != (p2.y > point.y) 为假，被自动跳过。 穿过顶点：只算一次交；本算法因“>”与“<”严格，不会重复计数。 点在边上：可视为“内”或“外”，需额外判等若需要严格边界。 4. 一句话总结 射线法就是： “向右发一支箭，数穿了几层墙，奇数层在里，偶数层在外。”
张叶安