我有一个二维单元格数组，大小为 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 )
最佳答案
Amanatides和Woo的方法A Fast Voxel Traversal Algorithm for Ray Tracing允许枚举所有相交的单元格。
Here is实际执行。
工作示例(交叉和接触的单元格是彩色的)
关于algorithm - 查找数组中被给定线段穿过的单元格，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35807686/