快速轴对齐单元遍历算法

Question

4

最快的方法是什么，可以找到线段所经过的单元格（如果有的话），并按遍历顺序排序？

sketch of cells

在上面的示例中，正确的结果如下：

- Nicolas Repiquet

2个回答

3

以下内容仅需使用简单的线段相交公式即可完成：

观察网格，它由6个线段组成（3条水平线段，3条垂直线段）。如果将每个线段无限延伸（变成没有起点或终点的线），则将2D空间分为16个区域。

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

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

1. 确定Au为u所在的区域，Av为v所在的区域。由于区域的轴对齐性质，每个区域最多只需要4次比较（2次x坐标，2次y坐标）。

同时，将当前位置p和当前区域A定义为起始点u和Au。

2. 首先，报告A作为S所穿过的区域。确定线段*(p，v]与A的4个边界的界定线之间的第一个交点q。如果找到这样的交点q，则包含q的边界将决定哪个相邻区域将成为我们的新A - 在这种情况下，我们的新p将是交点q。使用这个新的A和p，重复这个步骤。

如果没有找到交点，则p必须位于与v相同的区域中，行走结束。

*（p，v]表示：从p到v的线段，不包括p但包括v。

- Leon Bouquiet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MBo · Accepted Answer

你可以尝试使用由Amanatides和Woo编写的"用于光线追踪的快速体素遍历算法"。它旨在处理大型网格，但该原理对你的应用程序也可能有用。