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

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

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

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

您需要考虑沿线段的任一坐标的所有整数值。这将为您提供线与单元格边的交点，因此您可以将与该边相邻的两个单元格标记为 "traversed".

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

从单元格 A 开始
当您不在单元格 B 时：
- 找到线段与 x 轴的下一个交点
- 找到线段与 y 轴的下一个交点
- 取最近的一个，标记相邻的单元格，然后移动到它

有一些特殊情况，比如只在一个角上被触摸的单元格。在前面的算法中特别对待那些，你可以认识到这两个潜在的未来交叉点是相同的。

这里是 a quick python demo，我将参数方程的所有 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) )

Answer 2

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

作品示例（交叉和接触的单元格是彩色的）

Answer 3

试试 Bresenham 的画线算法，它有 python package。代码如下所示：

from bresenham import bresenham


cells = list(bresenham(96, 280, 95, 275))
print(cells)

我收到了 [(96, 280), (96, 279), (96, 278), (95, 277), (95, 276), (95, 275)]

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

Find cells in array that are crossed by a given line segment

algorithm

math

intersection

point

line-segment