代表室內地圖的數據結構

Question

假設我有一張表示室內地圖的圖像。在這張地圖上，某些區域是「允許的」，其他的則不是。然後我會定期獲得一組座標(x,y)，並且需要檢查它們是否在「允許」區域中。

目前，我用boolean[][] map變量表示此地圖，其中true表示允許。要檢查，我只是檢查值map[x][y]

但是，我代表的圖像可能會變得相當大，比方說最大5000x5000像素。因此，我的map變量在內存中變得過大（在這種情況下，假設boolean需要大約1個字節，則爲25MB）

是否有更好的數據結構，用於解決我的問題？我現在想了一會兒，但看不到任何需要更少空間的東西。

在此先感謝！

Answer 1

這種情況的常見情況是使用Rect結構的數組/ List。然後你定義這樣一個矩形定義了一個「允許」的區域。

然後，給定一個點(x, y)您只需遍歷數組/列表並檢查該點是否位於集合中的任何矩形內。你可以簡單地使用Rect.contains(x,y)。如果有任何Rect包含該問題，則回答true，否則回答false。

這應該會給你一個非常不錯的性能/內存消耗比。假設「區域」是矩形的（或者每個區域可以表示爲 - 理想情況下 - 少量的矩形）的聯合體，它通常用於您的應用程序中。

另一種選擇（假設矩形不是選項）將使用謹慎的多邊形來表示區域。如果這是可行的，你可以使用這裏提供的一個簡單的算法：http://alienryderflex.com/polygon/它可以讓你測試一個給定的點是否在時間內（甚至是非常複雜的）多邊形O(n)其中n是定義你的區域的所有多邊形的所有頂點的數量地圖。

如果您的區域是非常散（即很難使用他們甚至多邊形的矩形來表示），那麼你可能沒有其他簡單的選擇。你可以做的是（例如）創建一個包含行允許信息的數組。對於每一行，您將擁有一個數組int[]，其中每個int將包含32位，每個代表連續列的boolean值。這與您已經擁有的非常相似，但是您的內存佔用空間會縮小8倍，因爲每個值只會佔用一位而不是整個字節。