區域四叉樹資料結構

區域四叉樹用於表示二維空間的劃分，即將區域劃分為四個相等的象限、子象限等，每個葉節點包含與特定子區域對應的資料。樹中的每個節點要麼與正好四個子節點關聯，要麼沒有子節點（葉節點）。遵循這種分解策略（即細分子象限，直到子象限中存在需要進一步細化的有趣資料）的四叉樹的高度，對空間中有趣區域的空間分佈敏感並依賴於它。區域四叉樹被認為是一種trie。

深度為n的區域四叉樹可以用來表示一個由2n × 2n畫素組成的影像，其中每個畫素值要麼是0要麼是1。根節點用於表示整個影像區域。如果任何區域中的畫素既不是全部為0也不是全部為1，則對其進行細分。在此應用中，每個葉節點用於表示全部為0或全部為1的畫素塊。請注意，當這些樹用於儲存影像時，在空間方面可能節省的潛力；這些影像通常具有許多相當大的區域，在整個區域中具有相同的顏色值。與其儲存影像中每個畫素的大的二維陣列，不如使用四叉樹，它能夠以比我們原本需要的畫素解析度大小的單元大許多劃分級別來捕獲相同的資訊。畫素和影像大小能夠繫結樹的解析度和整體大小。

區域四叉樹也可以實現為資料欄位的可變解析度表示。例如，某個區域的溫度可以儲存為四叉樹，每個葉節點儲存其表示的子區域的平均溫度。

如果實現區域四叉樹來表示一組點資料（例如一組城市的緯度和經度），則對區域進行細分，直到每個葉節點最多包含一個點。

更新於：2020年1月8日

578 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始學習
廣告