正方形網格 - （旋轉）矩形相交 - 計算所有交點細胞

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