2016-04-03 53 views
2

要創建實時套接字/頻道,我需要離散值,例如具有名稱的聊天室(房間1,房間2等) ,用戶可以選擇/訂閱有限數量的預定義選項。Algo將地球分爲固定區域。然後用算法來查看給定緯度,經度和半徑的哪個區域重疊

對於我的新項目,實時的東西正在地圖上發生。因此,用戶可以發送緯度,經度和半徑,在該視野中發生的任何事件都將實時發送給他們。這確實是連續的(每個用戶的值可能是唯一的),所以爲用戶預定義套接字/信道更加困難。

這是我目前的想法,如何使其工作。

  1. 將地球劃分爲靜態,固定大小的正方形。 (任何寬度,大約500平方米)。這些現在是我們的離散插座/通道。

  2. 當用戶發送緯度,經度,半徑,發現自己的地圖覆蓋了廣場,把它們添加到每個通道/插座

    是在一個「廣場」
  3. 某些點,可能無法在用戶的實際視圖,因此客戶端必須檢查每個更新並在相關時顯示它,否則忽略它。

Here is an image to demonstrate

  • 藍點是用戶
  • 我們將用戶添加到頻道16,17,18,26,27,28,36,37,38。
  • 紅色和黃色圓點(方形16)都會實時推送給用戶。
  • 黃點與視圖相關,因此它將被添加
  • 紅點不在用戶視圖中,因此它被忽略。

我的問題: 1.有沒有更好的方法來做到這一點?

  1. 是否有這種類型的問題/問題的名稱?

  2. 這種類型的問題是否存在解決方案/算法/庫?

  3. 我該如何...

    a。將地球分成固定大小,統一編號的方格。

    b。給定一個lng,lat,radius - 計算哪些方塊與該用戶有關。

謝謝。

回答

0

是否有這種類型的問題/問題的名稱?

空間索引

是否有現有的解決方案/算法/對這類問題庫?

我敢肯定還有其他的(甚至一個也許這廣場上的作品),但這個突然出現在腦海中:

http://www.skyserver.org/htm/Old_default.aspx

採用三角形而不是正方形,但它是同樣的想法。不確定它本身是否支持半徑搜索,但是您可以進行粗略的查詢並進行細化,就像您在示例中所做的那樣。

另一種方法是,如果你只是想找到最近的用戶,你可以做一些像最近鄰居搜索的kd-tree(這是一個背離你的想法,但我不確定是什麼擁有大量套接字/通道的相對成本將是 - 您可以按照這種方式按照K級三角形的ID創建它們,其中K取決於您選擇的最小範圍)

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

相關問題