四叉樹：變焦鏡頭

演算法背後的故事：像素化的地圖

想像妳在繪製一張世界地圖。

• 太平洋是巨大的，大部分是空曠的藍色海水。
• 東京很小，但擠滿了數百萬條街道和建築物。

如果妳使用等大小的正方形網格（矩陣）來儲存這張地圖，妳就會遇到問題。為了捕捉東京的細節，妳的網格單元必須非常小（1 米）。但這意味妳需要數萬億個微小的藍色方塊來儲存空曠的太平洋。這是對記憶體的巨大浪費。

四叉樹 (Quadtree) 透過「變得聰明」來解決這個問題。它看著海洋說：「這整塊 1000 公里的區域都是藍色的。我把它存為一個大方塊。」然後它看著東京說：「這裡很複雜。我把它切成 4 個小方塊。夠了嗎？不夠？那我再把這幾個小方塊切成 4 份。」

它根據數據的密度自適應地調整解析度。

為什麼需要它？

• 碰撞檢測 (遊戲)： 不要檢查子彈是否擊中了遊戲世界裡的每一個物體，只檢查與子彈處於同一個四叉樹葉子節點裡的物體。
• 圖像壓縮： 透過將大塊相似顏色分組來儲存圖像（概念上類似於 JPEG 的工作原理）。
• 位置服務： 「查找我方圓 1 公里內的所有 Uber 司機。」

演算法是如何「思考」的

這個演算法是一個遞迴分割者。

1. 盒子： 每個節點代表一個矩形區域（邊界框）。
2. 容量： 每個節點有一個最大容量（例如 4 個點）。
3. 分裂：
   • 將一個點插入節點。
   • 如果節點超過了容量，它就細分為 4 個孩子：西北、東北、西南、東南。
   • 它將現有的點移動到正確的孩子節點中。

工程決策：平衡

• 深度限制： 如果妳有 100 個點完全重疊在一起（精確副本），四叉樹會試圖無限分裂直到崩潰（堆疊溢位）。現實世界的實作會設置一個「最大深度」來阻止這種情況。
• 重建： 四叉樹非常適合靜態數據。如果物體不斷移動（像在遊戲中一樣），每一幀都重建樹可能會很慢。在這種情況下，鬆散網格或動態 B 樹可能是更好的選擇。

實作參考 (Python)

class Rectangle:
    def __init__(self, x, y, w, h):
        self.x, self.y, self.w, self.h = x, y, w, h
    
    def contains(self, point):
        return (self.x <= point.x < self.x + self.w and
                self.y <= point.y < self.y + self.h)

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

class Quadtree:
    def __init__(self, boundary, capacity=4):
        self.boundary = boundary # 矩形區域
        self.capacity = capacity
        self.points = []
        self.divided = False
        self.nw = self.ne = self.sw = self.se = None

    def subdivide(self):
        x, y, w, h = self.boundary.x, self.boundary.y, self.boundary.w, self.boundary.h
        mw, mh = w/2, h/2
        
        self.nw = Quadtree(Rectangle(x, y, mw, mh), self.capacity)
        self.ne = Quadtree(Rectangle(x + mw, y, mw, mh), self.capacity)
        self.sw = Quadtree(Rectangle(x, y + mh, mw, mh), self.capacity)
        self.se = Quadtree(Rectangle(x + mw, y + mh, mw, mh), self.capacity)
        self.divided = True

    def insert(self, point):
        if not self.boundary.contains(point):
            return False

        if len(self.points) < self.capacity:
            self.points.append(point)
            return True

        if not self.divided:
            self.subdivide()

        return (self.nw.insert(point) or self.ne.insert(point) or
                self.sw.insert(point) or self.se.insert(point))

    def query(self, range_rect, found):
        # 查找 range_rect 範圍內的所有點
        # 假設 Rectangle 類有一個 intersects() 方法
        if not self.boundary.intersects(range_rect): 
            return
        
        for p in self.points:
            if range_rect.contains(p):
                found.append(p)
        
        if self.divided:
            self.nw.query(range_rect, found)
            self.ne.query(range_rect, found)
            self.sw.query(range_rect, found)
            self.se.query(range_rect, found)

小結

四叉樹教會我們：細節是需要付費的。我們不應該花費記憶體去描述空曠的空間。透過只將資源（節點）集中在複雜性所在的地方，我們可以以極小的代價表示宏大的世界。它是「細節層次 (LOD)」的終極演算法。