正方形网格 - （旋转）矩形相交 - 计算所有交点细胞

Question

我们有正方形格子的1.0

小区的宽度和高度的网格可以是任何大小的，让我们说25×25的这个例子。

现在有一个矩形（或一个厚度线），它有一个任意的开始和结束点，例如，起点（2.2,1.0）终点（20.4,5.5），厚度1.5。起点和终点位于矩形线的中心，因此线的两侧厚度均匀扩展。

如何计算矩形与该矩形相交的所有单元坐标？

Answer 1

为了列举细线情况下的所有相交单元，存在Amanatides和Woo的方法A Fast Voxel Traversal Algorithm for Ray Tracing。
Here is实际执行。

对于粗线条，您可以选择矩形的两条平行边线，并通过某个坐标（X或Y）同步穿过它们，每一步获取整个扫描线。

对于你的情况（任意坐标，可能不准确）：

bottom left corner is in (2,0) cell, top left in (2,1) cell 
(2,0)-(2,1) vertical scanline contains two cells 
walk with bottom ray to (3,0), wait until top ray reaches X=3 
walk with top ray to (2,2), add this cell to the last scanline 
walk with top ray to (3,2) 
(3,0)-(3,2) vertical scanline contains three cells 
and so on