比方說，我有一個地理地圖，其中點以緯度\經度表示。 我在這張地圖上有很多點，可以隨時添加\刪除\點。用於計算具有最高密度點的地理地圖上區域的高效算法
我需要的是獲得「最熱點」 - 包含點數除以面積的最高點數的區域 - 或換句話說，點密度最高的區域。
我需要一個高效的數據結構，以及一個算法，可以重新計算任何變化的最熱點。計算複雜性和內存複雜性必須最小化，因爲點數可能會非常高。
我想知道並按照降序排列最熱點地區 - 最擁擠的地區首先，然後是不太擁擠的地區。有一個限制大小的列表是可以的 - 例如，100個最熱點。
當然，爲了防止一個孤立點上的100％密度，存在最小面積（定義爲常數）。
這裏「area」的定義是地圖上任何包含點的可感知區域。它可能是整個地圖，但算法不應該看到，當然作爲熱點=）
謝謝！ 如果需要任何澄清，請這麼說...
你在做什麼是統計學上稱爲「2維密度估計」（所以你知道去哪裏找）工作。
一種常見的方法是'內核平滑'。想象一下您的每個數據點上都有一張光盤。在該區域平滑的內核是每個點重疊的光盤數量。這是使用固定半徑的統一內核平滑的內核。
您不必使用統一內核，也不必在所有點上都具有相同的大小 - 現在是「自適應帶寬內核平滑」。
這給了你一個很容易更新的網格，特別是如果你有一個有限的內核（你可以使用高斯（又稱普通）內核，這個內核是無限的，但會被剪切到你的研究區域）。每次添加或刪除一個點時，都會增加或減少內核對密度的貢獻。
所以這是問題的一半 - 你現在有一個密度網格。然後，您可以使用聚類算法對其進行分割，並根據任何標準找到單獨的峯a）定義「峯」，並且b）將其定義爲與相鄰峯分離。其他人已經提出了聚類算法。我在十年前完成了這個統計軟件包「R」中的聚類函數。速度不是它的強項，但...
你可能想借此轉移到http://stats.stackexchange.com
好主意。 OP現在可能想要找到平滑函數的輪廓線，這可以在本地完成。問題在於點移動。 – 2011-03-09 16:16:26
一個改進可能是將點存儲到四叉樹並使用緊湊支持的徑向核，以便能夠在地圖的任何點快速計算估計的密度。然後，計算一個固定高度的輪廓等級（假設爲10，假設單位爲峯值的內核） - 如果需要，我可以對此進行擴展。每次點移動，刪除或添加時，由於四叉樹和內核函數的有界支持，需要重新計算的輪廓級曲線的部分位於該點。熱點由輪廓水平線內部的連接組件給出。 – 2011-03-09 16:32:16
我理解了光盤的比喻 - 除此之外，這看起來像是一個知識領域，我不得不進入，或找到其他人會。這將是一個很好的參考？你將如何處理分區問題？ 爲了讓這個清楚 - 假設我在紐約市有很多觀點 - 一個集中在中央公園，另一個集中在自由女神像。我想分辨出這兩個獨立的熱點地區，還要把整個城市作爲第三大熱點（根據地區/點數定義）。 – SirKnigget 2011-03-10 00:03:07
所用算法的類型將取決於點的分佈。你很可能會遇到一個更難以將組劃分成「區域」的問題。由於您似乎需要一些東西來幫助您入門，因此我建議您閱讀Convex Hulls和calculating the area of an abritray 2D polygon和how to determine if a point is in a polygon。
這太長了評論，但這只是一個想法，我怎麼會「玩」這個，看看我是否能想出一些有趣的東西。但有一點是肯定的：以下可以做得很快非常。
這可以很容易地轉換爲一些離散的問題？您首先將所有座標「對齊」到一張大地圖上（您可以定義每個方格的大小，並將每個入口地圖映射到一個這樣的點）。那麼你最終的東西是這樣的：
0000000000000000000000000000
00XX000000000000000000X00000
00X00000000000000X0000000000
0000000000000000000000000000
0000000000000000000000000000
000000X00000000X000000000000
0000000000000000000000000000
000000000000X000000000X00000
00000000000000000000000X0000
0000000000000000000000000000
然後你會計算每一個條目和它的相鄰鄰居的數量：
0000000000000000000000000000
0033000000000000000001000000
0030000000000000010000000000
0000000000000000000000000000
0000000000000000000000000000
0000001000001001000000000000
0000000000000000000000000000
0000000000001010000000200000
0000000000000000000000020000
0000000000000100000000000000
然後，你可以增加你的平方大小，說兩個人，因此將您的地圖：
（地圖是不正確的，它的突出部分給的什麼，我想一個想法）
09001001000000
00000000000000
00100001100000
00000110002000
00000002000000
00000100000000
然後你重新計算相鄰的鄰居等
對我來說，這將允許找到熱點取決於你的「決議」：你只是尋找最大的數字，這將是你的「熱點」。
因爲在這種情況下：
0000X00000
0000XX0000
0000000000
0000000000
0Y0Y000000
0000000000
0Y0Y000000
無論是「X」可以是最熱的地方（三個有趣的點接近對方）或「Y」（四點接近對方，但他們沒有比'X'那麼接近）。
因爲你說你需要速度，我只是把它變成一個離散的問題，並將我的圖表表示爲數組。然後我會考慮一個可變的「區域」大小。
看起來像一個有趣的問題上:)
開始的好主意，除此之外 - 您的表示中的「重點」可能包含多個條目，因此需要考慮這一點。將'X'替換爲該座標中的條目數，然後優化計算。 – SirKnigget 2011-03-09 23:54:49
我主要是研究，因爲我甚至不知道什麼是算法，可以幫助知識領域我回答了這個問題......有一種「生力軍」的解決方案，如你所能想象的那樣效率不高。 – SirKnigget 2011-03-09 13:20:34
你如何定義一個區域？兩點之間的最大距離是多少，以便在同一區域考慮？或者你已經有了已經定義好的區域？ – 2011-03-09 13:29:15
由於我需要降序排列的結果，只要第一個結果的密度比第二個結果的密度要高，就沒有關係，等等...... 「區域」必須至少有一個防止一個孤立點的100％密度（當然會增加到主要問題）。 – SirKnigget 2011-03-09 13:37:35