2D 地圖分區外框：從 goo 濾鏡到 SDF 閉運算

2D 地圖上，每張卡片屬於一個分區（LLM / TOOLS / STATE），RUNTIME POLICY 是墊在最底下、包住全部的底圖。這篇記錄「分區外框怎麼畫」這件事改了四版的過程：每一版為什麼換、怎麼做、代價是什麼。

程式碼在 src/lib/contour.ts（演算法）與 src/pages/map.astro（套用），自我檢查是 src/lib/contour.check.ts。

目標

• 外框包住同區所有卡片，形狀像液體或水域，不是矩形拼貼
• 同區永遠是一整塊，遠處的卡片也要連進來
• 區與區可以互相覆蓋，由下到上依序是 RUNTIME POLICY、三個核心區、AGENT CORE
• 描邊粗細均勻，填色就是設定的顏色

演變

v1：goo 濾鏡 + 最小生成樹橋

每張卡片外擴 PAD 成圓角矩形，同區卡片之間沿最小生成樹（MST）各畫一條粗線當橋。整組交給 SVG 濾鏡處理：

<feGaussianBlur stdDeviation="10"/>
<feColorMatrix values="1 0 0 0 0  0 1 0 0 0  0 0 1 0 0  0 0 0 22 -9"/>

先模糊，再把 alpha 以 22a − 9 切回硬邊，相鄰的形狀就會融成一塊。濾鏡的輸出只有像素，沒有路徑可以加 stroke，所以描邊的做法是：先畫一份外擴 PAD + 1.5 的描邊色，再把外擴 PAD 的填色疊上去，只露出外圈。

這一版陸續出了幾個問題，每個都只能用補丁處理：

根本的限制是：形狀只存在於像素裡，沒有幾何。所以描邊得繞路做，顏色有精度問題，形狀也受模糊半徑牽制。

v2：SDF + smin + marching squares

改成用數學定義形狀，最後輸出向量路徑：

1. 每個形狀都有一個有號距離函數（SDF），在內部為負。卡片是矩形，橋是膠囊形（有粗細的線段）。
2. 同區的 SDF 用 smooth-min 合併：smin(a, b, k) = min(a, b) − h²k/4，其中 h = max(k − |a − b|, 0) / k。距離小於約 k 的兩個形狀會融成一塊，接縫是圓角。
3. 在網格上取樣，用 marching squares 取 field = PAD + LINE/2 的等值線，串成封閉迴圈，輸出成 <path>，用 fill-rule="evenodd" 處理洞。

一條 path 同時帶 fill 和 stroke，SVG 會先填色再描邊。描邊以等值線為中心、一半在內一半在外，所以等值線要多外推半個線寬（LINE/2）。goo 時代的兩份疊畫、濾鏡、色彩精度問題一次全部消失。

marching squares 的重點：

• 每格只看四個角在裡面或外面，共 16 種情況，邊界穿過的位置用線性內插算出。
• 兩個對角在裡面、另外兩角在外面的鞍點格，用格子中心的值決定哪兩個角相連。
• 交點以它所在的網格邊命名（h,i,j 或 v,i,j），同一個點在相鄰兩格會拿到同一個名字，最後沿著這些名字串成迴圈。
• 網格最外圈強制算作外面，所以每條迴圈一定會封閉。

效能問題：每個取樣點都要跟這一區的所有形狀比一次。底圖大約有 100 個形狀，量到 364ms。

• Math.hypot 換成 Math.sqrt 後是 265ms。hypot 為了精度多做了很多事，在每點、每個形狀都要跑的迴圈裡明顯偏慢。
• 用外框（bounding box）先算距離下界，確定太遠、不影響結果的形狀就跳過 SDF，同時把底圖改成 8px 網格：120ms。

v3：由形狀出發（splat）

把迴圈反過來：網格先全部設成 ∞，每個形狀只在自己外框外擴 level + smooth 的範圍內，逐格做 v = smin(v, sdf)。計算量從「點數 × 形狀數」降到「各形狀涵蓋的面積總和」，量到 77ms，底圖也能回到 4px 網格。

途中有一個判斷錯誤：我原本以為跳過遠處的形狀不會改變結果。寫 self-check 跟「每點都算全部形狀」的暴力版比較時，差距最多約 3px。原因是 smin 不滿足結合律：遠處的形狀雖然算不上最近，還是會先把中間值往下拉一點，後面再合併時結果就不同了。兩種結果其實都是合理的平滑聯集，差別只在圓角的曲率。最後把程式註解改成照實描述，self-check 也改驗證真正成立的性質：外框從不切進「形狀外擴 level」的範圍，而且只在有限範圍內往外長。

v4：閉運算，畫成一整片水域

smin 的外觀還是「一顆顆泡泡用管子串起來」。遠處的卡片靠一根細橋連著，看起來不像同一片水。改用形態學的閉運算（closing）：

1. 外擴（dilate）round：{ d ≤ round }，其中 d 是點到最近形狀的距離再減掉 PAD，直接由 SDF 取最小值得到，是精確的。
2. 內縮（erode）round：只保留「離外擴後的外側至少 round」的點。這需要知道網格上每個點到最近外側點的距離，也就是歐氏距離轉換（EDT）。

直觀的理解：半徑 round 的圓滾不進去的地方都算水。比 round 窄的海灣和縫隙都被填平，岸線往內彎的地方至少是半徑 round 的圓弧。

距離轉換用 Felzenszwalb & Huttenlocher 的做法：先對每一列、再對每一行做一維的「拋物線下包絡」，兩趟都是 O(n)，而且結果是精確的平方歐氏距離。

另外兩個細節：

• 連通性：只做閉運算的話，距離太遠的卡片還是可能變成孤島。所以同區卡片之間仍沿 MST 加上「跟卡片一樣粗」的帶狀形狀，閉運算會把它們撐成開闊的水面，而不是細管。
• 精度：距離轉換量的是「到最近的外側取樣點」，跟真正的邊界會差到一格。
  • 如果直接用 min(d, round − dist)，往外凸的岸線（也就是卡片自己的邊）會被這個誤差弄成鋸齒。
  • 所以把閉運算的結果往內偏 step + blend，再跟精確的 d 取聯集：凸岸由精確的 SDF 決定，只有被填平的海灣帶著網格誤差。
  • 兩者的接縫用 blend = 3·step 的 smooth-min 過渡，否則圓弧接到卡片邊時會留下小缺口。偏移量裡要包含 blend，不然接縫的平滑會反過來影響凸岸。

回傳給畫面縮放用的邊界，是「形狀外擴 level」的外框，而不是網格範圍。閉運算只會填補形狀之間的空間，不會超出這個外框；網格則必須多留 round 的邊距給外擴那一步。如果用網格範圍，自動縮放會把地圖縮得太小。

最終量到約 130ms，比 v3 多出的時間主要花在距離轉換和較大的外擴範圍。

精髓

• 形狀是距離，不是像素。 有了 SDF，外框就是一條等值線：聯集是取最小值、外擴是加常數、描邊寬度是等值線的偏移量，全部都能精確控制。
• 閉運算讓「像水」有定義。 「一片水域」變成一個可以調的參數：round 越大越接近凸包，越小越貼近卡片。
• 由形狀出發。 讓每個形狀只碰自己附近的格子，成本取決於面積而不是乘積。這對任何「很多小形狀、一張大網格」的問題都適用。
• 精確與近似分開處理。 凸岸交給精確的 SDF，只讓海灣承擔網格誤差，所以最顯眼的邊始終是乾淨的。

效能

在 headless Chromium 裡量，整張地圖所有分區算一次的時間：

只在開頁時算一次，平移和縮放是 CSS transform，不會重算。

取捨

• 允許小誤差：v3 的 smin 順序效應約 3px，v4 的海灣網格誤差不到一格。凸岸都是精確的。
• 疊層，而不是分割：也可以讓每一點只屬於一區（就像 3D 的領地模型），整張圖只塗一次。但會失去覆蓋的層次感，底圖也不再墊在下面，所以沒有採用。
• 沒採用的方案：
  • Bubble Sets：刻意避開別區的卡片，跟「允許重疊」的方向相反。
  • 精確幾何聯集（Clipper 之類）：需要引入依賴，而且圓角要另外處理。
  • 沿邊界追蹤：每個洞都要各自找起點，很脆弱。
  • GPU shader：結果又回到像素。
• 底圖網格加粗：底圖最大，又只需要大致的輪廓，所以用 2 倍的網格間距換速度。

參數

之後可以做

• 卡片數量多到開頁變慢時：底圖可以再加粗網格；或者先算一個粗網格，只在邊界附近細分。
• 如果想讓岸線有自然的起伏：在 d 上疊一點低頻雜訊（專案裡已經有 simplex-noise），凸岸也會跟著微微波動。