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

Question

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

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

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

编辑：我知道光线投射。有没有非常简单的实现，我可以看看？还有什么分析方法可以有效地解决这个问题。最后，是否有任何的概括，我可以做而不诉诸只有矩形（像一个旋转的矩形..，圆形等）

EDIT2：也开到好，高效的数据结构来存储地图和障碍

Answer 1

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

从（xo，yo）方向theta拍摄射线R，然后从定位包含（xo，yo）的单元格开始。接下来，计算R与小区之间的交集（即，其中R离开小区），并且取决于哪一边R离开该小区，使该相邻小区成为新当前小区。对于这个单元格，也要计算R离开它的位置等。

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

很明显，这要求你使网格的单元足够小，以便它们每个只包含少量的障碍物。如果你的障碍物的大小变化很大，你可以考虑使用Quadtree而不是一个普通的格子。尽管如此，这将使遍历单元更加复杂。

Answer 2

通过将障碍矩形定义为节点和边，您可能会获得一些吸引力。每个角是一个点（一个节点），每一边都是一个边。给定您的节点集合，您可以为边缘生成线性方程。

然后，用您已知的光线方程确定光线和每条边之间是否存在同步解。如果存在，那边就是解决点碰撞的候选对象。

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

最后，您可以确定解决方案点是否包含在边缘段（它是否位于两个节点内）。如果确实如此，则候选边是实际的碰撞边。如果找到多个碰撞边缘，只要取其解答点最接近光线原点的那个。