尋找哪個區域包含一個點的好的數據結構是什麼？

我正在尋找一個數據結構，它支持查找哪個「n」個區域包含一個點「p」。我正在研究Quadtree和R-trees，但我不認爲它們完全符合我的要求。尋找哪個區域包含一個點的好的數據結構是什麼？

實質上，我希望能夠在這棵樹上添加一些3維的矩形區域，然後能夠對這棵樹測試一個3維點並返回哪個區域最緊密地約束點。沒有地區會有重疊的邊界。

我目前使用的樸素算法是對每個矩形區域的每個維度簡單地測試點「p」。

for(region in regionList): 
    if(p.x > region.x1 && p.x < region.x2 && p.y > region.y1 && py < region.y2 && p.z > region.z1 && p.z < region.z2) 
     return region 
end

這運行在O（n）時間，其中n是地區的數量。我希望搜索將O（log n）作爲Quadtree找到2d點的一個點。

來源

2013-02-05 Rovert Renchirk

這看起來很有前途。 http://www.cs.umd.edu/~hjs/multidimension-book-flyer.pdf – RocketRoy

由於區域不能重疊，所以最多隻有一個區域可以包含該點。這使得「......返回哪個區域最嚴格地限制了點」的問題。邏輯上的不可能性。 1，只有1可以限制點。 – RocketRoy

這個應用程序可能會非常好地使用新的SIMD擴展，爲3D圖形應用程序提供16個128位寄存器。 – RocketRoy

我會建議一個QuadTree，它存儲像MX-CIF樹那樣的區域。它基本上是基於2維（x，y）的QuadTree。一旦找到包含點（x，y）的適當節點，就可以檢查它是否包含所有三個（x，y，z）維中的點。我做過something similar in Java。

你也可以看看八叉樹，它是一個三維QuadTree。

來源

2013-02-05 17:12:06 Justin

只是爲了確保我正確理解你。你是否建議我使用Quadtree檢查點是否位於xy區域，然後獨立檢查點是否也在該區域的z邊界內？如果我有兩個區域，一個在另一個之上，會發生什麼？ Quadtree會返回什麼？ –

一個點不能存在於多個區域，對嗎？這不是你問題陳述的一部分嗎？ – Justin

沒錯，但是因爲MX-CIF樹測試一個點是否在2d區域內。如果我有3d區域，那麼一個點可能在兩個3d區域的投影內，而不在這兩個區域中。除非你的意思是我將MX-CIF樹調整爲3維，在這種情況下應該可以工作。 –

結賬Segment Trees和KD Trees。

來源

2013-02-05 05:56:31

尋找哪個區域包含一個點的好的數據結構是什麼？

回答

相關問題