RecMap:Rectangular Map Approximations

[toc] # [RecMap : Rectangular Map Approximations](https://ieeexplore.ieee.org/document/1382888) >[name=Presenter: Chun-Hung Yu][time=Date: Tue , July 28, 2020] [name=Publisher: IEEE][time=Date of Conference: Oct, 2004] --- * slide: https://hackmd.io/@king87515/recmap# --- ## Authors >[name=Roland Heilmann∗ Bayer Technology] [name=Daniel A. Keim† University of Konstanz] [name=Christian Panse‡ University of Konstanz] [name=Mike Sips§ University of Konstanz] --- ## Abstract * 針對地理空間數據集提出了一種新穎的視覺化技術，稱為**RecMap**。 * 為一種全自動技術。 * 以顯示區域的**矩形**分區保留許多重要地理空間約束的地圖區域。 * 增強了對全局和局部的相關性。 **`Keywords: Geographic Visualization,Information Visualization, Database and Data Mining Visualization`** --- ## 1. Introduction * 許多應用領域的數據是按地理位置收集和索引的。然而地理空間數據在現實世界的不均勻分佈會對生成的地圖視覺化的效果有直接影響。 * 使用**經典面積圖**的問題在於，它們可能在重要性不高的大面積上突出顯示圖案，造成++無法快速地理解所呈現的地理空間信息++。 --- ## 1. Introduction * 手動構建製示意地圖是一項非常困難的任務。因為在一方面，我們必須根據其地理空間統計值來調整區域的大小。另一方面，我們必須考慮到區域的（原始）==形狀==及其鄰域關係（==拓撲結構==）要保留得盡可能多。 * 據我們所知，不存在任何自動程序來計算地圖的**分割層次**(split hierarchy)。且提出的大多數技術都沒有考慮到地圖的形狀和拓撲，或者無法完全消除連續製圖上的面積誤差。 --- ### 經典面積圖 **==重要性可能不高的大面積區域上突出地顯示圖案。==** ![](https://i.imgur.com/l9qIhUx.png) --- ### Circular Cartograms **==以圓形呈現，忽略了多邊形的形狀。==** ![](https://i.imgur.com/RUIczYm.png) --- ### TreeMaps **==此種呈現方法能以不同顏色區塊呈現不同資料，可以透過區塊大小看出各資料數值大小比較。==** **==當該區塊範圍越大，代表該資料數值越大、越多。==** ![](https://i.imgur.com/AiCBIBr.png) --- ## 2. Contribution * 用**矩形近似**熟悉的土地覆蓋的地圖區域形狀，並找到可用屏幕空間的分區，其中這些矩形區域的面積與給定的統計值成比例。 * 嘗試將矩形放置在盡可能靠近其原始位置並儘可能靠近其鄰居的位置。 * 我們定義了此優化問題的兩個變數，並提出了兩個相應的演算法，區別在於，++第一種方法不允許有空白空間，而第二種方法則保留了多邊形的形狀++。 Note: 這些統計值可能是人口、薪資、資源... 保留多邊形的形狀指的是整個地圖的拓樸結構 --- ### Optimization Problem ![](https://i.imgur.com/EXeAlKO.png) --- ## 3. Problem Definition * **先滿足 constraints 再轉向目標函數的單個組成部分。** **:pencil: *P* : A formulation of the problem of determining a near–optimal cartogram** **:pencil: *Z* : Vector ，為地理空間的數據值** * $\scriptsize P=\{p_1,p_2,\ldots,p_R\}$ * $\scriptsize \overline{P}=\{\overline{p}_1,\overline{p}_2,\ldots,\overline{p}_R\} \\\scriptsize\to consisting\ of\ R\ polygons\ or\ region\ \\\scriptsize\to Z=(Z_r)_{r_=1,\ldots,R}\ of\ spatial\ data\ values\ \\ \scriptsize \qquad\enspace Z_r\ge0\ with\sum\limits_{r = 1}^R{Z_r=1}$ --- ### 3.1. Constraints * 𝑃 為一**平面圖**。 * 任一多邊形 𝑝∈𝑃 皆為==矩形==。 * 任一多邊形 𝑝∈𝑃 對於另一多邊形 𝑝∈𝑃 至少存在一個不同的鄰居。 $\to$ *P* 須遵守這些 constraints 稱為 **feasible**。 $\to$ 這些 *P* 所成的集合，記作 *M*。 --- ### 3.2. Objective Function **==5個標準來評估 *P* 的質量==** * 質量取決於兩點: * *P* 的多邊形是否可以在 *P* 中輕易辨別 * *P* 的多邊形需反映 *Z* 給出的地理空間數據值 * Area * Shape * Topology * Relative polygon positions * Empty space --- ### Area * The area error $𝐴(𝑃)=𝐴(𝑃,𝑍)$ with $A(P):=\frac{1}{R}\sum\limits_{r = 1}^R{\frac{|\varepsilon_r-Z_r|}{Z_r}}$ **==平均相對偏差==** * $\varepsilon_r:=a(p_r)/A_f(P)$ **==全部面積分之r區域面積==** * $A_f(P):=\sum\limits_{r = 1}^R{a(p_r)}$ --- ### Shape * The shape error $𝑆(𝑃)=𝑆(𝑃,\overline{P})$ * $𝑆(𝑃):=\frac{1}{R}\sum\limits_{r = 1}^R{\frac{|s(p_r)-s(\overline{p}_r)|}{s(\overline{p}_r)}}$ **==平均相對偏差==** * $s(p_r), s(\overline{p}_r)$ 分別為各自的水平最大延伸率和垂直最大延伸率的比值 ![](https://i.imgur.com/xb6WcDV.png =500x) --- ### Topology * 先求 $P,\overline{P}$的**相鄰矩陣**或者 **pseudo dual graphs** ($G_a,\overline{G}_a$) * The topology error $T(𝑃)=T(𝑃,\overline{P})$ with $T(P):=\frac{|\overline{E}_a\backslash E_a|+|E_a\backslash \overline{E}_a|}{|\overline{E}_a\cup E_a|}$ **==偏差==** ![](https://i.imgur.com/EAXJQsh.png =300x) * $\overline{E}_a,E_a$ : 分別為 $\overline{G}_a$ 和 $G_a$ 的邊集合 * Normalized to the interval [0,1] --- ### Topology * adjacency graph of U.S map(左圖) * 右圖其相對應地圖的分區，紅色部分表示拓撲錯誤 ![](https://i.imgur.com/WYFe9HZ.png =600x) ![](https://i.imgur.com/2uWKSqy.png =500x) --- ### Relative polygon positions * The (relative) position error $R(𝑃)=R(𝑃,\overline{P})$ with $R(P):=\frac{2}{R\cdot(R-1)}\cdot\frac{1}{180^o}\sum\limits_{r = 1}^{R-1}\sum\limits_{\rho=r+1}^{R}{ \alpha_{r,\rho}}$ * $\alpha_{r,\rho}:=arccos\frac{{(\vec{\overline{u}}_{r,\rho}\cdot\vec{u}_{r,\rho})}}{|\vec{\overline{u}}_{r,\rho}|\cdot|\vec{u}_{r,\rho}|}$ **==$p_r \ and\ p_{\rho}$多邊形相對位置的偏差(角度)==** * $\vec{\overline{u}}_{r,\rho}=c(\overline{p}_{\rho})-c(\overline{p}_{r})$ * $\vec{{u}}_{r,\rho}=c({p}_{\rho})-c({p}_{r})$ **=="c()":重心==** * Normalized to the interval [0,1] --- ### Empty space * 製作矩形圖時，$P$ 可能會有孔洞或者空白區域 * The empty space error $E(P)$ with $E(P):=\frac{A_t(P)-A_f(P)}{A_t(P)}$ * Normalized to the interval [0,1] * $A_t$ 代表被 $P$ 包圍的空間區域 --- ### Formulation of the optimization problem * $𝐹(𝑃)=(𝐴(𝑃),𝑆(𝑃),𝑇(𝑃),𝑅(𝑃),𝐸(𝑃))$ * Variant 1 (MP1) * Min.    𝐹(𝑃) * s.t.      𝑃∈𝑀, 𝐴(𝑃)=0, and 𝐸(𝑃)=0. * Variant 2 (MP2) * Min.    𝐹(𝑃) * s.t.      𝑃∈𝑀, 𝐴(𝑃)=0, and 𝑆(𝑃)=0. $\to$ MP1,MP2 is ==NP-hard== optimization problems --- ### Traditional map ![](https://i.imgur.com/2o66YJE.png) --- ### RecMap for (MP1) * Variant 1 (MP1) * Min.    𝐹(𝑃) * s.t.      𝑃∈𝑀, 𝐴(𝑃)=0, and 𝐸(𝑃)=0. ![](https://i.imgur.com/LLKCRp6.png =400x) --- ### RecMap for (MP2) * Variant 2 (MP2) * Min.    𝐹(𝑃) * s.t.      𝑃∈𝑀, 𝐴(𝑃)=0, and 𝑆(𝑃)=0. $\because$ 不允許有形狀誤差 $\therefore S(P)=0$ ![](https://i.imgur.com/plkZrxd.png =400x) --- ## 4. The RecMap Algorithm * Step of map partition problem 1. 啟發法 (heuristic)**==MP1==** 1. 最佳近似解 (near-optimal solution)**==MP2==** * genetic algo. : 不斷迭代，為一種最佳化的搜尋演算法。 * $\hat{F}$ (means of a weighted objective function) is derived from $F$ **==可以由使用者設定權重以達到其想要的視覺呈現。==** --- #### Example : 對每個 constraints 設權重所帶來的結果 $\tiny(a) T(P)=1$, $\tiny(b) R(P)=0$, $\tiny(c) E(P)=0$, $\tiny(d) conbination\ of\ all\ constraints\ (weight=1)$ ![](https://i.imgur.com/M9W0Zqz.png =500x)  --- ### 4.1. Variant 1 |![](https://i.imgur.com/Obcfp9y.png =1300x)|<ol><li>$\widetilde{P}$ : 初始化參數，記錄一連串的 cartograms，確保沒有空區域發生。<li>[有一矩形行政區包含2個重心，則需分裂。](#/27)</li></li><li>$\lambda$為迭代次數</li><li>$I_{\lambda}\in{\{0,1\}}$</li><li>最後相當於一個p只有一個重心。</li></ol>| | --- | --- | --- ![](https://i.imgur.com/yYqDNZT.png) --- ### 4.2. Variant 2 |![](https://i.imgur.com/k7UYGQ8.png =1300x)|<ol><li>$\overline{G}_{a_x}$: $\overline{P}$的外部區域例外節點(R+1)的相鄰矩陣</li><li>$p^c$ 從 $\overline{p}_{R+1}$到某個行政區 $p_{r}$最大距離($d_{r,R+1}$)</li><li>在初始化步驟中，我們選擇一個多邊形 $p^c$(core polygon)作為佈局或製圖的中心</li><li>在主要步驟中，從 $p^c$開始，將其餘周圍R-1個多邊形圍繞放置直到$P :=\widetilde{P}$</li></ol> | |---|---|  --- ![](https://i.imgur.com/8X5EmqH.png) --- # Thank you for listening