algorithm - 快速轴对齐单元遍历算法

Question

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

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

在上面的例子中，正确的结果是：

• 第 1 段：[D]
• 第 2 段：[A，B]
• 第 3 段：[C、D、B]
• 第 4 段：[]
• 第 5 段：[C]

Answer 1

你可以试试Amanatides 和 Woo的“A Fast Voxel Traversal Algorithm for Ray Tracing”。

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

Answer 2

仅使用简单的线相交公式即可完成以下操作：

观察您的网格由 6 个线段组成（3 个水平，3 个垂直）。如果您要将这些线段中的每一个都无限延伸（使它们成为线，没有起点或终点），那么您已经将 2D 空间划分为 16 个区域。

定义一个 4x4 的区域数组。对于每个这样的区域，存储哪条线（如果有）在北侧、东侧等划分它。这将是我们的遍历数据结构。

现在，要找到给定查询段 S 遍历的单元格，从 u 开始到 v 结束，我们将使用此遍历数据结构从 u 到 v 进行直线遍历，以跟踪我们当前所在的区域我们正在离开该区域的哪些位置。

• 确定Au为u所在的区域，Av为v所在的区域。由于这些区域的轴对齐特性，每个区域的比较不应超过 4 次（x 坐标上 2 次，y 轴上 2 次）。
  另外，定义当前位置为p，当前区域为A；最初，它们分别是 u 和 Au。

• 首先，将 A 报告为 S 穿过的区域。确定线段* (p, v] 与 A 的 4 条边中每一边的分界线之间的第一个交点。如果找到这样的交点 q，则包含 q 的边决定了哪个相邻区域将成为我们的新 A - 在这种情况下，我们的新 p 将是交点 q。使用这个新的 A 和 p，重复此步骤。
  如果没有找到交点，p 必须位于与 v 相同的区域，步行已完成。

* (p, v] 含义：p和v之间的段，不包括p但包括v。