所以我正在嘗試制作像模擬人生這樣的墻壁系統。雖然它是 3D，但可以簡化為 2D（想想鳥瞰圖）。一堵墻由兩點定義：起點和終點，墻本身有方向，可以簡化為單位向量。墻壁也是用長方形棱鏡制成的，這些棱鏡中的每一個都從一個點開始，在另一個點結束。所以，牢記這一點，有時墻壁必須延伸，否則墻壁的凸角會有一個小間隙
如果其中一個點在墻壁之間共享。任意數量的墻都可以放置在一個位置，所以記住所有這些，一個網格點的資料可以包含這樣的東西（使用Lua），每個表代表一個vector2，為了便于可視化使用一個表，這段代碼贏了'實際上不起作用：
local gridPoint = {
{x = 1, y = 0},
{x = 0.7071, y = 0.7071},
{x = 0, y = 1},
{x = 0.7071, y = -0.7071},
}
這是點的外觀，其中交叉點是網格點，墻壁是從交叉點延伸的向量，假設每個向量的長度為 1（請原諒我糟糕的繪圖技巧）。由于點積在大于 180 度時翻轉，因此最大角度始終為 <=180。
所以現在，要得到任意兩個點之間的角度，我們可以只math.deg(math.acos(v1:dot(v2)))得到這兩個點之間的角度，以度為單位，其中v1向量 1v2是向量 2，而 dot 是一個回傳 和 的點積的v1函式v2。
所以到目前為止，一切都很好。問題是我必須創建兩個回圈來遍歷可能的點積的每一個組合，我不確定這是找到最大角度的最佳方法，這是#gridPoint^2可能的組合，在較低的數字下很好，但是這個數字可能的組合數量隨著每一堵新墻呈指數增長。
有沒有更簡單的方法來做到這一點？
uj5u.com熱心網友回復：
這個問題相當于找到最遠的一對點，所有點都在單位圓上。
排序點 - 將帶有正y（角度0..Pi）的點分隔到第一個串列中，將帶有負數的點分隔y到第二個串列中，按 X 坐標對它們進行排序，然后加入第一個串列并反轉第二個串列，這更簡單。這個階段需要O(nlogn)時間
然后執行最遠點的搜索 - 固定第一個點索引 ( A[i])，遍歷串列直到平方距離A[i]-A[j 1]小于平方距離A[i]-A[j]。所以我們找到 的最遠點A[j]。A[i]現在遞增i并搜索它的最遠點 - 從j.
重復直到j超過n。
這個階段是線性的，因為我們移動i并且j僅向前移動。本質上這是一種旋轉卡尺的方法，因此您可以在其他地方獲得一些實作。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/483287.html
上一篇：根據羅盤方向計算位移
下一篇：如何在顫振中自定義舍入？