优雅/简洁（特殊情况下）直线网格遍历算法？

Question

我正在整理我的一个旧项目。其中需要做的一件事是，给定一个笛卡尔坐标系和两个正方形，找到连接这两个正方形中心的直线穿过的所有正方形的列表。

特殊情况是所有起始点和结束点都限制在正方形 / 单元格的正中心。

下面是一些示例 - 带有示例起始点和结束点的对。阴影正方形是应由各自的函数调用返回的正方形

已删除的ImageShack链接-示例

起始点和结束点由它们所在的正方形引用。在上图中，假设左下角是[1,1]，右下角的线将被识别为从第六列中心的正方形，从底部第二行到第九列中心的正方形，从底部第五行。

也就是说，从第六列最左边的（中央）正方形开始，在底部第二行到第九列最左边的（中央）正方形结束，在底部第五行。

看起来并不那么复杂。然而，我在某个在线复杂算法中实现了它。

我记得它非常快。像为每一帧优化了几百或几千次快。

基本上，它沿着线跳过正方形的边界（线穿越网格线的点）。 它通过观察哪个交叉点更接近 -水平交叉点还是垂直交叉点- 来确定下一个交叉点的位置，并移动到那个交叉点。

这个算法在概念上还行，但实际实现起来并不美观，我担心所需的优化级别对我实际需要的要求过高（我大约每分钟调用此遍历算法五到六次）。

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

以编程术语表述：

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]

请注意，直接穿过角落的线条不应包括在线条的“翼”部分的正方形中。

（好老的Bresenham可能适用于这里，但与我想要的有点背道而驰。就我所知，为了使用它，我基本上必须将其应用于该线并扫描网格上的每个正方形以获取真或假。对于大型网格来说是不可行的，或者至少是不优雅的）

（我正在重新研究Bresenham和基于Bresenham的算法，因为我的一个误解）

---

澄清一下，这种算法的一个可能应用是，如果我在游戏中将所有对象存储在区域内（网格），并且我有一个光线，并且想要查看光线触及哪些对象。使用此算法，我可以测试光线仅针对给定区域内的对象，而不是地图上的每个对象。

在我的应用程序中的实际用途是，每个图块都有一个与之关联的效果，并且对象在每个回合通过给定的线段移动。 每次回合，需要检查对象已经穿过的正方形，从而确定要向对象应用哪些效果。

请注意，此时我拥有的当前实现确实可行。这个问题主要是为了好奇心。肯定有更简单的方法......对于这样一个简单的问题。

---

我要找的到底是什么？ 某种概念上/整洁明了的东西。另外，我意识到由于我所指定的内容，所有起始点和结束点始终会在方块/单元格的中心;因此，也许利用这一点的某些东西也很棒。

- Justin L.

---

你想让线的端点在哪里 - 方块的角落（如果是，哪一个）还是中心？ - a_m0d

@a_m0d 感谢您指出的歧义; 我已经添加了一张图片以进行澄清。我的意思是中心点。 - Justin L.

感谢您的澄清和图片 - 让它变得更清晰了。 - a_m0d

Answer 1

您需要的是超级覆盖的特定情况，即由几何对象相交的所有像素。该对象可以是线或三角形，并且有向更高维度的推广。

无论如何，这里有一个线段的实现。该页面还将超级覆盖和Bresenham算法的结果进行了比较-它们是不同的。
_{(来源：free.fr)} 我不知道您是否认为那里的算法优雅/简洁，但它肯定足够简单，可以适应代码并继续处理项目的其他部分。

顺便说一句，您的问题暗示Bresenham算法对于大型网格不高效。 这不是正确的-它仅生成在线上的像素。 您不必对网格上的每个像素进行真/假测试。

更新1：我注意到在图片中有两个“额外”的蓝色正方形，我认为线条没有穿过这两个正方形之一与'This algorithm'中的'h'毗邻。 我不知道这是否反映了算法或图表中的错误（但请参见下面@kikito的评论）。

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

更新2：另一种实现。

- brainjam

---

+1 特别是关于 Bresenham 的观察。Bresenham 是完成此工作的正确工具（可能包括抗锯齿版本）。 - Drew Hall

谢谢您指出Bresenham算法的问题。我对它的理解有误（我以为它是一种测试像素是否属于给定线条的方法）。但现在我正在研究替代算法 :) - Justin L.

我已经仔细阅读了它；老实说，与我已经拥有的算法相比（请参见a_m0d的答案），我不认为论文中的算法有多少优雅之处，但我会研究超级覆盖算法。 - Justin L.

我注意到图片中有两个“额外”的蓝色正方形，我认为线段不会穿过它们。我认为作者在页面末尾解决了这个问题，他说：“在这里，我们假设如果直线通过一个角落，就会画出两个正方形。如果你想去掉这个，你可以简单地删除处理角落的 else 部分”。 - kikito

正如 @DrewHall 已经指出的那样：也可以使用抗锯齿版本的修改版：http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm - Karussell

Answer 2

这个主题的论文可以在这里找到。虽然它与光线追踪有关，但似乎与你所需的内容非常相关，我想你能够利用它。

还有另一篇论文在这里，涉及类似的内容。

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

- a_m0d

---

很不幸，第一篇论文似乎恰好是我已经在使用的算法。它可以很好地完成所有任务；我只是想找到一个更加优雅的算法。我在第二篇论文中没有找到任何相关的内容 =/ 但还是感谢你的建议。 - Justin L.

@Justin - 对不起 :( - 出现完全相同的论文的机会有多大？ - a_m0d

哈哈可能很小，但这只意味着你和我想法一致。 - Justin L.

Answer 3

There's a very easy algorithm for Your problem that runs in linear time:

1. Given two points A and B, determine the intersection points of the line (A, B) with every vertical line of Your grid, that lies within this interval.
2. Insert two special intersection points inside the cells containing A and B at the start/end of the list from point 1.
3. Interpret every two sequent intersection points as the min and max vectors of a axis aligned rectangle and mark all grid cells that lie inside this rectangle (this is very easy (intersection of two axis aligned rects), especially considering, that the rectangle has a width of 1 and therefore occupies only 1 column of Your grid)

Example:

+------+------+------+------+
|      |      |      |      |
|      |      | B    *      |
|      |      |/     |      |
+------+------*------+------+
|      |     /|      |      |
|      |    / |      |      |
|      |   /  |      |      |
+------+--/---+------+------+
|      | /    |      |      |
|      |/     |      |      |
|      *      |      |      |
+-----/+------+------+------+
|    / |      |      |      |
*   A  |      |      |      |
|      |      |      |      |
+------+------+------+------+ 

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

优化后的实现需要Θ（|B.x - A.x| + |B.y - A.y|）时间来处理一条线（A，B）。此外，如果实现者更容易，可以编写此算法以确定与水平网格线的交点。

更新：边界情况

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

然而，浮点误差迟早会发生并产生不正确的结果。从我的观点来看，即使使用双倍也不足够，应该切换到Decimal数字类型。优化后的实现将在该数据类型上执行Θ（|max.x - min.x|）次加法，每次需要Θ（log max.y）的时间。这意味着在最坏的情况下（线((0, 0)，(N，N))，其中N（> 10 ^ 6）非常大），算法会降级为O(N log N)的最坏情况运行时间。即使根据线（A，B）的斜率在垂直/水平网格线交叉检测之间切换也无法帮助解决这个最坏情况，但它确实有助于解决平均情况-如果分析器确定 Decimal 操作是瓶颈，我只会考虑实现这样的开关。

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

更正

brainjam指出，即使十进制数据类型可以表示任意精度的浮点数，但它仍不令人满意，因为例如¹/₃无法正确表示。因此，应使用分数数据类型，该数据类型应能够正确处理边界情况。谢谢brainjam！ :)

- Dave O.

---

+1。不错！我认为所有这些算法在处理浮点误差时都需要小心，以避免当交叉点恰好在网格点上（但误差会使其略微偏离网格点）时出现问题。 - brainjam

@Justin L. 哈哈，我刚刚注意到，我提出的算法与 a_m0d 在他的答案中链接的算法相同（我跳过了第一个“here”），而且这就是您已经使用的算法。您对自己的算法不满意吗？我可以想象出一个美妙的实现 - 不幸的是，并非所有事情都可以成为一行代码。也许一些抽象化可以帮助^^或开始一次代码高尔夫比赛xD。 - Dave O.

这实际上在概念上与a_m0d答案中的论文有所不同；它通过步进正方形来注意水平和垂直轴的交点。但我喜欢它必须相交所有y轴交点之间的所有正方形的概括。 - Justin L.

@Dave，如果你指的是Python中的Decimal类型，我认为它并没有什么用处。1/3无法被准确表示。然而，Python中的Fraction类型应该可以解决问题。 - brainjam

@brainjam，我指的是一个伪十进制数类型，它可以表示任意精度的浮点数，例如Java的BigDecimal。但是，你说得对，分数类型更适合这个任务，因为它应该能够处理边界情况。 - Dave O.

Answer 4

这里是一个简单的Python实现，使用了numpy。然而，这里只使用了2D向量和分量操作，这是相当常见的。结果看起来对我来说相当优雅（没有注释的情况下约20行代码）。

这不是通用的，因为它假设瓦片以整数坐标为中心，而分隔线出现在每个整数加上半个（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

- Kolaru