射线投射法

发表于 本文字数： 978 阅读时长 ≈ 4 分钟

射线检测法

经常用于判断点是否在多边形内部，可用于处理非凸多边形，不要求顺时针逆时针，该算法的思路十分巧妙：

从目标点向任意约定方向，通常选 右侧（X 轴正方向） 发射一条无限长的水平射线，统计这条射线与多边形边的相交次数

  • 奇数 → 点在多边形内部
  • 偶数 → 点在多边形外部

不多介绍，下文主要说下算法的两个形式和优化变体。

通过交点

存在顶点 $\bm{p}_i$、$\bm{p}_j$ 和待检测点 $\bm{pos}$ ，求过 $\bm{pos}$ 平行于 $x$ 轴的直线与直线 $\bm{p}_i ,\bm{p}_j$ 相交，有：
$$
\bm{p}_i + m \cdot{\bm{d}_i} = \bm{pos} + n\cdot{\bm{R}}
$$
其中 $\bm{d}_i = \bm{p}_j - \bm{p}_i, \bm{R} = Vector2.right$

变量是m和n，我们可以选择叉积来约掉一个变量。

形式1

约掉n，有：
$$
D(\bm{R}, \bm{p}_i) + m\cdot{D(\bm{R}, \bm{d}_i)} = D(\bm{R}, \bm{pos})
$$
移项：
$$
m = \cfrac{D(\bm{R}, \bm{pos}-\bm{p}_i)}{D(\bm{R}, \bm{d}_i)}
= \cfrac{D(\bm{R}, \bm{pos}-\bm{p}_i)}{D(\bm{R}, \bm{p}_j - \bm{p}_i)}
$$
由于 $\bm{R}$ 是 $Vector2.right$ 分子分母都可以简化：
$$
m = \cfrac{pos_y - p_{iy}}{p_{jy} - p_{iy}}
$$
带入线段公式求得交点
$$
hitX = p_{ix} + \cfrac{pos_y - p_{iy}}{p_{jy} - p_{iy}} \cdot{(p_{jx} - p_{ix})}
$$
只要hitX大于等于当前的posX就可判断相交：
$$
hitX \ge{pos_x} => 相交
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/// <summary>
/// 不要求凸
/// 不要求逆/顺时针，混用都行
/// 不要求顺序，跳跃处理都行
/// </summary>
private static bool Inside(Vector2 pos, Polygon polygon)
{
    var vertices = polygon.vertices;
    var length = vertices.Count;
    var inside = false;
    for (int j = 0, i = length - 1; j < length; i = j++)
    {
        var pi = vertices[i];
        var pj = vertices[j];
        // 在Y轴方向不存在交点的可能性
        if ((pi.y > pos.y) == (pj.y > pos.y)) continue;
        // 进行香蕉判定
        var m = (pos.y - pi.y) / (pj.y - pi.y);
        var hitX = pi.x + m * (pj.x - pi.x);
        if (hitX >= pos.x) inside = !inside;
    }
    return inside;
}

形式2

通过叉积 $D(..)$ 约掉m，有：
$$
D(\bm{d}_i, \bm{p}_i) = D(\bm{d}_i, \bm{pos}) + n\cdot{D(\bm{d}_i, \bm{R})}
$$
移项：
$$
n = \cfrac{D(\bm{d}_i, \bm{p}_i-\bm{pos})}{D(\bm{d}_i, \bm{R})}
= \cfrac{D(\bm{p}_j - \bm{p}_i, \bm{p}_i-\bm{pos})}{D(\bm{p}_j - \bm{p}_i, \bm{R})}
$$
由于 $\bm{R}$ 是 $Vector2.right$ 分母可以简化为标量：
$$
n = \cfrac{D(\bm{p}_j - \bm{p}_i, \bm{p}_i-\bm{pos})}{p_{iy}-p_{jy}}
$$
n是 $\bm{pos}$ 引出的向右射线的相交时系数，因此当n大于等于0时，代表交点在右侧，也即是相交。如果n小于0，代表交点在左侧，也就代表与射线不相交。
$$
n \ge{0} => 相交
$$

1
2
3
4
5
// 在Y轴方向不存在交点的可能性
if ((pi.y > pos.y) == (pj.y > pos.y)) continue;
// 进行香蕉判定
var n = Det(pj - pi, pi - pos) / (pi.y - pj.y);
if (n >= 0) inside = !inside;

形式1（无除法版本）

将形式1的不等式拿过来：
$$
p_{ix} + \cfrac{pos_y - p_{iy}}{p_{jy} - p_{iy}} \cdot{(p_{jx} - p_{ix})} \ge{pos_x}
$$
两边乘以 $(p_{jy} - p_{iy})^2$，得：
$$
(pos_y - p_{iy}) \cdot{(p_{jx} - p_{ix})}
\ge{(pos_x - p_{ix})\cdot{(p_{jy} - p_{iy})^2}}
$$
化为叉积形式：
$$
D(\bm{pos} - \bm{p}_i, \bm{p}_j - \bm{p}_i)\cdot{(p_{jy} - p_{iy})} \le{0}
$$

1
2
3
4
5
6
if ((pi.y > pos.y) == (pj.y > pos.y)) continue;
// 进行几何判定，可以内联展开避免临时创建Vector2
var det = Det(pos - pi, pj - pi);
// 如果担心浮点数乘法越界，可以用三目运算
// if ((pj.y < pi.y) ? (det <= 0) : (det >= 0)) inside = !inside;
if (det * (pj.y - pi.y) < 0) inside = !inside;

形式2（无除法版本）

将形式2的不等式拿过来：
$$
n = \cfrac{D(\bm{p}_j - \bm{p}_i, \bm{p}_i-\bm{pos})}{p_{iy}-p_{jy}} \ge{0}
$$
两边乘以 $(p_{iy}-p_{jy})^2$，得：
$$
D(\bm{p}_j - \bm{p}_i, \bm{p}_i-\bm{pos})\cdot{(p_{iy}-p_{jy})} \ge{0}
$$
调整叉积第二个参数顺序、叉积顺序以及后面的乘法内的减法顺序，最终得到：
$$
D(\bm{pos} - \bm{p}_i, \bm{p}_j - \bm{p}_i)\cdot{(p_{jy} - p_{iy})} \le{0}
$$
这下殊途同归了

效果