在线上找到最近的矩形交点

Question

我有一条线从位置x_o和y_o以方向theta发出。这个世界并不是无限的，它有一个边界。

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

这是一个典型的2D游戏编程问题，但是否有任何简短的论文/教程可以阅读？我在搜索术语时遇到了麻烦。

编辑：我知道射线投射技术。是否有任何非常简单的实现我可以看一看？此外，是否有任何分析方法可以有效地解决这个问题？最后，是否有任何通用性的推广，而不仅仅是矩形（如旋转矩形、圆等）？

编辑2：同样欢迎好的、高效的数据结构来存储地图和障碍物。

- Pwnna

---

矩形是如何给定的？ - Bitwise

我还有基于瓷砖的东西...实际上，基于瓷砖的东西占了主要比例..还有一些矩形。 - Pwnna

Answer 1

通过将你的障碍矩形定义为节点和边，你可以获得一些进展。每个角落都是一个点（一个节点），每条边都是一条边。给定你的节点集合，你可以为边生成线性方程。

然后，使用你已知的射线方程，确定射线和每条边之间是否存在同时解。如果有，那么该边就是在解点处发生碰撞的候选边。

现在，这些边缘方程式是完整的线...你的矩形边只是该线段的一部分，而不是整个线。所以...

最后，你可以确定解点是否包含在边段上（它是否位于两个节点之间）。如果是，则候选边是实际的碰撞边缘。如果找到多个碰撞边缘，只需选择其解点距离射线原点最近的那个。

- OrangeWombat

Answer 2

你可以将世界划分为一个网格。在每个单元格中，存储完全或部分位于该单元格中的障碍物。这将成为你的搜索结构。

从（xo，yo）以方向θ发射光线R，然后开始定位包含（xo，yo）的单元格。接下来，计算R与单元格的交点（即R离开单元格的位置），并根据R离开单元格的哪一侧，将相邻的单元格作为新的当前单元格。对于这个单元格，也要计算R离开它的位置，以此类推。

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

显然，这需要使网格的单元格足够小，以便它们每个只包含少量障碍物。如果你的障碍物大小差异很大，可以考虑使用四叉树而不是常规网格。不过这会使遍历单元格更加复杂。

- Leon Bouquiet