如何搜索影響空間點的對象

Question

假設您有一個大網格。你有一些以點爲單位的對象。假設合理的方式來實現這一點，在運行時具有合理的性能（即說合理大小的網格的遊戲），假設內存是可用的是：

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

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

拆分電網分層

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

也許：

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

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

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

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

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

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

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

Answer 1

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