让您的点为
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 floordef 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) )
