在一條線上找到最近的矩形交點

Question

我有一條線從的方向從位置x_o和y_o伸出。世界不是無限的，有邊界。

我想找到第一個由直線和交點命中的矩形。

這是一個典型的2D遊戲編程問題，但是有沒有簡要的論文/教程可以閱讀？我遇到搜索字詞的問題。

編輯：我知道光線投射。有沒有非常簡單的實現，我可以看看？還有什麼分析方法可以有效地解決這個問題。最後，是否有任何的概括，我可以做而不訴諸只有矩形（像一個旋轉的矩形..，圓形等）

EDIT2：也開到好，高效的數據結構來存儲地圖和障礙

Answer 1

你如何將你的世界劃分爲一個網格。在每個細胞中，存儲完全或部分位於該細胞內的障礙物。這將是你的搜索結構。

從（xo，yo）方向theta拍攝射線R，然後從定位包含（xo，yo）的單元格開始。接下來，計算R與小區之間的交集（即，其中R離開小區），並且取決於哪一邊R離開該小區，使該相鄰小區成爲新當前小區。對於這個單元格，也要計算R離開它的位置等。

在你到達的每個單元格中，檢查R是否與存儲在這個單元格中的任何障礙物碰撞，如果是，你的射線與障礙物發生碰撞，你可以停止遍歷單元格。

很明顯，這要求你使網格的單元足夠小，以便它們每個只包含少量的障礙物。如果你的障礙物的大小變化很大，你可以考慮使用Quadtree而不是一個普通的格子。儘管如此，這將使遍歷單元更加複雜。

Answer 2

通過將障礙矩形定義爲節點和邊，您可能會獲得一些吸引力。每個角是一個點（一個節點），每一邊都是一個邊。給定您的節點集合，您可以爲邊緣生成線性方程。

然後，用您已知的光線方程確定光線和每條邊之間是否存在同步解。如果存在，那邊就是解決點碰撞的候選對象。

現在，這些邊緣方程是完整線......矩形的一側只是該線的一部分，而不是整條線。所以...

最後，您可以確定解決方案點是否包含在邊緣段（它是否位於兩個節點內）。如果確實如此，則候選邊是實際的碰撞邊。如果找到多個碰撞邊緣，只要取其解答點最接近光線原點的那個。