直骨架的研究:射线法

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

直骨架的研究:射线法 [2025/10/14 17:20] – 创建 张叶安直骨架的研究:射线法 [2025/10/14 17:25] (当前版本) – 张叶安
行 23: 行 23:
  
 ``` ```
 +
 +
 +射线法（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. 一句话总结
 +射线法就是：
 +“向右发一支箭，数穿了几层墙，奇数层在里，偶数层在外。”
Detach Close

该主题尚不存在

您访问的页面并不存在。如果允许，您可以使用创建该页面按钮来创建它。

  • 直骨架的研究/射线法.1760433632.txt.gz
  • 最后更改: 2025/10/14 17:20
  • 由 张叶安