用於存儲3d點的高效數據結構

我正在尋找用於存儲3d點（x，y，z）的高效數據結構。存儲在數據結構中的點上的效果應該產生更有效的內存結構並且更快地搜索特定的座標集合。三維點映射到一個特定的ID，所以它應該能夠跟蹤每一組座標，我正在尋找任何可用的實現。用於存儲3d點的高效數據結構

x，y，z給出了每個節點的笛卡爾座標。

ID arrow-

1 14.566132 34.873772 7.857000

2 16.022520 33.760513 7.047000

3 17.542000 32.604973 6.885001

4 19.163984 32.022469 5.913000

5 20.448090 30.822802 4.860000

6 21.897903 28.881084 3.402000

7 18.461960 30.289471 8.586000

8 19.420759 28.730757 9.558000

座標的數量將是巨大的1個000 000

也許各地提前感謝！

來源

2016-03-05 Yoko

你到目前爲止考慮過哪些選項？ –

已考慮八叉樹https://en.wikipedia.org/wiki/Octree和https：//en.wikipedia。org/wiki/R-tree，但docent找到任何用於存儲3d座標的好實現 – Yoko

您應該指定對您重要的內容。代碼可讀性（簡單的結構數組），自動矢量化（數組結構），或者可能有很好的插入/搜索時間（八叉樹？）。例如在N體計算中，八叉樹是O（nlog n）的最佳方法。 – Hopobcn

你可以使用一個struct：

struct coordinate 
{ 
    double x; 
    double y; 
    double z; 
} points[1000000];

來源

2016-03-05 20:31:56

一個小小的改進：鑑於他顯然只有7位有效數字，他可能想使用'float'而不是'double'。這對3D應用來說並不少見... –

它取決於您想存儲多少準確的價值！ –

這只是一個結構，我正在尋找一個用於存儲三維座標的數據結構。在這個結構中，我將不得不強行搜索特定的座標集，這不是我要找的。 – Yoko

了更大的內存高效的結構

更多的內存比什麼效率？一個列表？你需要壓縮。

一組特定座標

如果你想從一組座標找到K個最接近點的更快的搜索，一個ball tree是一個不錯的選擇。

如果要搜索卷，四叉樹（或octree）的效果會更好。

來源

2016-03-06 00:25:56 o9000

是比存儲列表中的所有內容更高的內存效率結構座標 {x} double y; double z; }; （））{ std :: vector list; 座標a =座標（2.123123,2.1231,3.112）; list .push_pack（a）; } – Yoko

我聽說你正在查找的座標將與結構中的座標完全匹配。根據您的空間分佈情況，您可以創建一個哈希函數，它可以採用座標並嘗試生成相當獨特的東西，然後使用標準哈希映射。大多數現代語言都提供了某種哈希映射實現，所以你需要做的就是爲你的座標提供適當的哈希值。

如果您需要在測試座標附近查找座標，然後是球樹或八叉樹或其他東西，但聽起來不像您需要的那樣。

來源

2016-03-06 00:40:31

使用散列法，他們需要一點一點地平等。如果查找值是浮點運算的結果，那麼由於精度的損失可能不會成立。如果是這種情況，散列函數將不得不考慮最大錯誤並在實際散列之前丟棄最低有效位。但我認爲OP對他需要什麼感到困惑。 – o9000

我知道，這就是爲什麼我將我的答案限定爲僅用於精確匹配。如果想在某個epsilon內找到匹配的數據，從底部刪除數據只會使一些鄰居（在3D座標的情況下約爲八分之一）統一起來。使用浮點形象化很難，但考慮儘可能接近的整數鄰居255和256之間的按位差異。我不會推薦這一點。基於epsilon的搜索需要不同的數據結構。 –

用於存儲3d點的高效數據結構

回答

相關問題