0

我有一个大小为 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] 的单元格

有什么算法吗？

这是一个类似的问题： 网格中的单元格被一条线交叉（PHP）

4

3 回答 3

5

Amanatides 和 Woo的方法用于光线追踪的快速体素遍历算法允许枚举所有相交的单元格。
这是实际的实现。

工作示例（交叉和接触的单元格被着色） 在此处输入图像描述

于 2016-03-05T05:30:02.603 回答
2

让你的点是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因此您不必除以dxor 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) )
于 2016-03-05T00:34:23.270 回答
1

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

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)]

于 2020-04-03T08:17:46.540 回答