快轴对齐细胞遍历算法

Question

• 给定一个轴对齐的正方形,分为四个大小相等的单元格A,B,C和D.
• 给定从s1点到s2的线段.

找到段遍历的单元格(如果有)的最快方法是什么,按遍历顺序排序？

在上面的示例中,正确的结果是:

• 第1部分:[D]
• 第2部分:[A,B]
• 第3部分:[C,D,B]
• 第4部分:[]
• 第5部分:[C]

Answer 1

您可以尝试Amanatides和Woo的"快速体素遍历算法进行光线追踪".

它旨在处理大网格,但该原则对您的应用程序也很有用.