c++ - 从一条线上查找网格正方形

Question

我正在尝试找到一种体面的算法，该算法允许我找到一条线在穿过网格时相交的所有正方形。Bresenham 的算法在我的场景中不起作用，因为线的端点不一定必须在正方形的中心开始或结束。即使它经过一个角落，也会计算一个正方形。

我试过谷歌搜索，但没有找到很多结果。

红色是 Bresenham 的算法，它可以做我想做的事情，但只有当线端点从正方形的中心开始时它才有效。绿色是我的理想方案。

Answer 1

为什么不遵循“数字”算法？
只需评估线上有限数量的点。
根据该点的坐标，很容易确定它们落在哪个方格上。
（只有当点所在的方格与最后一个点不同时，您才需要在列表中添加一个新方格。）

Answer 2

有同样的问题，在gamedev.stackexchange.com中找到了一个有用的答案，该问题链接到博客文章：http ://playtechs.blogspot.com/2007/03/raytracing-on-grid.html

如果您赶时间，下面是相关代码，但请查看 gamedev 问题以获得更多相关答案。该博客文章还更详细地解释了它的工作原理，并有两种额外的算法——一种更通用，更容易适应三个维度，另一种更简单，适用于线条始终在正方形中心开始和结束的情况。

#include <limits> // for infinity
void raytrace(double x0, double y0, double x1, double y1)
{
    double dx = fabs(x1 - x0);
    double dy = fabs(y1 - y0);

    int x = int(floor(x0));
    int y = int(floor(y0));

    int n = 1;
    int x_inc, y_inc;
    double error;

    if (dx == 0)
    {
        x_inc = 0;
        error = std::numeric_limits<double>::infinity();
    }
    else if (x1 > x0)
    {
        x_inc = 1;
        n += int(floor(x1)) - x;
        error = (floor(x0) + 1 - x0) * dy;
    }
    else
    {
        x_inc = -1;
        n += x - int(floor(x1));
        error = (x0 - floor(x0)) * dy;
    }

    if (dy == 0)
    {
        y_inc = 0;
        error -= std::numeric_limits<double>::infinity();
    }
    else if (y1 > y0)
    {
        y_inc = 1;
        n += int(floor(y1)) - y;
        error -= (floor(y0) + 1 - y0) * dx;
    }
    else
    {
        y_inc = -1;
        n += y - int(floor(y1));
        error -= (y0 - floor(y0)) * dx;
    }

    for (; n > 0; --n)
    {
        visit(x, y);

        if (error > 0)
        {
            y += y_inc;
            error -= dx;
        }
        else
        {
            x += x_inc;
            error += dy;
        }
    }
}