让您的点为A和B，并分别具有坐标(xA,yA)和(xB,yB)。

两点之间线段的参数方程式由
A + t * (B-A) = (xA + t * (xB - xA), yA + t * (yB - yA))
下式给出：其中t，所有取值器在0和1之间。

您需要考虑沿线段的任一坐标的所有积分值。这将为您提供直线和单元格一侧的交点，因此您可以将与该侧相邻的两个单元格都标记为“横越”。

这是执行此操作的算法的概述，该算法沿线对交点进行排序：

• 从单元格A开始
• 当您不在B单元时：
  • 找到您的线段与x轴的下一个交点
  • 找到您的线段与y轴的下一个交点
  • 选择最接近的一个，标记相邻的单元格，然后移到该单元格上

有一些特殊情况，例如仅在一个角上被触摸的单元格。要对以前的算法中的那些进行特殊处理，您可以识别出两个潜在的未来交集是相同的。

这是一个快速的python演示，其中我按比例缩放（乘以了）t参数方程式的所有值，dx *dy因此您不必除以dx或dy，除非您需要确切的交点坐标。

from math import floor
def sign(n):
    return (n > 0) - (n < 0)

def raytrace(A, B):
    """ Return all cells of the unit grid crossed by the line segment between
        A and B.
    """

    (xA, yA) = A
    (xB, yB) = B
    (dx, dy) = (xB - xA, yB - yA)
    (sx, sy) = (sign(dx), sign(dy))

    grid_A = (floor(A[0]), floor(A[1]))
    grid_B = (floor(B[0]), floor(B[1]))
    (x, y) = grid_A
    traversed=[grid_A]

    tIx = dy * (x + sx - xA) if dx != 0 else float("+inf")
    tIy = dx * (y + sy - yA) if dy != 0 else float("+inf")

    while (x,y) != grid_B:
        # NB if tIx == tIy we increment both x and y
        (movx, movy) = (tIx <= tIy, tIy <= tIx)

        if movx:
            # intersection is at (x + sx, yA + tIx / dx^2)
            x += sx
            tIx = dy * (x + sx - xA)

        if movy:
            # intersection is at (xA + tIy / dy^2, y + sy)
            y += sy
            tIy = dx * (y + sy - yA)

        traversed.append( (x,y) )

    return traversed

如果您的像元宽度为，w且具有坐标的像元0, 0始于(x0, y0)（即[x0 , x0 + w] * [y0, y0 + w]），则在调用函数时对此进行标准化，即

raytrace( (1,1.5) , (5,2.5) )

用

raytrace( ((1 - x0) / w, (1.5 - y0) / w) , ((4 - x0) / w, (1.5 - y0) / w) )