DEIM Forum 2014 E9-1

地図オブジェクトの形状を考慮したFocus 生成システムの実現
加藤 史也†

山本 大介†

高橋 直久†† 名古屋工業大学大学院 工学研究科 情報工学専攻 〒 466-8555 愛知県名古屋市昭和区御器所町
E-mail: †fumiya@moss.elcom.nitech.ac.jp, ††{yamamoto.daisuke,naohisa}@nitech.ac.jp
あらまし Focus ＋ Glue ＋ Context マップは，大縮尺の注目領域 (Focus)，小縮尺の周辺領域 (Context)，および，縮尺差により生じる歪みを吸収して両者を結ぶ領域（Glue) からなる．一般に，公園，神社，商店街など，ユーザが注目する地図上の区域 (地図オブジェクトと呼ぶ) は，様々な形状であるが，これまで，Focus の形状は，円形や矩形など一部の形状に限られていた．任意形状の Focus を描画しようとすると，事物の位置関係が損なわれたマップになることがある．本稿では，配置関数を用いて正しく Focus+Glue+Context マップを作成するためには，Focus の形状が準凸多角形でなければならないことを提示する．また，ユーザにより指定された地図オブジェクトに適合した準凸多角形の Focus を生成するアルゴリズムについて述べる．さらに，提案アルゴリズムを実装した準凸多角形 Focus 生成システムのプロトタイプを用いて，準凸多角形 Focus の有用性を評価する．
キーワード

Web マップ，Focus+Glue+Context マップ，幾何学

1. は じ め に
近年，GoogleMaps などの Web マップサービス [1-3] が普及している．しかし，多くの Web マップサービスでは地図を拡大する場合，表示している地図全体に対し，スケール (縮尺) の変更を行う．また，複数の離れた場所を比較したい場合，小縮尺の地図を用いて位置関係を把握しつつ，大縮尺の地図で閲覧する必要がある．これらには「地図の縮尺を変更する」、「地図をスクロールさせ表示領域を変更する」等の操作を複数行わなければならない問題がある．この問題を解決するために我々はFocus+Glue+Context マップ EMMA[4-9] を提案してきた．
EMMA は，大縮尺で詳細に描画した注目領域 (Focus)，小縮尺で広域を描画した周辺領域 (Context)，両者を結ぶ歪みのある領域 (Glue) からなる．公園や神社などの施設を含む区域を Focus 内に描画すると，利用者は他の区域との位置関係を広域マップで確認しながら，その区域の詳細を調べることができるようになる．しかし，Focus は Context よりも縮尺が大きいため，同じ描画面積では地理的に狭い区域の領域となる．

図 1 Focus+Glue+Context マップの例とがある．その例を図 2 に示す．図 2 では図の右下の Focus とGlue を通る道路や線路が繋がっていないのがわかる．従来，この問題の原因が明確ではなかったため，これを回避するために

EMMA では凸多角形 Focus を用いてきた．本論文では，上記問題の原因を究明し，その問題を解決するため，準凸多角形のFocus を生成するシステムを提案する．

Focus の面積を増やすと本来 Context に歪みなく描画される広い区域を，Glue に圧縮，歪ませて描画することになる．Glueは Focus と Context を横断する道路を繋ぐことを主目的としている．Glue で表示すべき道路が増えると圧縮によって，道路の繋がりが見難くなる．注目区域周辺の視認性を向上させるためには Focus をできるだけ小さくする必要がある．一方，EMMA では，道路や施設などの地図オブジェクトの描画において，原点 (不動点) からの距離に応じ，地理上の各地点をマップ上のどの位置に配置するかを定めた配置関数を用いている．
これは Focus+Glue+Context マップを比較的簡単で高速に描画可能にしているが，Focus の形状次第では，マップ上で地図オブジェクトの連続性が損なわれるなど異常描画が発生するこ

図 2 道路の継続が破たんしている Focus

が行われる．また，Context 内の傾き sc は sc = 1(図 5(b)A よ2. Focus+Glue+Context マップにおける Focus 生成機能り外の範囲）である．このとき，Context は拡大前の地図から

この章では従来の Focus+Glue+Context マップについて説い地図になる．そして，拡大範囲の領域を sf 倍に拡大して割明し，その問題点についてまとめる．

Focus と Glue の領域を取り除いた領域で同じ縮尺の歪みのな付範囲に配置した歪のない地図になる．一般に地図を拡大する

2. 1 Focus+Glue+Context マップ

際に，すべての地図オブジェクトの点に対して配置関数によりFocus+Glue+Context マップとはスケールの異なる地図を位置を計算して再描画すると多大な時間を要する．しかし，こ同一画面上に同時に表示する Web マップである．Context はのような配置関数を用いることにより Focus と Context におスケールの小さい地図を表示する．Focus は多角形で表現され，いては縮尺が一定になるため，それぞれの縮尺に応じたラスタその多角形内部に含まれる地図領域を Context よりもスケール画像の地図を用いることができる．よって配置関数で計算するを拡大して描画する．Glue は Focus と Context のスケール差のは Glue の地図オブジェクトのみとなり，応答性の良い Webによる歪みを吸収する．Glue は Focus と Context を通る道路マップシステムを実現できるようになる．

を連続させる役割を持つ．
多くの Web マップサービスではスケールを拡大すると閲覧可能な地図領域が狭くなってしまう．すなわち，ブラウザやモニター等の表示範囲外へ多くの地図領域が追いやられてしまう問題点がある (図 3(a))．一方，Focus+Glue+Context マップは拡大したい領域を Focus 内部に拡大して表示することが出来る．この際，Context に表示された閲覧可能な地図領域の範囲は保たれる．よって，Focus の生成前後で閲覧可能な地図領域が減らない利点がある (図 3(b))．
図4

glue領域
拡大範囲
割付範囲

拡大範囲と割付範囲

移動対象の座標点
ＢＣ

不動点Ａr’直線 ベジェ曲線
部分 部分
関数範囲外
r=r’直線ＢＣ(a)

Ａr(b)

図5

配置関数形状の決定

図 3 Focus+Glue+Context マップの例

2. 3 Focus の生成における問題点
2. 2 Focus の生成方法

Focus の生成における問題点について述べる．前節で述べた

Focus+Glue+Context マップの Focus と Glue の生成法につように，Context において拡大範囲にある地図が割付範囲の大いて述べる．ユーザが，図 4（a) のように，地図（Context）上きさになるように，拡大範囲の全ての点に対して不動点からので拡大すべき領域（拡大範囲という）を指定すると，図 4(b) の距離を均一倍率で拡大することにより Focus を生成する．

ように，その領域を大縮尺で描画した地図（Focus）を Context

不動点には「拡大範囲内部の観測点であること」という条件上に配置する（配置した領域を割付範囲という)．EMMA では，が存在する．観測点とは多角形内部の全ての点が見える点であ配置関数と呼ばれる関数を用いている．配置関数とは Focus とる [10]．観測点でない点を不動点とした場合，不動点から引いGlue を生成する際に用いられ，配置関数とは Focus 内部のあた直線が Focus，Glue，Context の順で通らない箇所があり，る点 (不動点という) から引かれた角度が同じ直線上の全ての配置関数による点の移動が正しく行われず，道路が途切れる等点に対し，移動方法を決める関数である．配置関数は不動点 Oのマップが破たんしてしまう可能性がある．本稿では多角形内を原点としている．図 5(a) には一番内側の円の範囲 C が拡大部に存在する観測点の集合体を観測点領域と呼ぶ．また，多角範囲，1 つ外側の円の範囲 B が割付範囲となっている．範囲 C形内部にいくつかの観測点を持つ多角形を準凸多角形と呼び，内の全ての点を範囲 B へ移動させる配置関数の形状が 5(b) の内部全ての点が観測点である多角形を凸多角形という．そして，

r′ = f (r) である．配置関数上で範囲 C 内の傾き sf は sf = 一定値 >1 となっており，これにより点同士の間隔が広がり拡大

多角形内部に観測点を持たない多角形を非準凸多角形と呼ぶ．
凸多角形，準凸多角形，非準凸多角形の例を図 6 に示す．観測点を多角形内部から導出するような問題として他に図書館問3. 2 準凸多角形 Focus
準凸多角形 Focus とは凹角の存在する多角形を拡大範囲とし題 [11] がある．

た Focus である．従来システムでは拡大範囲の形状を考慮せずに不動点の座標を決めていた．しかし，この方法で準凸多角形

Focus を生成すると，観測点ではない点を不動点としてしまう可能性がある．その場合，マップを正しく生成できない．

4. 提案システムの実現法
図6多角形の例

4. 1 準凸多角形 Focus 生成のアルゴリズム
準凸多角形 Focus を生成するには拡大範囲の形状を調べ，観2. 4 既存の EMMA の問題点と解決策

測点領域が存在するか確認する必要がある．凹多角形における既存の EMMA(以後，「従来システム」という) では任意の凸観測点領域とは，凹角を構成する辺を多角形内部へ延長するこ多角形の Focus を生成することが可能である．しかし，地図とで出来る多角形である．凹角が複数ある場合はそれぞれ辺をオブジェクトの形状は必ずしも凸多角形で表現されるとは限ら延長してできた多角形のオーバーラップ領域 (積領域) となる．

ない．このため，凸多角形では余剰領域 (拡大したい地図オブ

図 8 に観測点領域の例を示す．

ジェクト以外の Focus 内の領域) が大きく発生する場合があった．余剰領域を減らすためには，凹角を含む多角形を Focus として生成する必要がある．そこで本研究では，凹角を含む多角形の Focus を生成する機能を考案する．例えば，図 7(b) のよ
うな Focus を生成する．準凸多角形を拡大範囲とすることで敷地面積にあわせた Focus が可能となり，Focus 内の余剰領域を出来るだけ少なくできる．図 7(a) では Glue 内部で表示されて図8いる名古屋駅が図 7(b) では Context で歪まずに表示されてい観測点領域の例

る．これは Focus の面積が減ったことで地図が見やすくなっていると言える．

4. 2 観測点領域の導出
変形アルゴリズムの入出力は以下の通りである．
入力

拡大範囲の頂点座標

出力

変形後の頂点配列座標，不動点座標

アルゴリズムの説明において，次の用語を以下の様に定義し使用する．
凹角を埋める凹角の面積

頂点を 1 つなくし凹角を 1 つ減らすこと凹角を埋めたことで凹多角形の面積が増加した

領域
入力の拡大範囲が凹多角形である時，後述する変形アルゴリズ
図 7 Focus の形状によって起きる問題

ムを用いることで準凸多角形へ変形させる．変形後，観測点領域内部より不動点の導出を行う．

3. 提案システム

変形には再帰を用いる．まず，多角形に存在する凹角の数を長さとした要素が全て 1 のビットベクター V を用意する．1 番

この章では提案システムについて述べる．

目の要素は多角形の 1 番目の凹角と対応している．再帰を 1 回

3. 1 提案システムが有する機能行うたびに V の 1 の要素を先頭から 1 つずつ 0 にしていく．0

本稿では任意形状多角形の入力に対し Focus 生成機能を有すにした要素に対応する凹角を埋める変形を行い，変形後の多角る Focus+Glue+Context マップを提案する．提案システムは形内部に観測点領域が求められればそこで再帰を抜け，V を返以下の 3 つの機能から成る．

す．求められなければもう 1 つ 1 を 0 に変えた V に対し，再帰機能 1 拡大範囲の形状を識別し，観測点領域を導出を行う．これを観測点領域が求められるまで，または多角形内機能 2 凹多角形を準凸多角形へ変形

部に存在する凹角が 1 つになるまで繰り返す (凹角が 1 つの多機能 3 観測点領域内部から不動点の座標を決定

角形は必ず準凸多角形となるため)．最後に再帰後の V に従い，まず，入力の拡大範囲内部に観測点領域が存在するか調査す

V 内の 1 となっている箇所に対応した凹角は残し，0 となってる．そして必要に応じて変形を行った後，観測点領域内部よりいる箇所に対応した凹角を埋めることで多角形の変形を行う．

不動点を導出し Focus の生成を行う．

もし，変形の仕方が複数ある場合は，「埋める凹角の面積の総和が最も少ない」変形を採用する．

Algorithm 1 凹多角形変形アルゴリズム
k：凹角の数V ：埋める凹角を 0，残す凹角を 1 とした長さ k のビットベクタ−
S ：凹角の面積
P ：V の 1 の凹角による観測点領域の頂点配列
comp(k, V, S)｛
P = opa(k, V )if P ! = Ø or k == 1 thenreturn Velse
for i = 0 to k − 1 do
j = f ind − ith − one(V, i)for h = 0 to k − 1 doif h == j then

図 9 変形アルゴリズムの再帰

Wi [h] = 0else

変形アルゴリズムの簡単な変形例を図 9(a) の凹多角形を用

Wi [h] = V [h]いて以下に述べる．図 9(a) の凹多角形には 2 つの凹角が存在

end ifする．これを図の様に左側の凹角を凹角 1，右側の凹角を凹角

end for2 とする．

Vk−1 [i] = comp(k − 1, Wi , S)
X[i] = area(S, Vk−1 )まず，V を用意する．図 9(a) では V[11] となる．V の 1 つ目の要素は凹角 1 に，2 つ目の要素は凹角 2 を示す．次に V の要

end forend if

素を 1 つだけ 0 にしたものを全て用意する．図 9(a) では V のj = min(X[i])長さが 2 なので V1 [10](図 9(b)) と V2 [01](図 9(c)) となる．そreturn (Vk−1 [j])して，それぞれのビットベクターで 0 となった要素に対応する｝

凹角を埋めるよう多角形の変形を行う．図 9(b) では V1 [10] なので凹角 2 を埋めた変形を行っている．変形した多角形に対し，観測点領域を求める．図 9(b)，図 9(c) はどちらの図形も観測点領域が導出可能である．ここで先述したように「埋める凹角の面積の総和が最も少ない」変形を採用する．よって図 9 の場合では，面積が小さい凹角 1 を埋め，凹角 2 を残す．したがって図 9(a) の多角形に提案する変形アルゴリズムを用いると図9(c) のような変形が行われる．
Algorithm1 に第 5 章で述べるプロトタイプに実装した変形アルゴリズムを示す．

5. プロトタイプシステムこの章では第 4 章のアルゴリズムを実装したプロトタイプシステムについて述べる．プロトタイプシステムの作成にはAction Script [12] [13] を用いた．またプロトタイプシステムは以下の目的を満たすために作成した．

•

準凸多角形に対し，観測点領域を求め，Focus が正しく

図 10 機能の流れ生成できるか確認する•

非準凸多角形を準凸多角形へ変形するアルゴリズムが正しく行えるか確認する•

従来システムの円形や矩形 Focus 及び Glue と提案シス

テムによる Focus，Glue の双方に対し評価実験を行う
入力から出力までのプロトタイプシステムの機能の流れを図 10 に示す。入力は拡大範囲の全頂点座標であり，出力として Focus と Glue が生成される．この EMMA システムには縮尺の違う地図が 15 種類用意されている。システムを起動すると、7 万分の 1 の地図が Context 領域として表示される．拡
大範囲の全頂点座標を入力すると第 4 章で述べたアルゴリズムにより不動点の座標が求まる．その後，求めた不動点を原点とした配置関数により割付範囲の Focus と Glue の生成を行う．Focus 内部の縮尺は Context よりも 1 段階拡大されたものが用いられる．出力として生成された Focus，Glue による

Focus+Glue+Context マップが表示される．
図 11 に プ ロ ト タ イ プ シ ス テ ム に よって 生 成 さ れ た Fo-

cus+Glue+Context マップを載せる．

角形を用いて注目したい施設のみを Focus に出来るためである．
ここで，Glue，Context は Focus よりも縮尺が小さいため，同じ面積の図形内部において，表示されている地図領域が広がっていると言える．そこで，円形，正方形で表示可能な領域を 1とし，準凸多角形 Focus を用いたときの表示可能な領域の比率を求める．比率を求めるための各面積を図 12 に示す．図 12 のA は「準凸多角形 Focus の拡大範囲の面積」，B は「準凸多角形 Focus と従来システムの割付範囲の面積の差」，C は「従来システムの拡大範囲の面積」である．図 12 の A，B，C の値を用いると 表示可能領域の比率 = (A + B)/C となる．

図 11

準凸多角形 Focus
図 12

図 11 において，Focus の割付範囲は黒線で囲まれた準凸多角形である．準凸多角形 Focus を用いることにより，拡大したい建物の敷地の輪郭に合わせた Focus，拡大したい領域のみをピンポイントに指定した Focus の生成が可能になった．図 11
より Focus と Glue，Glue と Context のそれぞれの境界線付近において道が途切れずに繋がっていることがわかる．

6. 評 価 実 験
この章では第 5 章で述べたプロトタイプシステムを用いて提案システムの準凸多角形 Focus を評価し，その結果について述べる．

6. 1 目的と実験方法
準凸多角形 Focus の有効性を示すため，また，提案システムによる Focus+Glue+Context マップの道が空間的に接続されているか確認するため評価実験を行う．比較するシステム，評価する項目を以下に記す．
比較するシステム•

S1:円形 Focus 生成システム (従来システム [5])•S2:正方形 Focus 生成システム ( [5])•S3:準凸多角形 Focus 生成システム (提案システム)

既存システムの円形，矩形 Focus と提案システムの準凸多角形

Focus に対し，評価実験として以下の項目を評価する．
評価項目•

Glue を描写する時間•

割付範囲の面積•

表示可能領域の比率•

道の断裂の有無の確認 (提案方式のみ)

評価項目の「表示可能領域の比率」とは，「円形，正方形の割付範囲の中での表示可能な地図領域の比率」である．従来シ
ステムにおける円形，正方形 Focus の各図形の面積を，提案システムと比較すると提案システムでは円形，正方形の内部にGlue，Context 領域が存在する．これは提案システムが準凸多視認可能領域を求める各面積

6. 2 実 験 結 果
評価実験の結果を表 1 に示す．表 1 の項目は，左から対象物の名称，円形 Focus，正方形 Focus，準凸多角形 Focus である．
また，比率の項目は前節で述べた表示可能領域であり，円形，正方形の面積に対し，準凸多角形 Focus を用いた場合に表示可能領域がどれだけ増えたかを示している．

6. 3 考察

実験結果より全ての評価対象において準凸多角形 Focus の方が円形，正方形 Focus に比べて面積が小さくなった．図 13 の荒子川公園の様に，敷地の形状が細長い矩形だったり敷地の一部が突出している形状では円形，正方形 Focus を用いると敷地以外の領域も拡大範囲に含んでしまい，Focus の面積が大きくなる．そのため，円形，正方形 Focus の面積と準凸多角形 Focusの面積の差の割合は評価対象毎に差が出ている．円形，正方形Focus 内部の拡大したい領域以外の面積が大きいほど，表示可能領域が増えるので面積の差の割合が大きい評価対象ほど表示可能領域が増えている．表示可能領域は円形 Focus の場合は平均 2.24 倍，正方形 Focus の場合は平均 2.08 倍増えた．また，Glue が生成されるまでの時間は，面積の大きい公園では従来システムの方が早かった．しかし，面積の小さい公園では差はあまり見られなかった．これは準凸多角形 Focus は円形，正方形よりも Focus，Glue 生成のための計算量が多く，その計算量が面積に依存しているからである．最後に提案システムで生成したマップにおいて，今回の実験箇所では道路の断裂は見られず，マップが正しく生成されていることを確認した．

7. お わ り に本研究では，任意形状の入力に対し Focus の生成方法を提案した．既存の EMMA システムにおける Focus+Glue+Context
マップの生成法を解析し、Focus，Glue の生成における問題点を提起した．不動点，配置関数をそれぞれ 1 つのみ用いて準凸表1システム

よる準凸多角形 Focus と既存の円形，正方形の Focus を比較

実験結果

S1S2S3する評価実験を行い，提案システムが Focus+Glue+Context

形状

円形

正方形

準凸多角形

マップを表示するのにかかる時間の従来システムとの差が大き

平和公園 時間

266286

325

名称

くないこと，Focus の面積が減ったことによりマップ全体が見面積160549 141266

比率1.861.69-

東山公園 時間

193194252

今後の課題として，変形アルゴリズムの最適化や変形を行

72970

わずに Focus を生成するような配置関数の提案，準凸多角形

97149やすくなったことを示した．

面積133787 103788

比率

1.99

1.65-

Focus の自動生成システムの開発がある．本稿で提案した変形

大高緑地 時間

182161317

アルゴリズムは埋める凹角を面積で決めており，観測点領域を面積

104891

97199

64951

導出するのに必要のない凹角を埋めてしまう可能性があり，改比率

1.83

1.73-

善の余地がある．また，今回実装したプロトタイプシステムで名古屋城 時間

197

168258

面積72763

52272

26725

比率

2.362.06-

荒子川公園 時間

161

141

133

手し，それらの面積を内包する多角形を拡大範囲とした Focus

面積6542343199

9704を自動生成する方法の検討が挙げられる．

比率2.822.66-

庄内緑地公園 時間

164

161

204

面積

55145

49923

23016

比率

2.252.17-

瑞穂運動場 時間

186

187

147

面積

44263

38988

11906

比率

2.55

2.47-

日光川公園 時間

131

101

122

面積

24419

14700

5625

比率

2.652.33-

鶴舞公園 時間

100

132

151

面積

18786

17328

11925

比率

1.80

1.69-

熱田神宮 時間

97106

140

面積

24419

24300

10187

比率

2.33

2.33

-

は Focus の拡大範囲の入力をマウスを用いた手作業で行っているので，GPS データや公園の敷地をデータベース [14] から入文
[1]
[2]
[3]
[4]

[5]

[6]

[7]

[8]

[9]

[10]

図 13

準凸多角形 Focus が有効な形状

多角形 Focus とその Focus に対する Glue を生成するための不[11]
[12]
[13]

動点座標の新たな導出法を提案した．非準凸多角形の入力に対し，準凸多角形へ変形するアルゴリズムを提案し，そのプロトタイプシステムを実装した．実装したプロトタイプシステムに

[14]

献

GoogleMaps， http://maps.google.co.jp
AlpsMAP， http://alpsmap.yahoo.co.jp
Yahoo!地図，http://map.yahoo.co.jp
Naohisa Takahashi: An Elastic Map System with Cognitive
Map-based Operations, International Perspectives on Mapsand the Internet, Springer-Verlag, pp.73-87, Feb. 12, 2008．
Daisuke Yamamoto, Shotaro Ozeki, Naohisa Takahashi, Focus+Glue+Context: An Im-proved Fisheye Approach for
Web Map Services, Proceedings of the ACM SIGSPATIALGIS 2009, Seattle, Washington, pp.101-110, 2009.11
H. Mizutani, D. Yamamoto, and N. Takahashi, ”A Fusionof Multiple Focuses on a Focus+Glue+Context Map”, Proceedings of the International Conference on Intelligent Interactive Multimedia Systems and Services (IIMSS 2012),
pp.11-21, 2012.5.
小関章太郎，高橋直久:focus+glue+context マップの glue 領域
における道路ネットワーク総描法，第 6 回情報科学技術フォー
ラム講演論文集，D-025(2007)
水谷祐弥，山本大介，高橋直久，Focus+Glue+Context マッ
プにおける Focus 変形・結合・分裂手法， 第 3 回データ工学と情報マネジメントに関するフォーラム（DEIM2011), B4-4,2011.02.
加藤史也, 山本大介, 高橋直久, 任意形状 Focus 生成機能を有す
る Focus+Glue+Context マップシステムの実現, 電子情報通信学会, データ工学研究会 (DE), 情報処理学会, 第 156 回データベースシステム研究会 (DBS),2012.3
Michael Worboys,Matt Duckham,Chapter3,Fundamental
spticial concepts,GIS:A COMPUTING PERSPECTIVE,CRC
PRESS,2004
譚 学厚 · 平田 富夫，計算幾何学入門
大重美幸，Adobe Flash CS3 詳細!ActionScript3.0 入門ノート，森北出版，2001
ActionScript3.0 コンポーネントリファレンスガイド
http://livedocs.adobe.com/flash/9.0_jp/
ActionScriptLangRefV3/
樋川貴一，山本大介，片山喜章，高橋直久，”XML を用いた
WEB サービス用施設領域 DB サーバの構築”，情報処理学会第74 回全国大会，1P-7，2012/3.