什么是确定常规2D网格中被线段触及的所有单元格的最快方法？

Question

我想找到所有与给定线段相接触或包含其部分的网格瓦片。该网格是一个二维规则网格，因此我可以从瓦片位置（行、列）推断出任何瓦片的中心，反之亦然，我可以通过两个快速整数除法从给定浮点坐标计算瓦片位置。这些瓦片是四方形的，例如0.25x0.25，其中0.25定义为瓦片宽度。 现在我需要确定所有被给定线段碰触的瓦片 （由浮点数给出的两个2D点定义了一条线段）。 我的当前方法是将线段分成等距点，距离为半个瓦片宽度（向香农致敬）。然后收集包含给定点的所有瓦片并删除重复瓦片。 由于此操作是我的程序中最重要的性能关键部分，我想知道是否有更快的方法来计算相应的瓷砖。

编辑：正如Patricia所指出的那样，我的当前方法不能得出完整的瓷砖集，因为仅被线条轻微碰触的瓷砖不会被包括在内。对于我来说，这是可以接受的，因为在我的情况下速度比准确性更重要，但仍应予以注意。

让它更清晰一些：我想要图像中的所有红色瓦片，但如果我为此获得速度，我可以跳过玫瑰色瓷砖等其他颜色的瓷砖。

- Martin

---

我不确定你目前的方法在所有情况下都有效，或者可能是我没有理解问题。一条线段难道不能只剪切瓦片的一个角落，并且仅有极小部分的线段在瓦片内吗？ - Patricia Shanahan

嗨，Patricia：你说得很对，这是当前解决方案无法解决的问题。对于我的算法，我做出了这个妥协，因为速度比绝对准确性更重要。我应该在文本中加入你的评论。 - Martin

这看起来非常像CS 101中的Bresenham线绘制算法。 - twalberg

谢谢所有的答案：我应该真正地复习一下我的算法基础 :-P - Martin

Answer 1

你的问题基本上是在光栅图像上绘制线段。

如果你可以使用粉色瓷砖，可以使用Bresenham算法。否则，使用类似于绘制抗锯齿线条的技术：

从包含线段一端的瓷砖开始，并将其放入队列中。然后按照常规BFS算法进行，只将与线段相交的瓷砖放入队列中：

在一个迭代中，从队列的一端取出一个瓷砖，这是下一个发现的相交瓷砖。然后找到所有相邻的瓷砖，并将与线段相交的瓷砖（在这种情况下仅测试与直线的相交）放入队列的另一端。必须根据线的方向选择邻居。如果向下右移，则使用向下、向右和向下右侧的瓷砖作为邻居；如果向上移动，则仅使用上邻居，依此类推。

当到达包含线段另一端的瓷砖时结束。

- Michał Trybus

Answer 2

测试线的梯度，与具有相同梯度符号的瓷砖对角线进行比较。如果比瓷砖对角线更陡峭，请在接下来的步骤中交换x和y坐标。

如果梯度比瓷砖对角线更浅，则该线会触及或穿过给定的瓷砖，并且该瓷砖不包含端点，至少其与瓷砖边缘的交点之一必须位于瓷砖的x边界上。

对于每个线端，请收集包含或接触端点的瓷砖。

对于两个端点x坐标之间的瓷砖边缘上的每个x坐标，请计算线的y坐标。收集接触该点的瓷砖。

我认为这可以通过最多几次除法来完成梯度检查。主要过程都是乘法、加法和比较。

- Patricia Shanahan

Answer 3

根据线段的端点，您可以轻松计算出直线的方程：y = mx + b。而且，根据线段的长度，您可以计算出参数形式：

x = x0 + ft
y = y0 + gt

给定这两个方程中的任意一个，您可以计算出该直线上任何给定 x 坐标的 y 坐标。因此...

从直线的第一个端点开始，您知道包含该点的单元格在集合中。您知道每个单元格的 x 坐标，因此您可以快速确定线段穿过单元格边界的 y 坐标。如果该 y 坐标在单元格的顶部 y 坐标之上，则线段与起始单元格上方相交。（如果线段的斜率为“向下”，则替换为“下方”）

如果您在 x 轴沿着每个单元格边界重复进行该测试，则会得到线段穿过的所有单元格的列表。

- Jim Mischel