2013-05-11 44 views
0

假設您有一個大網格。你有一些以點爲單位的對象。假設合理的方式來實現這一點,在運行時具有合理的性能(即說合理大小的網格的遊戲),假設內存是可用的是:如何搜索影響空間點的對象

你有指針,每個對象的每一個點上操作一個特定的點。

讓我們假定,但是,網格的精度是望而卻步,你不希望存儲指針每一點,想必你會實現這樣的:

拆分電網分層

的接下來的問題是,找到包含一組所述子集中的一個點的空間子集的最佳方法是什麼?

也許:

一個可以做通過整個組或一個罐索引原點/逆POS軸的幼稚選臺搜索(N),然後執行匹配範圍的交集。

至於存儲在內存中的數據結構對象的屬性的索引,可以推測最佳實施:

保持在對象屬性 搜索索引B樹索引和不相交/聯合進行查詢

所以基本上這是一個問題:

  1. 我錯過了關於從網格請求這類信息的內容嗎?
  2. 如何一個一般無二有關實現內存索引(當然他們可能只用一大組用很小的範圍內是有用的,考慮到路口將是巨大的成本是多少?)

Sorted String Table (SSTable) or B+ Tree for a Database Index?

有那個線程。我不明白他們是如何存儲索引的,看起來像是一個數組。他們如何解決插入/移入(動態/磁盤)陣列中間的N成本問題?

+3

看看k-D樹或quadtrees。 – wildplasser 2013-05-11 18:01:45

回答

1

如果我正確理解你的問題,因爲你有對象在網格上的一系列點上操作,那麼你可以用2-dimensional interval tree來表示這個。