我有一個應用程序，通過細分二十面體來創建近似球體。笛卡爾頂點座標轉換爲球面座標，以便所有頂點坐落在單位球體的表面上。細分的二十面體 - 如何找到任意點的最近頂點
接下來我需要做的是找到球體表面上任意點的最近頂點。我想出了兩個簡單的算法...
蠻力搜索 - 將成爲少數頂點的確定，但會過度更精細的細分。
排序/索引搜索 - 通過方位角和傾角將頂點排序爲某種順序的形式，然後創建一個粗略索引以通過限制其範圍來加速窮舉搜索。
我想知道是否有更微妙的，並希望更高性能的算法，我可以使用，而不是上述兩個之一。
更新1：我剛剛回憶說，對於應用程序的另一部分，頂點存儲有關其鄰居的信息。我的新算法是
一個可能的解決方案是建立頂點BSP樹：http://en.wikipedia.org/wiki/Binary_space_partitioning
如果二十面體具有在北極一個頂點，並在南極相反的頂點則有各5個頂點的2組它們在與赤道平行的平面上。有了幾何幾何圖形，我認爲這些飛機在N/S 57.3056°（小數，而不是dd.mmss）。這將你的二十面體分成4個緯度區域;
我正在作爲一名導航員工作，弧度以度數衡量並表示爲南北向;如果你喜歡更多的數學約定，你可以很容易地將這一切轉化爲你的球形座標版本。
我懷疑，雖然我沒有編碼它，檢查到5個頂點的距離和選擇最近的將比基於將球體表面劃分爲二十面體的投影表面的更復雜的方法更快，或將球體上的點投影回二十面體並在該座標系中解決問題。例如，您在更新1中建議的方法至少需要計算到6個頂點（第一個，任意選擇的一個及其5個鄰居）的距離。
無論您是僅想知道哪個頂點最接近，都無關緊要計算笛卡爾座標還是球面座標的距離。但是，笛卡兒座標系中的計算避免了對三角函數的大量調用。
另一方面，如果你還沒有在你的球體的兩極安排你的二十面體的頂點，那麼你應該有！
我想我可能沒有提出足夠清晰的問題 - 二十面體細分爲接近球體。一旦我對我的算法感到滿意，我計劃將節點數量增加到600000以上，並將處理數量減少到GPU。但是，我確實在兩極有頂點！ – 2012-08-14 10:36:50
在這種情況下，請查看http://www.geog.ucsb.edu/~good/papers/162.pdf和谷歌周圍類似的想法。 – 2012-08-14 10:55:23
通過回答掃描，我想我可能會脫離基地，但你所追求的是簡單的。我認爲。
由於您只處理坐在球體上的點，因此您可以從頂點到球體中心放置一條線，從任意點向中心放置另一條線並求解創建的角度它們之間。越小越好。我認爲最簡單和最便宜的方式就是點積。角度基本上沒有了。這裏有一個關於它的鏈接：http://www.kynd.info/library/mathandphysics/dotProduct_01/ 爲了測試它們，我建議選擇一個頂點，測試它，然後測試它的鄰居。它應該總是在最小的鄰居方向（角度應該總是隨着你接近頂點而減小）
無論如何，我希望這就是你所追求的。 哦，我在找到你的細分算法的時候遇到了這個頁面。很難找到;如果你可以發佈一個鏈接，我認爲它會比我自己更有幫助。
找到一個好的起始頂點的方法不太困難：在球體上覆蓋一個100x100x100網格，併爲每個網格單元預先計算距離單元中心最近的頂點。現在，給定一個任意點，查找該點所在的單元格，並使用預先計算的最近頂點作爲起點。 – 2012-09-04 21:59:53