❄️

【特別編;ネットワークボロノイ分割】GISを作るデータ構造とアルゴリズム【計算幾何学】

に公開

概要

前回の記事では, GISの基本機能のひとつ, ボロノイ分割を説明した.
ボロノイ分割は, ボロノイサイトと呼ばれる複数の点を中心とした領域を求めることを目的に, 他の点と均等距離を保った領域に分割する処理であった. その効率的なアルゴリズムとしてFortuneのアルゴリズムを紹介した.

実はこのボロノイ分割にはさまざまな亜種が存在している. そのなかでも, 「コンピュータ・ジオメトリ 第3版 計算幾何学:アルゴリズムと応用」にも言及されていないネットワークボロノイ分割について説明する.

今回は特別編ということで, 説明も簡単にして記事を終わらせたいと思う.

ネットワークボロノイ図とは

まずはネットワークボロノイ分割,もとい,ネットワークボロノイ図とは何か,説明する.
”ネットワーク”と言葉が付いているように, 与えられたノード集合に対してグラフ上のノード集合やエッジ集合を,エッジコスト(距離コストや移動コストなど)に応じて分割する方法である.

『Spatial Tessellations: Concepts and Applications of Voronoi Diagrams』, Okabe et al., Wiley, 2000, にて紹介されている.

通常のボロノイ分割が2点間のユークリッド距離(直線距離)を均等するように領域を分割していたのに対し, ネットワークボロノイ分割では, グラフネットワーク上でのある2つのノードを結ぶエッジ群を,例えば均等に分割する方法である.

それゆえ, ネットワークボロノイ分割では, ノード間の直線距離ではなく, それらを結ぶエッジの長さに基づいて分割されるという制約がかかる.

ユースケースとしては, 道路やその周辺における地形の制約を考慮した道路網上の特定地点からの勢力関係を得ることができる.例えば,通学の距離を考慮した学区の決定,消防署の管轄範囲,店舗の商圏問題など, 移動コストが主にネットワーク構造(例:道路)に支配されるケースに向いている.

上図にネットワークボロノイ分割のイメージをおいた. ネットワーク構造に対し, 領域の中心となるノード(ここではサイト)を指定すると, エッジのコストを考慮してネットワークを分割する. このとき,他の領域との境界点がどこかのエッジ上で現れることがある, というのが特徴だ.

この境界点を基準に,各エッジがどの中心ノードの勢力下にあるのか識別することができる.

アルゴリズム

このネットワークボロノイ分割の仕方について考えよう.
ここでは以下の論文に載っている擬似コードを参照して説明する. (例もトレースして使わせてもらった).
https://kansai-u.repo.nii.ac.jp/records/11026

ここでは具体例をもちいて処理の流れを確認する. そのため, 擬似コードそのものは論文を参照してほしい.


上記のようなネットワーク図およびエッジコストが与えられた場合を想定する. いま, 大きな円が各領域の母点ノードとする. 他のノードおよびエッジがどの母点ノードに所属するのか,色分けしていく.

最初のステップは, 母点ノード間の最短経路および最小経路コストを求めること. (下図の緑線)

なぜ最短経路を求めるかというと,

  1. 最低限, この経路上のちょうど真ん中には母点ノード間の境界点があるため
  2. 母点ノードを出発してこの最小経路コスト範囲内のノードおよびエッジの部分はこの母点ノードの領域になる

という2点がわかるからだ.

まず1.について, 以下のように境界点を母点ノード間の最短経路上の中点に設ける.(下図)

この段階で, 到達したノードについては, 対象の母点ノードの色をつけておく.

つぎに, 2.に関して, 各母点ノードから,この最小経路コスト範囲内のノードおよびエッジの部分を色づけしておく(下図, 今回の例では5 コストまで移動)

この状態になれば, 残りのノードおよびエッジに色をつけていく. ここで3つのパターンに分かれる.

  1. 色が完全に定まっていないエッジの両端ノードがすでに同色で色付けされている (下図 赤枠)
  2. 色が完全に定まっていないエッジの両端ノードが異なる色で色付けされている(下図 青枠)
  3. 色が完全に定まっていないエッジの両端ノードのうち少なくとも片方がまだ色付けされていない(下図 緑枠)

1-3の場合で対処が異なる.
1の場合, 同色ノードに囲まれたエッジは同じ母点ノードの領域に含まれるので両端ノードの母点ノードの色にする
2の場合, 色がついていないエッジ部分をちょうどに分割して領域をわける.
3の場合, 色がついていないエッジ部分だけでもう一度最短経路をもとめ, その中間点を求める. (その後, また1-3を再帰的に繰り返す)

これらの処理をすると,全てのノードおよびエッジが何かの色がつき,そして, 境界点もすべて見つかるはずである.

実装例

論文内の疑似コードをPythonで再現したものを挙げておく.
ネットワーク構造を作成するときの読み取りファイルのデータ構造等は自身の状況に合わせて欲しい.

# ネットワーク構造
def network_input(file_name):
    E         = np.empty(vmaxsize+1,np.int)
    length    = np.empty((vmaxsize+1,vmaxsize+1))
    dist      = np.empty((vmaxsize+1,vmaxsize+1))
    p_b_dist  = np.empty((vmaxsize+1,vmaxsize+1))
    path      = np.empty((vmaxsize+1,vmaxsize+1))
    n,m       = 0, 0
    G         = nx.Graph()  # 無向グラフ
    pos       = {}

    print("入力するデータは無向ネットワークのデータです\n")
    print("ファイルからグラフ構造を取得してます")
    with open(file_name) as f:
        reader = csv.reader(f)
        header = next(reader)
        n      = int(header[1])
        G.add_nodes_from([int(i) for i in range(1,n+1)])
        m      = int(header[2])
    for i in range(1, n+1):
        for j in range(1,n+1):
            length[i][j] = maxvalue
            path[i][j] = undefined
            path_matrix[i][j] = undefined
        length[i][i] = 0
        path[i][i] = root
        path_matrix[i][i] = root

    print("m本の各辺の始点と終点および長さを入力してください\n")
    count = 0
    adjust = [[] for _ in range(n+1)]              # お隣のリスト:adjust[i]は頂点iに接続する隣のノードIDが格納
    with open(file_name) as f:
        reader = csv.reader(f)
        header = next(reader)
        for row in reader:
            count += 1
            i = int(row[1])
            pos[i] = (float(row[2]),float(row[3]))        
            j = int(row[4])
            pos[j] = (float(row[5]),float(row[6]))
            d = float(row[7])
            E[count*2-1] = i
            E[count*2] = j
            # print(i,j,d)
            G.add_edge(i, j)
            length[i][j] = d
            length[j][i] = d
            path[i][j] = i
            path[j][i] = j
            adjust[i].append(j)
            adjust[j].append(i)
    if count == m:
        print("サイズ整合性とれてる")
    return n,m,length,path,G,pos,adjust,E,dist,p_b_dist

# アルゴリズム1
def init(n,m, K):
    V       = [-1]*(n+1)                        # v[p]:点pの母点となる頂点配列 
    D       = [maxvalue]*(n+1)                   # D[p]:pからV[p]までの移動コスト
    P       = [-1]*(n+1)                          # P[p]:pからV[p]にまで向かう経路の、pの次の点
    M       = [False]*(n+1)                       # M[p]:pの母点pが確定したかどうか
    eV      = [-1]*(m+1)                      # eV[b]:エッジbの所属先の母点
    next_h  = []                    
    next_Dh = []
    for p in range(1,n+1):
        if p in K:
            V[p] = p
            D[p] = 0
            P[p] = 0
            M[p] = True
            next_h = np.append(next_h,p)
            next_Dh = np.append(next_Dh,D[p])
    return V,D,P,M,eV,next_h,next_Dh

# アルゴリズム2
def expand_childnode(p,V,D,P,M,next_h,next_Dh,dist,adjust):
    print("頂点{}の隣接群は{}".format(p,adjust[p]))
    for w in adjust[p]:
        print("頂点{}の隣接点{}について".format(p,w))
        if M[w] == False:
            print("隣接点{}は母点が不在".format(w))
            delta = D[p] + dist[p][w]
            if D[w] >= maxvalue:
                V[w] = V[p] # wの母点はpの母点と同じになる
                D[w] = delta # wの母点とpの母点は同じなので、V(w)<->w間のコスト、つまりD(w)はdeltaとなる
                P[w] = p # wからV(w)に向かう経路で、wの次の点はp
                next_h = np.append(next_h,w)
                next_Dh = np.append(next_Dh,D[w])
            elif delta < D[w] < maxvalue: # どこかの母点に含まれているが、もっと距離の小さいのが見つかった
                V[w] = V[p]
                D[w] = delta
                P[w] = p
                delete_index = np.where(next_h == w)[0]
                nnext_h = np.delete(next_h,delete_index[0])
                nnext_Dh = np.delete(next_Dh,delete_index[0])
                next_h = np.append(nnext_h,w)
                next_Dh = np.append(nnext_Dh,D[w])
    return  V,D,P,M,next_h,next_Dh

# アルゴリズム4
def edge_network(n,m,E,V,eV,dist,p_b_dist,length,G,pos):
    edge_b = 0
    for e in range(1,m+1):
        p1 = E[2*e -1]
        p2 = E[2*e]
        if V[p1] == V[p2]:
            print("一致した! ")
            eV[e] = V[p1]
        else:
            edge_b += 1
            p_b_dist[p1][edge_b] = (dist[V[p1]][p1]+dist[V[p2]][p2] + length[p1][p2])/2
            rw                   = (p_b_dist[p1][edge_b] - dist[V[p1]][p1])/length[p1][p2]
            pos[n + edge_b]      = ((pos[p2][0] - pos[p1][0])*rw+pos[p1][0],(pos[p2][1] - pos[p1][1])*rw+pos[p1][1])
            G.remove_edge(p1,p2)
            G.add_edges_from([(p1,n+edge_b),(n+edge_b,p2)])

    return edge_b,p_b_dist,eV,pos,G
main.py
import numpy as np
import csv
import networkx as nx
import matplotlib.pyplot as plt
import time

vmaxsize  = 10000
maxvalue  = 100000000
root      = 0
undefined  = -1 

path_matrix = np.empty((vmaxsize+1,vmaxsize+1))

n,m, length,path,G,pos,adjust,E,dist,p_b_dist= network_input("ファイル名")

K = [17, 78, 52, 100, 130]
print("頂点{},辺数{}のネットワークを構築します。".format(n,m))

# エッジコストのマトリックス [n,n]
for i in range(1, n+1):
    for j in range(1,n+1):
        dist[i][j] = length[i][j]
V,D,P,M,eV,next_h,next_Dh = init(n,m,K)
print("/////全点間最短経路探索中/////")

# ワーシャルフロイド
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1,n+1):
            print(k,i,j)
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                # path[i][j] = path[k][j]
print("/////全点間最短経路探索終了/////")

# アルゴリズム3
while len(next_h) > 0:
    sorted_h = next_h[np.argsort(next_Dh)]
    print("next_h:{}".format(next_h))
    print("next_Dh:{}".format(next_Dh))
    p = int(sorted_h[0]) # 最小コストのノードID
    delete_index = np.where(next_h == p)[0]
    print("消されるのは{}番目".format(delete_index[0]))
    nnext_h = np.delete(next_h,delete_index[0])
    nnext_Dh = np.delete(next_Dh,delete_index[0])
    M[p] = True
    V,D,P,M,next_h,next_Dh = expand_childnode(p,V,D,P,M,nnext_h,nnext_Dh,dist,adjust)

edge_b,p_b_dist,eV,pos,G = edge_network(n,m,E,V,eV,dist,p_b_dist,length,G,pos)
print("取り合ってるエッジ数は{}箇所\n".format(edge_b))
print(eV)

# 可視化
node_colors = ["black"]*(n+1)
colorlists = ["lightblue","coral","lime","plum","lightpink","red","blue","yellow","brown","purple"]
np_v = np.array(V)
for index,k in enumerate(K):
    color_index = np.where(np_v == k)[0]
    for i in color_index:
        node_colors[i] = colorlists[index]
    node_colors[k] = "black"
nx.draw_networkx(G, pos,font_size = 10,node_color=node_colors[1:],with_labels = False,node_size=50,
                    nodelist = [i for i in G.nodes if 1 <= i <= n])
nx.draw_networkx(G, pos,font_size = 0,node_size=20, node_color='b', alpha=0.7, node_shape='d',
                    nodelist = [i for i in G.nodes if n+1 <= i],width=3)
plt.axis('off')
plt.show()

途中全頂点間の最短経路を求めている. ここではワーシャルフロイド法を使用しているが,めちゃくちゃ遅いので, 必要に応じて軽量化すると実用的になると思う. (numbaを使うと)

https://qiita.com/rp523/items/8fba3882c4a6ea203757

まとめ

今回はボロノイ分割の変わり種, ネットワークボロノイ分割を紹介した.
通常のボロノイ分割が2点間のユークリッド距離(直線距離)を均等するように領域を分割するのに対し, ネットワークボロノイ分割では, グラフネットワーク上でのある2つのノードを結ぶエッジ群をそのエッジコストに応じて分割する方法である.

ネットワークボロノイ分割について言及する記事は極端に少ない. 誰かの参考になれば幸いである.

Discussion