algorithm - 找到直线上最近的矩形交点

Question

我有一条线从 x_o 和 y_o 位置向 theta 方向突出。世界不是无限的，而是有边界的。

我想找到被直线和交点击中的第一个矩形。

这是一个典型的 2D 游戏编程问题，但是有没有我可以阅读的简短论文/教程？我在搜索字词时遇到问题。

编辑:我知道光线转换。我可以看一下任何非常简单的实现吗？还有什么分析方法可以有效地解决这个问题。最后，如果不求助于矩形(如旋转矩形..、圆形等)，我是否可以做出任何概括

Edit2:也对存储 map 和障碍物的良好、高效的数据结构开放

Answer 1

如何将您的世界划分为网格。在每个单元格中，存储完全或部分位于该单元格中的障碍物。这将是您的搜索结构。

从 (xo, yo) 沿 theta 方向射出一条射线 R，然后从定位包含 (xo, yo) 的单元开始。接下来，计算 R 和单元格之间的交点(即 R 离开单元格的位置)，并根据 R 离开单元格的哪一侧，使相邻单元格成为新的当前单元格。同样对于这个单元格，计算 R 离开它的位置，等等。

在您到达的每个单元格中，检查 R 是否与存储在该单元格中的任何障碍物发生碰撞，如果是，则您的射线已与障碍物碰撞并且您可以停止遍历单元格。

显然，这要求您将网格的单元格设置得足够小，以便每个单元格仅包含少量障碍物。如果障碍物的大小变化很大，您可以考虑使用 Quadtree而不是规则的网格。不过，这将使遍历单元更加复杂。