我有一個2D空間的對象，每個對象都有座標向量和一個相對於他的座標的頂點數組，現在我需要一種有效的方式來存儲對象，這個存儲應該能夠添加和刪除對象，也是最重要的部分是碰撞檢測：2D空間中對象的高效數據結構
我想獲得一個對象的列表有機會碰撞（近鄰等），應該是快速和簡單的約
O([number of objects with collision chance] * log([number of all objects]))這樣，當沒有關閉對象時，它應該在O(1)中執行，而不是隻使用g的蠻力方式覆蓋了O(n)中的所有對象。
詢問是否有不清楚的地方。
也許你知道一些關於這個主題或任何好主意的鏈接。
謝謝。
Chipmunk Physics和Box2D都提供有效的2D碰撞檢測。你可以使用其中之一，或者只是檢查它們的來源。
您可以通過使用二進制空間分區來使用樹型數據結構，下面是關於它的wikipedia article。據我所知，這是存儲有關n維空間中物體位置信息的最有效方式。
這裏是如何工作的：假設你有以下字段
比方說，你已經有了100×100的空間。
你有6個對象中有一個名爲A到F的座標 A（25,25） B（25,75）， C（25,85）， d（75,75 ）， E（90,60）
現在，我們將空間分爲4部分，每部分將成爲樹中根節點的一個子節點。左上角只包含A點，所以這是一個葉節點。 左下角包含2個對象B和C，因此它們將成爲第二個屏幕的葉節點。 現在右下角會有3個元素，我們不希望因爲二叉樹的想法，所以我們再做一個細分。通過遞歸的方式，您可以獲得一個非常高效的數據結構，用於在2D空間中查找對象。
您可以使用quadtree來檢查所有附近的物體。
你想要使用空間索引或四叉樹。四叉樹可以是簡單的空間填充曲線（sfc）或希爾伯特曲線。 sfc將2d複雜度降低到1d複雜度，並用於許多地圖應用程序或熱圖。也可以使用sfc來存儲郵政編碼搜索。你想搜索Nick的希爾伯特曲線四叉樹空間索引博客。