我想找到所有接触或包含给定有限线段部分的网格图块。网格是 2d 规则网格，因此我可以从瓦片位置（行、列）推断出任何瓦片的中心，反之亦然，我可以使用两个快速整数除法从给定浮点坐标计算瓦片位置。瓦片是二次方的，例如 0.25x0.25，其中 0.25 定义为瓦片宽度。现在我需要确定给定线段接触的所有图块（浮点数中给出的两个 2d 点定义一个线段）。我目前的方法是将线段分成等距点，距离为平铺宽度的一半（向香农致敬）。比我收集包含给定点的所有图块并删除重复的图块。
编辑：正如 Patricia 所指出的，我目前的方法不会产生完整的图块集，因为不会包含仅被线触及的一小部分的图块。这对我来说是可以接受的，因为在我的情况下，速度比准确性更重要，但仍应注意。
为了更清楚：我想要图像中的所有红色瓷砖，但如果我获得速度，我可以节省例如玫瑰色瓷砖。
您的问题基本上归结为在光栅图像上绘制线段。
如果您可以节省粉红色瓷砖，请使用 Bresenham 算法。否则，使用与绘制抗锯齿线类似的技术：
您从包含段一端的图块开始，并将其放入队列中。然后使用常规的 BFS 算法，仅将与该段相交的图块放入队列：
在一次迭代中，从队列的一端取一个图块，这是您找到的下一个相交图块。然后找到它的所有邻居，并将与线段相交的那些（在这种情况下测试与一条线相交就足够了）到队列的另一端。必须根据线的方向选择邻居。如果它向右下方，则使用向下、向右和向右下方的瓷砖作为邻居，如果向上，则仅使用向上的邻居，依此类推。
当您到达包含该段另一端的图块时，您就结束了。
给定线段的端点，您可以轻松计算线的方程，y = mx + b。给定段的长度，您可以计算参数形式：
x = x0 + ft
y = y0 + gt
给定这些方程中的任何一个，您都可以计算线上y任何给定坐标的坐标。x所以 ...
从线的第一个端点开始，您知道包含该点的单元格在集合中。您知道x每个单元格的坐标，因此您可以快速确定y线段穿过单元格边界的坐标。如果该y坐标高于单元格的顶部y坐标，则线段与起始单元格上方的单元格相交。（如果线的斜率是“向下”，则替换为“下方”。）
如果您对沿x轴的每个单元格边界重复该测试，您将获得该段穿过的所有单元格的列表。
测试线的渐变，与具有相同渐变符号的瓷砖对角线相对。如果它比平铺对角线更陡，则在下面交换 x 和 y 坐标。
如果渐变比瓦片对角线浅，线接触或穿过给定瓦片，并且瓦片不包含端点，则其与瓦片边缘的至少一个交点必须在瓦片的 x 边界上.
对于每条线的末端，收集包含或接触端点的瓷砖。
对于作为两个端点 x 坐标之间的平铺边缘的每个 x 坐标，计算线的 y 坐标。收集接触该点的瓷砖。
我认为这一切都可以通过最多几个部门进行梯度检查来完成。主要过程是所有的乘法、加法和比较。