2010-03-11 95 views
3

我有位置數據存儲在Core Data中的對象,我希望能夠獲取並顯示與當前位置最近的點。我知道有些公式會計算從當前緯度/經度到存儲緯度/經度的距離,但我很好奇最好的方式來對存儲在覈心數據中的一組1000+點執行此操作。我知道我可以將核心數據中的點返回給一個數組,然後循環遍歷那些尋找點間距離的最小值,但我想可能會有更高效的方法,可能以某種方式利用核心數據。什麼是計算最近點的有效方法?

任何有識之士將不勝感激。

編輯: 我不知道我是如何在初始搜索時錯過的,但this SO question建議只是遍歷核心數據對象的數組,但使用基於當前位置的邊界框限制數組大小。這是我能做的最好的嗎?

+1

使用邊界框聽起來很合理,應該很快得到第一組點,如果猜測是好的,不需要迭代太多。技巧是猜測正確的盒子大小,我想你可以從一個小的開始,並通過某個因子增加它的高度和寬度,直到找到多個點,然後開始迭代。 – Douglas 2010-03-11 09:23:19

+0

我認爲[this](http://en.wikipedia.org/wiki/Voronoi_diagrams)可以幫助你。 – user272879 2010-03-11 09:02:17

回答

2

據我所知,它看起來好像在這種情況下,最好的辦法是返回一個數組使用當前位置周圍的邊界框的點數。

如果返回的數組爲空,則可以檢索當前位置的某個範圍內的點,然後增加框的大小。一旦某些結果回來,計算數組中最近的並使用該點。

2

我不知道很多關於核心數據,但也有好喜歡Quadtree已知的算法來解決這個問題

1

什麼你正在做被稱爲Nearest neighbor search並具有描述方法用於計算一個維基百科條目它。我認爲這是一個良好的開端作爲每個方法的複雜性是國家,所以你可以衡量如何實施將如何:)

到NNS 問題最簡單的辦法是從查詢計算距離 複雜指向數據庫中的每個其他 點,保持跟蹤 「迄今爲止最好的」。這種算法, 有時被稱爲幼稚 方法中,具有(ND)O的運行時間

局部性敏感散列(LSH)是用於分組在空間 點分成基於一些距離「桶」一個 技術 度量在點上運行。這是在所選指標的 彼此靠近點 被映射到相同的 桶高概率

相關問題