空間排序百萬點在三維空間

各點是一個對象

Struct Point 
{ 
    double x; 
    double y; 
    double z; 
};

的萬點被存儲在一些隨機順序的C++矢量MyPoints內部。

我想根據空間中的點的空間分佈對這些百萬點進行排序，使得在排序後我的數組內的物理距離更近的點也應該更接近。

我就怎麼做，這是如下第一個猜測：第一次分揀點相對於z軸，然後進行排序沿Y軸點，然後現在首先梳理沿X軸

MyPointsSortedAlongZ = Sort(MyPoints, AlongZAxis) 
MyPointsSortedAlongY = Sort(MyPointsSortedAlongZ , AlongYAxis ) 
MyPointsSortedAlongX = Sort(MyPointsSortedAlongY , AlongYAxis )

點，我不知道這種方法是否正確。我的最終排列點MyPointsSortedAlongX是否在空間上完全排序（或在空間上幾乎排序）？其次，如果這種方法是正確的，那麼這是否是最快的方法呢？什麼是更好的方法來做到這一點？

來源

2014-04-01 nurabha

沒有辦法做到這一點，並獲得空間距離到線性（1D陣列）距離的完美映射，因爲您正在降低維度。您可能對[*空間填充曲線*]（http://en.wikipedia.org/wiki/Space_filling_curve）感興趣，以此作爲實現此目的的手段。 –

另一種方法是將空間分解爲3d數組，並在每個單元格中存儲該單元格中的點或對它們的引用。就我個人而言，我喜歡@OliCharlesworth的建議，即更好地使用空間填充曲線，但編程起來可能非常棘手。 –

我沒有提到我的帖子中的空間填充曲線，雖然我知道它。我在考慮是否構建一個Barnes-Hut樹，然後按順序遍歷該樹可以導致空間排序（但也許我錯了）。 – nurabha

的CGAL庫提供了一個空間填充曲線算法，可以爲這項任務有用的implementation。

來源

2014-04-02 05:54:32 sloriot

感謝分享。我已經在看它 – nurabha

嗯，這真的取決於你要使用兩個陣列之間進行比較，但看例如在其上的相鄰點之間的差異和度量什麼指標：

metric(arr) = sum[ d(arr[i],arr[i-1]) | i from 1 to n ] 
where d(x,y) is the distance between point x and point y

注意的這個度量的最優（最小）解決方案基本上是經過所有點的最優（最短）路徑。這是Traveling Salesman Problem (TSP)，這是NP-Hard，所以沒有已知的多項式解決方案。

我建議 - 首先確切地定義比較兩個數組的指標是什麼。
然後，使用啓發式或近似度量標準，如Genetic Algorithms或hill climbing，或將問題簡化爲TSP，並使用已知的啓發式/近似值。

關於你的方法：這是很容易看到它是不是最佳的簡單的例子：

[(1,100),(1,-100),(2,0)]

假設主排序x，二次排序y。
它會給我們的「排序」向量：根據上述指標

[(1,-100),(1,100),(2,0)]

，我們得到metric(arr) ~= 300

然而，爲了[(1,-100),(2,0),(1,100)]將得到我們metric(arr) ~= 200

因此，建議的啓發並不是最佳的（如預期的那樣）。

來源

2014-04-01 08:24:32 amit

我需要近似排序和快速排序。因此，對性能影響最小的衡量指標就是我所需要的。 – nurabha

也許這會有所幫助： A Template for the Nearest Neighbor Problem (DDJ 2001)

來源

2014-04-01 08:38:11

這不是最近鄰居問題。 NN是關於從最接近單個點的樣本中找出一個點。在這裏 - 問題是關於許多點的優化排序。如果您認爲問題與某種相關性有關，請解釋如何減少使用NN的問題，然後鏈接到您的文章，解釋如何使用減少的問題。 – amit

只是一個猜測 - 對不起。 –

在三軸上分類三次是浪費。第三類將完全取消其他類別所做的工作。

來源

2014-04-02 12:30:30

你沒有告訴我們「身體接近的點也應該更接近我的陣列」背後的動機。知道這可能會讓我們提供更有建設性的答案。空間填充曲線根本沒有這個屬性！ –

我認爲你對空間填充曲線是不正確的。我的陳述背後有三個主要動機：1.改善記憶的局部性：記憶中的空間關閉點意味着更高的空間局部性......這意味着更好地利用緩存在cpus上... gpus它會改善記憶聚合。 2.易於區域分解：通常一些計算將與點相關聯，並且通過空間排序點，可以很容易地在cpus/gpus上的線程之間拆分計算。 3.提高負載均衡：這是另一個可以提高某些並行算法的因素。 – nurabha

看到這個http://corte.si/%2Fposts/code/hilbert/portrait/index.html – nurabha

空間排序百萬點在三維空間

回答

相關問題