Voronoi Cover

發生災害時,如何用地圖快速呈現各地區最近的救護站?在做地理資料視覺化時,常有這樣的需求:依據站點將地圖切分成許多塊,每一塊都有專屬最方便的站點;想要做到這樣的效果,我們可以使用「Voronoi Diagram」,至於要怎麼實作,我們就在這篇文章中簡短介紹。

走在路上,如果想要找間便利商店,我們會打開電子地圖搜尋商店,然後挑一間看起來最近的商店朝著他走去。看似簡單的動作由電腦來做卻不容易;最簡單的做法,是先將所有的便利商店列出來,逐一用當前位置算距離,再取出距離最短的一個。

聽起來簡單,但這個做法一次只能算一個點,當我們想要製作一份地圖用分區的方式告訴每個讀者距離他們最近的便利商店,我們必須算過地圖上所有點,相當的費時。

不過  D3.js 幫我們解決了這個困擾,它實作了「Voronoi 演算法」- 將平面根據多個點切分成許多小塊,每一塊對應到一個這一帶最「方便」的點。D3.js  的實作概念並不複雜:

  1. 我們準備好多個點,餵給 d3.geom.voronoi 物件
  2. d3.geom.voronoi 傳回一組多邊形,各對應到每個點,代表在該多邊形範圍內最近的點。

如果對 D3.js 不熟悉,可以先讀一下我們先前的專文「網頁視覺化利器 - D3.JS 簡介」。下面為使用 voronoi 的範例,我們在 data 變數中準備了三個點,並利用 voronoi 製作了三個多邊形放到 polygons 變數中:

  var data = [[0,0], [100,100], [200,200]];
  var voronoi = d3.geom.voronoi();
  var polygons = voronoi(data);

產生的多邊形陣列 polygons 可以用 Array.join 函式組成 SVG <path> 所需要的屬性:

  var d = "M" + polygons[0].join("L") + "Z";

搭配 D3.js 核心的資料綁定函式集,一個隨機產生 Voronoi 的完整程式碼如下:

  for(var i=0,data = []; i <100;i ++) data.push([Math.random()*800,Math.random()*600]);
  var voronoi = d3.geom.voronoi();
  var path = d3.select("svg").selectAll("path").data(voronoi(data)).enter().append("path");
  path.attr({
    d: function(it) { return "M" + it.join("L") + "Z"; },
    fill: "none",
    stroke: "black"
  });

上述程式碼的執行結果類似下圖:

Voronoi Example 1

範圍限定

最常應用  Voronoi Diagram 的地方可說就是地圖了,不過由於台灣是個海島,單純應用 Voronoi Diagram 在台灣上的話,你會看到多邊形也包含到海洋、其它國家等等地方,有時候並不全然是我們要的效果。這時候,我們可以利用 d3.js 提供的另一組「d3.geom.polygon」函式來搭配使用,將產出的多邊形調整成我們期望中的形狀。

用數據看台灣 / 空氣品質地圖

Voronoi Diagram 應用範例:用數據看台灣 / 空氣品質地圖

當我們準備好多邊形座標點陣列以後, d3.geom.polygon 提供了三個方便的函式讓我們針對座標點陣列做操作,包含了:

  • centroid: 計算多邊形中心
  • area: 計算多邊形面積與方向 ( 順時針或逆時針 )
  • clip: 計算多邊形交集

其中的 clip 即是我們這次要使用的工具函式,有了 clip ,我們可以事先準備一個特殊的形狀 ( 例如,台灣本島外形 ) ,然後將前面計算出來的 voronoi 多邊形與台灣做交集,最後產生的結果自然就不會跨到台灣本島之外了。

要使用 d3.geom.polygon ,我們先將準備好的多邊形陣列用 d3.geom.polygon 包裝,:

  polygon1 = d3.geom.polygon(polygon1);
  polygon2 = d3.geom.polygon(polygon2);

接著,便可以直接對包裝過後的多邊形呼叫上面三個輔助函式:

  polygon1.clip(polygon2);

比方說,我們先建立一個接近圓形的多邊形,圓心在 (400,300) 的位置,半徑為 100:

  var circle = [];
  for(var i = 0; i < 360; i++) circle.push([
    400 + 100 * Math.cos(i * 3.14 / 180), 
    300 + 100 * Math.sin(i * 3.14 / 180)
  ]);
  circle = d3.geom.polygon(circle);

接著在繪製 voronoi 多邊形前,將這個圓形拿來計算交集:

  d3.select("svg").selectAll("path").data(
    voronoi(data).map(function(v) { circle.clip(d3.geom.polygon(v)); })
  );

 

我們會得到類似下圖的效果:

Voronoi in Circle

像這樣的效果也可以應用在表現地標一定距離內的區域,比方說買房子時我只關心 500 公尺內有便利商店的區域,那就以每間便利商店為圓心建立許多 500 公尺的圓取Voronoi Diagram 交集就可以了。

如果搭配 Force Layout 讓點動起來,還可以做到類似 agar.io 單細胞遊戲的效果;比方說,下面這個例子的細胞會彼此聚在一起,滑鼠移上時則會彈開:

結合線上地圖

正如先前提到的, Voronoi Diagram 常見到在地圖上的應用,因為「距離最近」這個概念常用在我們搜尋地點上。其實我們的確可將 D3.js 與 Google Maps 、 OpenStreetMap 等等的線上地圖相結合,做出更有趣的應用,不過由於篇幅關係,這次我們先不談如何整合應用地圖與視覺化,留待未來另行專文介紹,有興趣的朋友再請繼續關注資料視覺化網站囉! 🙂

Leaflet

 


Written by infographics.tw

6 Comments

infographics.tw

路人你好, geom.polygon 的 clip 函式會受到順、逆時針的影響而產生不同的效果
你可以試著把產生圓該段的 400 + 100 * Math.cos(i * 3.14 / 180) 裡面的「+」改為「-」
另外在產生裁切多邊形時你好像多放了一段函式進去,我貼上正確的寫法給你看:
voronoi_map.selectAll “path” .data(voronoi(data).map (v) -> circle.clip d3.geom.polygon v)

這是我改過的程式碼,你可以參考看看:
https://gist.github.com/infographicstw/c10902e24dc5a60a4f31

Reply
Dan

做完交集总是有这个错误:
Uncaught TypeError: Cannot read property ‘join’ of undefined

Reply

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *