优雅/干净(特殊情况)直线网格遍历算法? [英] Elegant/Clean (special case) Straight-line Grid Traversal Algorithm?

问题描述

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

I'm dusting off an old project of mine. One of the things it had to do was -- given a Cartesian grid system, and two squares on the grid, find a list of all squares that a line joining the center of those two squares would pass through.

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

The special case here is that all start and end points are confined to the exact center of squares/cells.

这里有一些示例——带有成对的示例起点和终点.阴影方块是相应函数调用应返回的方块

Here are some examples -- with pairs of sample starting and ending points. The shaded squares are the ones that should be returned by the respective function call

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

起点和终点由它们所在的方格表示.在上图中，假设左下角是[1,1]，那么右下角的线就是标识为 [6,2] 到 [9,5].

The starting and end points are referred to by the squares they are in. In the above picture, assuming that the bottom left is [1,1], the line on the bottom right would be identified as [6,2] to [9,5].

即从左数第六列的(中心)正方形，从底部第二行到(中心)正方形 左起第九列，倒数第五行

That is, from the (center of the) square on the sixth column from the left, on the second row from the bottom to the (center of the) square on the ninth column from the left, on the fifth row from the bottom

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

Which really doesn't seem that complicated. However, I somehow seemed to have found some complex algorithm online and implemented it.

我确实记得它非常非常快.例如，针对每帧数百或数千次优化.

I do recall that it was very, very fast. Like, optimized-for-a-hundreds-or-thousands-of-times-per-frames fast.

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

Basically, it jumped from border to border of the squares, along the line (the points where the line crosses the grid lines). It knew where the next crossing point was by seeing which crossing point was closer -- a horizontal one or a vertical one -- and moved to that next one.

这在概念上还可以，但实际的实现结果却不是那么漂亮，而且我担心优化级别可能对于我实际需要的东西来说太高了(我是调用这个遍历算法可能一分钟五六次).

Which is sort of okay in concept, but the actual implementation turned out to be pretty not-so-pretty, and I'm afraid that the level of optimization might be way too high for what I practically need (I'm calling this traversal algorithm maybe five or six times a minute).

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

Is there a simple, easy-to-understand, transparent straight-line grid traversal algorithm?

在程序化方面:

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

其中给定的坐标标识了方块本身.

where the given coordinates identify the squares themselves.

一些例子:

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]

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

Note that lines that move directly through corners should not include squares on the "wing" of the line.

(Good ol' Bresenham's 可能在这里工作，但它与我想要的有点倒退.据我所知，为了使用它，我基本上必须将它应用到生产线上，然后扫描网格上的每一个方格以判断真假.对于大网格来说，这是不可行的——或者至少是不优雅的)

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

(I am re-looking into Bresenham, and Bresenham-based algorithms, due to a misunderstanding of mine)

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

For clarification, one possible application of this would be, if I was storing all of my objects in a game inside zones (a grid), and I have a ray, and want to see which objects the ray touches. Using this algorithm, I could test the ray to only the objects that are within the given zones, instead of every object on the map.

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

The actual use of this in my application is that every tile has an effect associated with it, and an object moves through a given line segment every turn. At every turn, it is necessary to check to see which squares the object has traversed through, and therefore, which effects to apply to the object.

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

Note that, at this point, the current implementation I have does work. This question is mostly for curiosity's purpose. There has to be a simpler way...somehow...for such a simple problem.

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

What am I looking for exactly? Something conceptually/neat and clean. Also, I've realized that due to what I am exactly specifying, all start and end points are always going to be in the center of squares/cells; so perhaps something that takes advantage of that would be neat as well.

推荐答案

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

What you want is a particular case of a supercover, which is all of the pixels intersected by a geometric object. The object may be a line or a triangle, and there are generalizations to higher dimensions.

无论如何，
_{(来源:free.fr)}

Anyways, here is one implementation for line segments. That page also compares the supercover with the result of Bresenham's algorithm - they are different.
_{(source: free.fr)}

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

I don't know whether you consider the algorithm there as elegant/clean, but it certainly seems simple enough to adapt the code and move on to other parts of your project.

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

By the way, your question implies that Bresenham's algorithm is not efficient for large grids. That's not true - it generates only the pixels on the line. You don't have to do a true/false test for every pixel on the grid.

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

Update 1: I noticed that in the picture there are two 'extra' blue squares that I believe the line does not pass through. One of them is adjacent to the 'h' in 'This algorithm'. I don't know if that reflects an error in the algorithm or the diagram (but see @kikito's comment below).

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

In general, the 'hard' cases are probably when the line passes exactly through a grid point. I speculate that if you are using floating point that float point error may mess you up in these cases. In other words, algorithms should probably stick to integer arithmetic.

更新 2: 另一种实现方式.

这篇关于优雅/干净(特殊情况)直线网格遍历算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！