我想找到所有接触或包含给定有限线段部分的网格图 block 。网格是一个 2d 规则网格，因此我可以从一个瓦片位置(行，列)推断出任何瓦片的中心，反之亦然我可以从给定的浮点坐标计算一个瓦片位置与两个快速整数除法。瓷砖是二次方的，例如0.25x0.25，其中 0.25 定义为平铺宽度。 现在我需要确定给定线段接触的所有图 block ( float 中给出的两个 2d 点定义了一条线段)。 我目前的方法是将线段分割成等距点，距离为平铺宽度的一半(向香农问好)。然后我收集所有包含给定点的图 block 并删除重复的图 block 。 由于此操作是我程序中性能最关键的部分，我想知道是否有更快的方法来计算各个图 block 。
编辑:正如 Patricia 指出的那样，我当前的方法不会生成完整的图 block 集，因为不会包括仅被线触及到非常小部分的图 block 。这对我来说是可以接受的，因为在我的情况下速度比准确性更重要，但仍然应该注意。
为了更清楚:我想要图像中的所有红色瓷砖，但我可以节省，例如如果我为此获得速度，那就是玫瑰色的。
最佳答案
您的问题基本上归结为在光栅图像上绘制线段。
如果您可以保留粉色方 block ，请使用 Bresenham 算法。否则，使用与绘制抗锯齿线类似的技术:
您从包含片段一端的图 block 开始并将其放入队列。然后使用常规 BFS 算法，仅将与该段相交的图 block 放入队列:
在一次迭代中，从队列的一端取出一个图 block ，这是您找到的下一个相交图 block 。然后找到它的所有邻居，并将那些与线段相交的邻居(在这种情况下足以测试与一条线的相交)放到队列的另一端。必须根据线路的方向选择邻居。如果它向右下方移动，则使用向下、向右和向右下方的磁贴作为邻居，如果向上移动，则仅使用向上的邻居，依此类推。
当您到达包含该段另一端的图 block 时，您就结束了。
关于performance - 确定由线段接触的规则二维网格中的所有单元格的最快方法是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13352236/