algorithm - 查找数组中被给定线段穿过的单元格

Question

我有一个二维单元格数组，大小为 10x10，许多点是成对的浮点值，例如:(1.6, 1.54), (4.53, 3.23)。对 (x,y) 满足 x<10 和 y<10

每个单元格取其坐标与单元格坐标具有相同整数部分的点。因此 arr[3][7] 将采用 x={3...3.99(9)} 和 y={7...7.99(9)} 的点，例如 (3.5, 7.1) 或 (3.2, 7.6 ).类似地，(1.6, 1.54) 在 arr[1][1] 中，(4.53, 3.23) 在 arr[4][3] 中，等等。

每个点在数组中都有一个指定的位置，很容易找到，因为我只需将 x 和 y 转换为 int 即可去掉小数点。

但我想找出数组中的哪些单元格与两点 A(x,y) 和 B(x,y) 之间的线段相交。

例如:A(1.5, 2.5) 和 B(4.3, 3.2) 穿过索引为 [1][2]、[2][2]、[3,3] 和 [3,4] 的数组中的单元格

有什么算法吗？

这是一个类似的问题: Cells in grid crossed by a line ( PHP )

Answer 1

Amanatides和Woo的方法A Fast Voxel Traversal Algorithm for Ray Tracing允许枚举所有相交的单元格。
Here is实际执行。

工作示例(交叉和接触的单元格是彩色的)