23

我正在清理我的一个旧项目。它必须做的一件事是——给定一个笛卡尔网格系统，以及网格上的两个正方形，找到连接这两个正方形中心的一条线将通过的所有正方形的列表。

这里的特殊情况是所有起点和终点都被限制在正方形/单元格的确切中心。

这里有一些例子——有成对的样本起点和终点。阴影方块是相应函数调用应返回的方块

删除了无效的 ImageShack 链接 - 示例

起点和终点由它们所在的正方形表示。在上图中，假设左下角是[1,1]，则右下角的线将被标识[6,2]为[9,5]。

即从左起第六列、下第二行的方格（中心）到左起第九列、下起第五行的方格（中心）

这看起来真的没有那么复杂。不过，不知怎么的，我好像在网上找到了一些复杂的算法并实现了。

我记得那是非常非常快的。就像，每帧快速优化了数百或数千次。

基本上，它沿着线（线与网格线相交的点）从正方形的边界跳到边界。它通过查看哪个交叉点更接近（水平的或垂直的）来知道下一个交叉点在哪里，然后移动到下一个交叉点。

这在概念上是可以的，但实际的实现结果并不那么漂亮，而且我担心优化水平可能对我实际需要的东西来说太高了（我称之为遍历算法可能每分钟五六次）。

有没有简单、易懂、透明的直线网格遍历算法？

在程序化方面：

def traverse(start_point,end_point)
  # returns a list of all squares that this line would pass through
end

其中给定的坐标标识了正方形本身。

一些例子：

traverse([0,0],[0,4])
# => [0,0], [0,1], [0,2], [0,3], [0,4]
traverse([0,0],[3,2])
# => [0,0], [0,1], [1,1], [2,1], [2,2], [3,2]
traverse([0,0],[3,3])
# => [0,0], [1,1], [2,2], [3,3]

请注意，直接通过拐角的线不应包括线“翼”上的正方形。

（Good ol' Bresenham's 可能在这里工作，但它与我想要的有点倒退。据我所知，为了使用它，我基本上必须将它应用到线上，然后扫描每个正方形真或假的网格。对于大型网格不可行——或者至少不优雅——

（由于我的误解，我正在重新研究 Bresenham 和基于 Bresenham 的算法）

为了澄清起见，一个可能的应用是，如果我将所有对象存储在区域（网格）内的游戏中，并且我有一条射线，并且想查看射线接触到哪些对象。使用这个算法，我可以只测试给定区域内的对象，而不是地图上的每个对象。

在我的应用程序中，它的实际用途是每个图块都有与之关联的效果，并且对象每转都会通过给定的线段。在每一个转弯处，都需要检查对象已经穿过了哪些方格，因此需要对对象应用哪些效果。

请注意，在这一点上，我当前的实现确实有效。这个问题主要是出于好奇的目的。对于这样一个简单的问题，必须有一种更简单的方法......不知何故......

我到底在寻找什么？概念上/整洁干净的东西。另外，我意识到由于我确切指定的内容，所有起点和终点都将始终位于正方形/单元格的中心；所以也许利用这一点的东西也会很整洁。

4

4 回答 4

20

你想要的是一个超级覆盖的特殊情况，它是一个几何对象相交的所有像素。对象可能是一条线或一个三角形，并且可以推广到更高的维度。

无论如何，这是线段的一种实现。该页面还将超级封面与 Bresenham 算法的结果进行了比较——它们是不同的。 （来源：free.fr）替代文字

我不知道你是否认为那里的算法优雅/干净，但它确实看起来很简单，可以调整代码并继续到项目的其他部分。

顺便说一句，您的问题意味着 Bresenham 的算法对于大型网格效率不高。这不是真的 - 它只生成线上的像素。您不必对网格上的每个像素进行真/假测试。

更新 1：我注意到图片中有两个“额外”的蓝色方块，我相信这条线没有通过。其中一个与“此算法”中的“h”相邻。我不知道这是否反映了算法或图表中的错误（但请参阅下面的@kikito 评论）。

一般来说，“困难”的情况可能是直线恰好通过一个网格点。我推测，如果您使用浮点数，那么在这些情况下，浮点错误可能会搞砸您。换句话说，算法可能应该坚持整数运算。

更新 2： 另一个实现。

于 2010-07-13T03:52:58.450 回答
6

可以在此处找到有关此主题的论文。这是关于光线追踪的，但这似乎与你所追求的非常相关，我认为你将能够使用它。

这里还有另一篇论文，处理类似的事情。

这两篇论文都链接在Jakko Bikker关于光线追踪的优秀教程的第4 部分（其中还包括他的源代码，因此您可以浏览/检查他的实现）。

于 2010-07-13T03:12:47.807 回答
4

您的问题有一个非常简单的算法，可以在线性时间内运行：

  1. 给定两个点 A 和 B，确定线 (A, B) 与位于此区间内的网格的每条垂直线的交点。
  2. 在包含 A 和 B 的单元格内从点 1 开始/结束插入两个特殊的交点。
  3. 将每两个连续的交点解释为轴对齐矩形的最小和最大向量，并标记位于该矩形内的所有网格单元（这很容易（两个轴对齐的矩形的交点），特别是考虑到矩形具有宽度1，因此仅占您网格的 1 列）
例子：
+------+------+------+------+
|      |      |      |      |
|      |      | B    *      |
|      |      |/     |      |
+------+------*------+------+
|      |     /|      |      |
|      |    / |      |      |
|      |   /  |      |      |
+------+--/---+------+------+
|      | /    |      |      |
|      |/     |      |      |
|      *      |      |      |
+-----/+------+------+------+
|    / |      |      |      |
*   A  |      |      |      |
|      |      |      |      |
+------+------+------+------+

“A”和“B”是终止由“/”表示的线的点。“*”标记线与网格的交点。需要两个特殊的交点来标记包含 A 和 B 的单元格并处理特殊情况，例如 Ax == Bx

优化的实现需要 Θ(|Bx - Ax| + |By - Ay|) 时间用于线 (A, B)。此外，如果对实施者来说更容易的话，可以编写此算法来确定与水平网格线的交点。

更新：边境案件

正如brainjam 在他的回答中正确指出的那样，当一条线完全穿过一个网格点时，困难的情况就是那些。让我们假设发生这种情况并且浮点算术运算正确返回具有整数坐标的交点。在这种情况下，所提出的算法仅标记正确的单元格（由 OP 提供的图像指定）。

但是，浮点错误迟早会发生并产生不正确的结果。在我看来，即使使用 double 也是不够的，应该切换到Decimal数字类型。优化的实现将对该数据类型执行 Θ(|max.x - min.x|) 加法，每个加法都需要 Θ(log max.y) 时间。这意味着在具有巨大 N (> 10 6 )的最坏情况下（行 ((0, 0), (N, N))，算法会降级为 O(N log N) 最坏情况运行时。即使在垂直/根据线的斜率（A，B）检测水平网格线交叉点在这种最坏的情况下没有帮助，但在一般情况下确实有帮助 - 如果分析器产生Decimal操作，我只会考虑实现这样的开关成为瓶颈。

最后，我可以想象一些聪明的人可能会想出一个 O(N) 的解决方案来正确处理这种边界情况。欢迎您提出所有建议！

更正

Brainjam 指出，即使十进制数据类型可以表示任意精度的浮点数，它也不能令人满意，因为例如1 / 3不能正确表示。因此应该使用分数数据类型，它应该能够正确处理边界情况。谢谢你的脑筋急转弯！:)

于 2010-07-13T10:43:48.013 回答
0

这是一个简单的 Python 实现，使用 numpy。然而，这里使用的只是二维向量和逐个分量的操作，这是相当常见的。结果对我来说看起来很优雅（~20 loc，没有评论）。

这并不普遍，因为它假设瓦片以整数坐标为中心，而分隔线出现在每个整数加上二分之一（0.5、1.5、2.5 等）处。这允许使用舍入从世界坐标获取瓦片整数坐标（在您的特殊情况下实际上不需要），并给出幻数0.5来确定我们何时到达最后一个瓦片。

最后，请注意，此算法不处理在交叉点处与网格完全交叉的点。

import numpy as np

def raytrace(v0, v1):
    # The equation of the ray is v = v0 + t*d
    d = v1 - v0
    inc = np.sign(d)  # Gives the quadrant in which the ray progress

    # Rounding coordinates give us the current tile
    tile = np.array(np.round(v0), dtype=int)
    tiles = [tile]
    v = v0
    endtile = np.array(np.round(v1), dtype=int)

    # Continue as long as we are not in the last tile
    while np.max(np.abs(endtile - v)) > 0.5:
        # L = (Lx, Ly) where Lx is the x coordinate of the next vertical
        # line and Ly the y coordinate of the next horizontal line
        L = tile + 0.5*inc

        # Solve the equation v + d*t == L for t, simultaneously for the next
        # horizontal line and vertical line
        t = (L - v)/d

        if t[0] < t[1]:  # The vertical line is intersected first
            tile[0] += inc[0]
            v += t[0]*d
        else:  # The horizontal line is intersected first
            tile[1] += inc[1]
            v += t[1]*d

        tiles.append(tile)

    return tiles
于 2019-07-09T03:04:13.037 回答