線性時間的多面體測試點

假設我們有一個具有N個頂點的3D多面體。你如何測試一個點是否在時間O（n）內。應該有一個線性算法，但我的搜索不成功。線性時間的多面體測試點

2011-10-09 anonymous

如果有限定凸多面體（3D版多邊形的）N個點，這意味着得到的形狀是拓撲等價球體。

如果你查找幾個拓撲定理，這並不難證明。基本上，由於沒有內部孔，所以缺少孔將您的多面體放置在與球體相同的幾何對象的「屬」中。然後，您只需將每個頂點（一組N個拉伸）轉換爲距給定內點的某個固定距離R.由於所有這些點現在位於球體的表面上，並且只使用拓撲合法的「拉伸」操作（通過移動它們的頂點來拉伸邊界面），所以凸多面體在拓撲上等同於球體。我省略了正式的條款，因爲它們不會增加太多混亂。

只要你空穴 - 並不等同於球體再添加任何排除內部區域 - 。在這種情況下，你可以使用相同的擴展版本。你測試你是否在多面體的「邊界面」內，然後測試你是否在它的任何一個洞內（它們也是多面體）。你需要一些額外的標誌或條款孔位於外多面體的一部分，等

來源

2013-09-23 02:21:34

-1

可能您正在使用給定頂點的凸包。

計算凸包（O（N log n）的），並發現是在多面體點（O（N））具有複雜度O（N log n）的。

如果點不在凸多面體比有分隔點和多面體的平面。在2D中，很容易找到從點到多面體頂點的矢量之間的分離平面測試角度。對於3D我不知道如何做到這一點（在O（n））。

來源

2011-10-10 18:00:31 Ante

不幸的是爲凸多面體不需要內處理孔。無論如何，似乎算法在O（n）中運行的額外要求是多面體是簡單的（在拓撲上相當於一個球體）。這應該意味着它可以變成一個球形的物體，它是凸的，就是它。我只需要考慮這樣一個轉換... – anonymous

那麼，你有面孔定義的多面體？ – Ante

我想我現在有解決方案。由於多面體在拓撲上等價於球體，因此它的面（和邊）數爲O（n）（因爲它相當於一個平面圖，... - 需要一個簡短的證明）。只需迭代所有面並進行類似於2D中的點中多邊形測試的光線投射，實際上將在O（n）中運行，因爲只有O（n）個面。 – anonymous

-1

解決方案是：由於多面體在拓撲上等價於一個球體，因此它的面（和邊）數爲O（n）（因爲它相當於一個平面圖，... - 需要一個簡短的證明）。只需迭代所有面並進行類似於2D中的點中多邊形測試的光線投射，實際上將在O（n）中運行，因爲只有O（n）個面。

來源

2011-11-24 18:17:17 anonymous

等等，什麼？一個低調的，但接受的答案？ –

線性時間的多面體測試點

回答

相關問題