この記事はFOSS4G Advent Calendar 2014の、8日目の参加記事になります。
advent calendarには初参加なので緊張しますが、生暖かい目で見守ってください。
さて、今回のテーマですが。
openlayersとか使っててこう思うことはなかったですか。
「labelが重なってしまう！」
「popupが重なってしまう！」
狭い地域で複数選択するとごちゃごちゃと重なってしまいます。
手で調整できるのですが、できれば自動でできないだろうかと。
そんな時、天啓きました。
「openlayersで出来ないならpostgisでやればいいじゃない」
・・・ということで今回はpostgisでdivの衝突回避をしてみようと思います。
正直javascriptの物理エンジンとかD3のフォースレイアウトとか使ったほうがいいとは思うんですが、
postgisで物理演算処理が使えるのか興味があったので実験してみました。
まず手始めにdivタグの座標をpostgisに送ります。
注意点としてはtop,left,width,heightを元に5点の座標情報に変換するとこでしょうか。
postgisのpolygonは必ず閉じなければいけないので、BOXであれば最初の座標を一番最後に追加する必要があります。
[0 0,1 0,1 1,0 1,0 0]
こんな感じで。
実際にjQueryで書くとこんなかんじです。
$("div").each(function(i){
var width=$(this).width();
var height=$(this).height();
var position = $(this).position();
polygon.push({id:$(this).attr("id"),positions:position.left+" "+position.top+","+position.left+" "+(position.top+height)+","+(position.left+width)+" "+(position.top+height)+","+(position.left+width)+" "+position.top+","+position.left+" "+position.top});
});
var param={polygons:polygon};
テストで作ったDIV座標はこんな感じ。
<div id='bbox1' style="width:100px; height:100px; left:210px; top:200px;"></div>
<div id='bbox2' style="width:100px; height:100px; left:220px; top:230px;"></div>
<div id='bbox3' style="width:100px; height:100px; left:210px; top:210px;"></div>
これをラッパー用のphpに投げておきます。
// PostGISにDIV座標を送り計算します
$.ajax({
url: "collision.php",
type: "POST",
async: false,
datatype: "json",
data: param
}).done(function(response){
var data =JSON.parse(response);
//計算結果をDIVに適用します。
for(val in data){
$("#"+data[val].id).css({top:data[val].x+"px",left:data[val].y+"px"});
}
});
collision.phpの中身は殆ど何もありません。ストアドに送って返り値をjsonにしてjavascriptに返しているだけです。
<?php
// DB接続
$db = pg_connect("host=localhost dbname=postgisdb user=postgres password=postgres");
$polygons = $_POST["polygons"];
$matrix_array = array();
foreach($polygons as $val){
$matrix_array[]="['".$val["id"]."','".$val["positions"]."']";
}
$sql = "SELECT * from getNotCollisionPos(ARRAY[".implode(",",$matrix_array)."])";
$result = pg_query($sql);
$list = array();
while ($row = pg_fetch_assoc($result)) {
$list[]=$row;
}
echo json_encode($list);
// DB切断
pg_close($link);
これでpostgisにdivタグの座標が渡ります。
さていよいよ本題のpostgisですが、ここで少し中学校で習った代数幾何学が入ってきます。
ちょっと手書きでわかりづらいかもしれませんが、全体の重心からそれぞれの重心の延長上に
ある（m:n）外分点へ移動をし、移動したら衝突チェックを繰り返し、ダメだったらもう一度外分点へ移動…
という処理を繰り返す必要があると考えました（もしかしたら衝突回避のアルゴリズムとしては間違っているかも）。
この再帰処理はphp上でやると遅くなりそうなので全てストアド上の再帰処理で行うことにしました。
まずは呼び出し元の親ストアドはこんな感じになりました。
create or replace function getnotcollisionpos(text[]) returns table(id varchar, x float, y float) as $$
declare
matrix_array alias for $1;
matrix text[];
matrix_all_centroid_x float8;
matrix_all_centroid_y float8;
rec record;
rec2 record;
cu refcursor;
begin
--div計算結果テンポラリテーブル
execute 'create temporary table calc_result (id varchar(255),x float,y float);';
--div衝突計算用テンポラリテーブル
execute 'create temporary table collision (id varchar(255),geom geometry);';
--div用ポリゴン作成
foreach matrix slice 1 in array matrix_array
loop
execute 'insert into collision(id,geom) values (''' || matrix[1] || ''', ''polygon((' || matrix[2] || '))'');';
end loop;
--全divの重心取得
execute 'select st_x(geom) as matrix_centroid_x,st_y(geom) as matrix_centroid_y from (select st_centroid(st_collect(geom)) as geom from collision) as t0' into rec;
matrix_all_centroid_x:=rec.matrix_centroid_x;
matrix_all_centroid_y:=rec.matrix_centroid_y;
--各divが衝突しているかチェック
foreach matrix slice 1 in array matrix_array
loop
open cu for execute 'select id,ST_Intersects(geom,(select st_collect(geom) from collision where id<>''' || matrix[1] || ''')) as intersect from collision where id=''' || matrix[1] || '''';
loop
fetch cu into rec;
if not found then
exit;
end if;
--衝突している場合は外分線上に移動させてupdate
if rec.intersect=true then
raise notice 'matrix is intersect(getnotcollisionpos)';
perform chkcollision(matrix, matrix_all_centroid_x, matrix_all_centroid_y);
else
raise notice 'matrix is not intersect(getnotcollisionpos)';
--衝突していない場合はx,y取得
execute 'select st_xmin(geom) as x,st_ymin(geom) as y from collision where id=''' || matrix[1] || '''' into rec2;
execute 'insert into calc_result(id,x,y) values (''' || matrix[1] || ''', ''' || rec2.x || ''', ''' || rec2.y || ''');';
end if;
end loop;
close cu;
end loop;
return query select * from calc_result;
end;
$$ language 'plpgsql';
再帰処理でチェックを繰り返す子ストアドはこんな感じ。
create or replace function chkcollision(text[], float8, float8) returns boolean as $$
declare
matrix alias for $1;
matrix_all_centroid_x alias for $2;
matrix_all_centroid_y alias for $3;
matrix_centroid_x float8;
matrix_centroid_y float8;
m int:=10;
n int:=1;
target_x float8;
target_y float8;
rec record;
cu refcursor;
begin
--重心を取得
execute 'select st_x(geom) as matrix_centroid_x,st_y(geom) as matrix_centroid_y from (select st_centroid(geom) as geom from collision where id=''' || matrix[1] || ''') as t0' into rec;
matrix_centroid_x:=rec.matrix_centroid_x;
matrix_centroid_y:=rec.matrix_centroid_y;
--全divから現divの重心を元に外分線上(m:n)に移動
target_x=((-n*matrix_all_centroid_x+m*matrix_centroid_x)/(m-n))-matrix_centroid_x;
target_y=((-n*matrix_all_centroid_y+m*matrix_centroid_y)/(m-n))-matrix_centroid_y;
execute 'update collision set geom=st_translate(geom,''' || target_x || ''',''' || target_y || ''') where id=''' || matrix[1] || ''';';
--移動後に衝突しているかチェック
execute 'select id,ST_Intersects(geom,(select st_collect(geom) from collision where id<>''' || matrix[1] || ''')) as intersect from collision where id=''' || matrix[1] || '''' into rec;
if rec.intersect=true then
raise notice 'matrix is intersect(chkcollision): id:%, target_x:% target_y:%', matrix[1],target_x,target_y;
--衝突しなくなるまで再帰
perform chkcollision(matrix, matrix_all_centroid_x, matrix_all_centroid_y);
else
raise notice 'matrix is not intersect(chkcollision)';
--衝突していない場合はx,y取得
execute 'select st_xmin(geom) as x,st_ymin(geom) as y from collision where id=''' || matrix[1] || '''' into rec;
execute 'insert into calc_result(id,x,y) values (''' || matrix[1] || ''', ''' || rec.x || ''', ''' || rec.y || ''');';
return true;
end if;
return false;
end;
$$ language 'plpgsql';
注意した点としては衝突チェックをそれぞれでやるのは面倒だったのでst_collectで自分以外をマージしてST_Intersectsでbboxで重なっているか判定してます。
あと、実テーブルではなく処理速度を稼ぐためテンポラリテーブルで計算してます。
一日で作ったので多分バグがあるかもしれませんが、その辺は見逃してくださいorz
postgisで適当にポリゴン食わせると、なんかそれっぽい感じで座標を吐き出してくれました。
大体数十msecなので速度的にはそこそこいいのではないでしょうか。
IE7とかレガシー環境で動的な衝突チェックがしたいときにはこのやり方もありかもしれません。
こんな用途にpostgisを使う人はいないのでしょうけど、githubにおいておきましたので、よろしければ見てやってください。
https://github.com/makinux/postgis_chkcollision