确定线段触摸的常规2d网格中所有单元格的最快方法是什么
Mar*_*tin 1 algorithm grid performance graphics2d
我想找到触摸或包含给定有限线段部分的所有网格图块.网格是2d规则网格,因此我可以从图块位置(行,列)推导出任何图块的中心,反之亦然我可以从给定的浮点坐标计算图块位置,具有两个快速整数除法.瓦片是二次的,例如0.25x0.25,其中0.25被定义为瓦片宽度.现在我需要确定给定线段触摸的所有图块(浮点数中给出的两个2d点定义一个线段).我目前的方法是将片段分割成等距点,其距离是拼贴宽度的一半(向shannon的问候).我收集包含给定点的所有瓷砖并删除重复的瓷砖.
编辑:正如Patricia所指出的那样,我目前的方法并没有产生完整的图块集,因为不会包含只触及线条非常小部分的图块.这对我来说是可以接受的,因为在我看来,速度比准确性更重要,但应该注意到.
为了使它更清晰:我想要图像中的所有红色瓷砖,但如果我获得速度,我可以保留例如玫瑰色的瓷砖.
您的问题基本上归结为在光栅图像上绘制线段.
如果您可以使用粉红色瓷砖,请使用Bresenham的算法.否则,使用与绘制抗锯齿线相似的技术:
您从包含段的一端并将其放入队列的磁贴开始.然后使用常规BFS算法,仅将与段相交的切片放入队列:
在一次迭代中,从队列的一端取一个图块,这是您下一个找到的相交图块.然后找到它的所有邻居,并将与段相交的那些(在这种情况下足以测试与一条线的交点)到队列的另一端.必须根据线的方向选择邻居.如果它向右下方,则使用向下,向右和向右的图块作为邻居,如果它上升,则仅使用向上的邻居,依此类推.
当您到达包含该段另一端的图块时,您将结束.