射线投射法

发表于 2026-04-18 更新于 2026-04-19 本文字数： 2.2k 阅读时长 ≈ 8 分钟

射线检测法

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

从目标点向任意约定方向，通常选 右侧（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} => 相交
$$

/// <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} => 相交
$$

// 在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;

形式3（形式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}
$$

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;

形式3（形式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}
$$
这下殊途同归了

Optimized

形式3（标量展开）

前面的代码都是学习用途的玩具，比如Det(pj - pi, pi - pos)这一句，它会调用Vector2.operator-生成新的Vector压栈，而且是跨程序集的，Mono可能都没法内联，更无法让 JIT 执行”结构体标量替换”（Scalar Replacement of Aggregates）——将结构体字段打散为独立标量并分配到寄存器。所以其实前文给的代码里，形式1的代码反而是最快。因此针对这种每个格子都要调用的热路径，手动展开标量运算是必要的！

1
2
3

var det = (pos.x - pi.x) * (pj.y - pi.y) - (pos.y - pi.y) * (pj.x - pi.x);
if (det * (pj.y - pi.y) < 0)
    inside = !inside;

形式4

其次就是在学习这个代码的时候，首先我们是在一行里顺序检测的，这样的话岂不是包含很多重复运算？我想了想，我们可以在做射线检测计算交点的x轴坐标，并保存与所有边相交时交点里最近的哪一个x坐标nearestX，返回给外部后，外部在这一行继续遍历格子时，只要小于先前计算时得到的nearestX就直接复用上一次计算的状态就行了，不必重复计算。

这个优化形式上和扫描线填充（Scanline Fill）很相似，它是计算当前y与所有边的交点，然后对交点排序，最后在相邻交点之间填充像素（1~2交点填充，2~3不填充，3~4填充，以此类推），之前大学学习计算机图形学里大名鼎鼎的“活性边表（Active Edge Table, AET）”。而我这里的优化相当于它的一个“惰性变体”，不预计算交点，只追踪最近的那个。这对简单多边形来说效果极好。

private static void CoreOptimized(MapGrid mapGrid, Polygon polygon, int minX, int minY, int maxX, int maxY, List<int> grids)
{
    float nearestX = float.MinValue;
    bool preInside = false;
    for (var y = minY; y < maxY; y++)
    {
        for (var x = minX; x < maxX; x++)
        {
            var worldX = mapGrid.min.x + (x + 0.5f) * mapGrid.gridSize;
            var worldY = mapGrid.min.y + (y + 0.5f) * mapGrid.gridSize;
            if (nearestX <= worldX)
            {
                var worldPos = new Vector2(worldX, worldY);
                preInside = Inside4(worldPos, polygon, out nearestX);
            }
            if (preInside) grids.Add(y * mapGrid.Col + x);
        }
        nearestX = float.MinValue;
    }
}

/// <summary>
/// 利用扫描连贯性，跳过重复计算
/// </summary>
private static bool Inside4(Vector2 pos, Polygon polygon, out float nearestX)
{
    nearestX = float.MaxValue;
    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];
        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;
            nearestX = nearestX > hitX ? hitX : nearestX;
        }
    }
    return inside;
}

效率展示

形式	耗时（ms）
形式1	21.8
形式2（未进行标量展开）	37.1
形式3（未进行标量展开）	35.8
形式3（标量展开）	20.5
形式4	1.70

测试的是一张500x500的格子地图，里面有四个凸多边形（该算法可以处理凹的），如下图所示。（下图的格子是25x25，方便看覆盖区域的，多边形一致），从结果来看：

可能是没能成功内联导致的形式1~3，对比之下标量展开提升还是很明显的
对比其他形式和形式4，多余性能都被浪费在了重复计算了，加上由于全是凸多边形，形式4的优化才能有这种效果。

扫描线方法

刚才改进的方法很像扫描线方法，这里直接实现了扫描线方法以供参考：

public static class ScanLine
{
    public static void GetCoveredGrid(MapGrid mapGrid, Polygon polygon, List<int> grids)
    {
        var vertices = polygon.vertices;
        var n = vertices.Count;
        var minPoint = new Vector2(float.MaxValue, float.MaxValue);
        var maxPoint = new Vector2(float.MinValue, float.MinValue);
        for (var i = 0; i < n; i++)
        {
            var point = vertices[i];
            minPoint.x = Mathf.Min(minPoint.x, point.x);
            minPoint.y = Mathf.Min(minPoint.y, point.y);
            maxPoint.x = Mathf.Max(maxPoint.x, point.x);
            maxPoint.y = Mathf.Max(maxPoint.y, point.y);
        }

        var relaMinPoint = minPoint - mapGrid.min;
        var relaMaxPoint = maxPoint - mapGrid.min;
        var minCol = Mathf.Max(Utilities.FloorToInt(relaMinPoint.x * mapGrid.GridSizeInv), 0); // 闭区间
        var minRow = Mathf.Max(Utilities.FloorToInt(relaMinPoint.y * mapGrid.GridSizeInv), 0); // 闭区间
        var maxCol = Mathf.Min(Utilities.CeilToInt(relaMaxPoint.x * mapGrid.GridSizeInv), mapGrid.Col); // 开区间
        var maxRow = Mathf.Min(Utilities.CeilToInt(relaMaxPoint.y * mapGrid.GridSizeInv), mapGrid.Row); // 开区间

        Core(mapGrid, polygon.vertices, minCol, minRow, maxCol, maxRow, grids);
    }

    private static readonly List<float> Temp = new(16);
    private static void Core(MapGrid mapGrid, List<Vector2> vertices, int minX, int minY, int maxX, int maxY, List<int> grids)
    {
        for (var y = minY; y < maxY; y++)
        {
            var worldY = mapGrid.min.y + (y + 0.5f) * mapGrid.gridSize;
            Intersect(vertices, worldY);
            Temp.Sort();
            var m = Temp.Count;
            for (var i = 0; i + 1 < m; i += 2)
            {
                var lc = Mathf.Max(Utilities.FloorToInt((Temp[i] - mapGrid.min.x) * mapGrid.GridSizeInv + 0.5f), 0);
                var rc = Mathf.Min(Utilities.FloorToInt((Temp[i + 1] - mapGrid.min.x) * mapGrid.GridSizeInv - 0.5f), mapGrid.Col - 1);
                for (var j = lc; j <= rc; j++)
                {
                    grids.Add(y * mapGrid.Col + j);
                }
            }
        }
    }

    private static void Intersect(List<Vector2> vertices, float worldY)
    {
        Temp.Clear();
        var n = vertices.Count;
        for (int j = 0, i = n - 1; j < n; i = j++)
        {
            var pi = vertices[i];
            var pj = vertices[j];
            if ((pi.y > worldY) == (pj.y > worldY)) continue;
            var m = (worldY - pi.y) / (pj.y - pi.y);
            var hitX = pi.x + m * (pj.x - pi.x);
            Temp.Add(hitX);
        }
    }
}

最后发现扫描线方法的性能最好，当然它的缺点也是，只能覆盖中心处于多边形的情况，对于需要保守覆盖的情况，需要独立作边的光栅化，再取并集。

最后

用于判定点在多边形内部十分方便，但是要获得覆盖多边形内的栅格，只通过栅格中心点来做，会漏掉许多，不太好处理。针对覆盖多边形问题，后面我会介绍另外一种方法，可以自由控制覆盖容忍度。