地図上のある地点が領域内含まれるかの判定

8,292 views
Skip to first unread message

YON

unread,
Jul 1, 2009, 5:22:07 AM7/1/09
to Google-Maps-API-Japan
今日は、
地図上のあるポイントが特定の領域内に含まれるが否かを調べる方法をネットで検索したところ、以下の資料を見つけました。
「領域内外判定方法」
http://www.j-tokkyo.com/1999/G06T/JP11144041.shtml
上のページでは、プログラムコードまで参照できませんが、使用したい理論は

「点p=(Xp,Yp)と、多角形の頂点qi=(Xi,Yi)が与えられた時、
 多角形の各辺について、M1=(Xp- Xi)(Xp-Xi+1)を計算して
 これが負である場合のみ、
  M2=(Xp-Xi){(Xp-Xi)(Yi+1-Yi)-(Yp-Yi)(Xi+1-Xi)}を求めて
 その符号( M2<0のとき1、M2>0のとき0)の和を求め、
 これが偶数であるとき、与えられた点pは多角形で囲まれる領域の外部にあり、
 奇数であるときには内部にあると判定する」

です。上は特許のようですが、商用利用はしないので、この理論を元に、javascriptでコーディングして、googleマップ上のある
Glatlng地点がGpolygon領域内にあるかを判定する関数を作ってみました。もっとも、この理論は2次元平面座標系の理論だから、地球面上の
地図に適用させると、領域の頂点間の距離が大きくなると誤差がでます。また、北半球かつ東半球の緯度経度でないと正常結果が得られません。南緯や西経に
対応させるのは全点に90と180を加えてから計算すればよいはずです。球面への対応は、球面三角法で座標の計算をしなおせばいいような気がします。
今の所、肝はjavascriptやphpやvbで簡単に出来るといったところです。
以下が作成した領域判定の関数です。
function Region_chk(gpoint,gpolygon){
var result = new Boolean();
var count = 0;
for (i=0;i<gpolygon.getVertexCount()-1;i++){
if(
(
((gpoint.lng()-gpolygon.getVertex(i).lng()) *
(gpoint.lng()-gpolygon.getVertex(i+1).lng()))
< 0)
&&(
( (gpoint.lng()-gpolygon.getVertex(i).lng()) *
(
((gpoint.lng()-gpolygon.getVertex(i).lng()) *
(gpolygon.getVertex(i+1).lat()-gpolygon.getVertex(i).lat()))
-
((gpoint.lat()-gpolygon.getVertex(i).lat()) *
(gpolygon.getVertex(i+1).lng()-gpolygon.getVertex(i).lng()))
)
)
< 0)
){count++;}
}
if(count % 2 == 0){
result = false;
}else{
result = true;
}
return result;
}
この関数を、簡単にテスト出来るページも作ってみました。
http://yoneyone.my-sv.net/regionchk.htm
です。

 次に取り組んでいる事というか本来の目的は、件の、総理府提供の国勢調査「町丁・字等境界データ」のXMLから領域を取り出してジオコーディングした
住所がどの国勢調査の(町丁・字)地域に入るか調べたいのです。
 出来る限り、javascriptのみで作成するのを目的に、無理そうならphpで作成しDBは使用せず、ダウンロードしたXMLファイルのまま処理
したいのです。Xpathを使えば検索の手間が省けそうです。DBを使うとしても検査対象とするXMLファイル名の絞込みに使うぐらいにとどめたいで
す。

 何故DB使わないかというと、XMLのデータを全部DBに入れて処理するのは、完成すれば後が楽だけれども、XMLデータをロードするプログラムも作
らなければならないし、XML->EXCELロード->VBA->CSV->MySQLでやるにしても作業がたいへんそうに思えるからです。

 ※SQL Server 2008で、空間データ型やXMLネーティブ型なる物があるそうです
   が、これって無償の「SQL Server 2008 Express Edition」でも使えるみたい
   ですね。これもダウンロードして試してみようかな....

Masashi.K

unread,
Jul 1, 2009, 10:59:09 AM7/1/09
to Google-Maps-API-Japan
YON さん

細かく読んではいないのですが、
GBounds の containsPoint メソッドではダメなのですか?
http://code.google.com/intl/ja/apis/maps/documentation/reference.html#GBounds

YON

unread,
Jul 1, 2009, 9:18:59 PM7/1/09
to Google-Maps-API-Japan
> GBounds の containsPoint メソッドではダメなのですか?
ご返事ありがとうございます。
実は、最初
var latlangBounds =gpolygon.getBounds();
result = latlangBounds.containsLatLng(gpoint);
でやってだめだったので、別方法を考えたのです。
アドバイスされたGBoundsを使って
var polypoints =[];
for (i=0;i<gpolygon.getVertexCount();i++){
polypoints.push(new GPoint(gpolygon.getVertex(i).lat
(),gpolygon.getVertex(i).lng()));
}
var polybounds = new GBounds(polypoints);
result = polybounds.containsPoint(new GPoint(gpoint.lat(),gpoint.lng
()));
としてやっても、結果は同じでだめでした。
GBoundsのリファレンスの説明には、
 Constructs a rectangle that contains all the given points.
と記述され、与えられた点を全て含む長方形(rectangle)の領域となるようです。
従って、いびつな領域だと含まれていないのに含まれてしまう地点が起こりえます。

Masashi.K

unread,
Jul 1, 2009, 9:28:51 PM7/1/09
to Google-Maps-API-Japan
あぁ、なるほど。そうゆうことですか。

たぶん、計算幾何学 の本とか見れば載ってますよね。
大学時代にやった記憶がうっすらと・・・。
あまり覚えてないですが、たしかいくつかの三角形に分割してやれば
検出が簡単だったと思います。

三角形内に任意の点が含まれるかどうかは、下記ページにサンプルがありましたよ。
http://katsura-kotonoha.sakura.ne.jp/prog/c/tip00030.shtml


あとは、ゲーム系の本とかにそうゆう理論が載っているはずでは・・・。

あまりお役に立たずスミマセン。

yo

unread,
Jul 1, 2009, 9:53:03 PM7/1/09
to Google-Map...@googlegroups.com
時間が無いのでちょっと簡単に失礼しますが

http://trac.osgeo.org/geos/
^ たぶん、ここらへんのライブラリを使うかすると出来るかと思います。
(英語の資料ばかりなので、これを使っている、PostGIS関連を調べた方がいい資料が見つかると思います。)

http://d.hatena.ne.jp/hfu/20071217/1197866761
^ あと、国勢調査「町丁・字等境界データに関しては解らないので修正してある可能性もありますが、飛び地などを表現する為に、接続線などがついている場合、GEOSで「正常なトポロジでは無い」旨のエラーが出る事があるので、注意が必要かと思います。
(基盤地図情報 & PostGISで使用した場合に、エラーが出たような記憶がある、という事で参考までに。)

Masashi.K

unread,
Jul 1, 2009, 11:58:25 PM7/1/09
to Google-Maps-API-Japan
おぉ!いいですねこれ。

YON

unread,
Jul 2, 2009, 4:04:58 AM7/2/09
to Google-Maps-API-Japan
yo様情報提供ありがとうございます。
> http://trac.osgeo.org/geos/
のライブラリですが、残念ながら私には何を同使うのか理解困難でした。
PostGISは調べてみました。PostgreSQLのDBで空間データ扱う仕組みですね、
知りませんでした。参考になりそうなサイトがいくつか見つかりました。感謝です。
 (MySQLにもこんな拡張があればよかったのですが...)

GIS(Geographic Information System)関連については、暇な時、いろいろなサイト
を見て勉強中です。

> (基盤地図情報 & PostGISで使用した場合に、エラーが出たような記憶がある、という事で参考までに。)

 基盤地図情報というのは、国土交通省国土計画局の電子国土ポータルの地図で使われる国土数値情報ダウンロードのやつですね。国土交通省街区レベルと総
務省統計局提供の統計GISの地図で使われる町丁領域境界のダウンロードデータは、データの持ち方が違いますね。統計GISのデータでも飛び地、抜け地
の領域情報も区別して持ってるようです。

 表記名に対する領域は、国土交通省と総務省では異なっています。日本郵政の郵便番号領域や、法務省法務局の地番領域も微妙に異なるそうです。ジオコー
ディングという物は難しいですね。

Yoichi Kayama

unread,
Jul 2, 2009, 4:27:44 AM7/2/09
to Google-Map...@googlegroups.com
かやまと申します

一点だけ

2009/07/02 17:04 に YON<yyr...@gmail.com> さんは書きました:


> (MySQLにもこんな拡張があればよかったのですが...)

MySQLにもジオメトリ型という空間情報をあつかう型があります。
空間情報あつかう基本的な操作はできますよ。

古籏一浩

unread,
Jul 2, 2009, 5:38:41 AM7/2/09
to Google-Maps-API-Japan
On 7月2日, 午前10:28, "Masashi.K" <wf9a5...@gmail.com> wrote:
> あとは、ゲーム系の本とかにそうゆう理論が載っているはずでは・・・。
 ゲーム関係よりもCG関係で、それも1980年代の書籍や雑誌などには、こういう関係の解説や
 サンプルなどが結構掲載されていました(Oh!mz/Oh!X,Oh!FM, C MAGAZINE, アスキーのCG入門など)。

 今月だと、インターフェイス誌だったか、ハードウェア系の雑誌でライン描画や、ペイントなど
 Low Levelなアルゴリズムが掲載されてました。

 とりあえず、情報ということで。

OHTSUKA Ko-hei

unread,
Jul 2, 2009, 6:48:17 AM7/2/09
to Google-Map...@googlegroups.com
大塚です。

> MySQLにもジオメトリ型という空間情報をあつかう型があります。
> 空間情報あつかう基本的な操作はできますよ。

MySQLの空間拡張だと、バウンダリボックスベースでのインデックス検索はできますが、
PostGISばりのWithInチェックなんかはできないんじゃなかったでしたっけ?

もっとも、私も昨日見つけたところですけど、MySQLも最新のベータではかなり空間
関数が追加されているみたいですが、
http://forge.mysql.com/wiki/GIS_Functions
元諮問者の方の求めるWithIn関数なんかはなさそうです...。

※まあ、INTERSECTION関数とかで代用はできそうですが

2009/07/02 17:27 に Yoichi Kayama<yoichi...@gmail.com> さんは書きました:

wat

unread,
Jul 2, 2009, 8:02:49 AM7/2/09
to Google-Maps-API-Japan
こんにちは。

>  何故DB使わないかというと、XMLのデータを全部DBに入れて処理するのは、完成すれば後が楽だけれども、XMLデータをロードするプログラムも作
> らなければならないし、XML->EXCELロード->VBA->CSV->MySQLでやるにしても作業がたいへんそうに思えるからです。
>
>  ※SQL Server 2008で、空間データ型やXMLネーティブ型なる物があるそうです
>    が、これって無償の「SQL Server 2008 Express Edition」でも使えるみたい
>    ですね。これもダウンロードして試してみようかな....

PostGISとかでなくともノーマルのPostgreSQLでも、幾何データ型と幾何演算子が普通に使えますよ。
http://www.postgresql.jp/document/pg814doc/html/datatype-geometric.html
↑点、線、円、長方形だけでなく多角形(ポリゴン)データ型もあります。
http://www.postgresql.jp/document/pg814doc/html/functions-geometry.html
↑これの「~」(含むかどうか判定)っていう演算子が、それにあたるのでしょう。

> らなければならないし、XML->EXCELロード->VBA->CSV->MySQLでやるにしても作業がたいへんそうに思えるからです。

XML->perl/ruby/phpのXML取り扱いモジュールで書いたスクリプト->PostgreSQL
でやるってのはどうでしょう。javascriptでのコーディングができるのであれば
こうしたスクリプトを書くもそうハードルの高いものではないかもしれません。GoodLuck。

Yoichi Kayama

unread,
Jul 2, 2009, 9:41:33 AM7/2/09
to Google-Map...@googlegroups.com
かやまです

2009/07/02 19:48 に OHTSUKA Ko-hei<koko...@gmail.com> さんは書きました:


>
> 大塚です。
>
>> MySQLにもジオメトリ型という空間情報をあつかう型があります。
>> 空間情報あつかう基本的な操作はできますよ。
>
> MySQLの空間拡張だと、バウンダリボックスベースでのインデックス検索はできますが、
> PostGISばりのWithInチェックなんかはできないんじゃなかったでしたっけ?

http://dev.mysql.com/doc/refman/5.1/ja/functions-for-testing-spatial-relations-between-geometric-objects.html

ここに

16.5.4. Functions for Testing Spatial Relations Between Geometric Objects

とかいう章があるけど中身がなにも書いてないから、そういう関数は現状ではないのかもしれませんね(汗;

OHTSUKA Ko-hei

unread,
Jul 6, 2009, 10:29:16 PM7/6/09
to Google-Map...@googlegroups.com
大塚です。

> PostGISとかでなくともノーマルのPostgreSQLでも、幾何データ型と幾何演算子が普通に使えますよ。

おおー、PostGIS使いなので、逆に標準の幾何データ型はよく知らないのですが、意外といろいろできるん
ですね。
衝突判定までできるとは知りませんでした。
確かに本ユースケースだけだと、これでもすみそうですね。

ただ、単に幾何図形を扱うのではなく、地理情報を扱うのであれば、今回のユースケースは幾何データ型で
済むとしても、将来的にでてくるかもしれないユースケースを考えると、同じPostgreSQLを使うのなら
PostGISをお勧めします。

1.点、線、ポリゴンと別々のデータ型でなく、全部まとめて同じカラムに入れたいとか

2.オブジェクト間の球面上距離を計算したい、或いは球面上距離で検索したいとか

3.市町村合併なんかが起きたりで、ポリゴンをマージして新ポリゴンを作りたいとか

4.やっぱりmysqlラブなんじゃよー、ということで、将来mysqlの空間対応が十分に発展したら、即効で
mysqlにデータ移して乗り換えたい、とか
(PostGISやmysqlの空間拡張は、OGCという規格に準拠して作られているので、データの表現形式だと
ほぼ100%の互換、関数等も6~7割方は互換です。)

5.大量の日本測地系のポリゴンデータを、まとめて世界測地系に変換して登録したいとか、逆に世界測地系
で入ったポリゴンデータを日本測地系で出力したいとか

6.ポリゴンデータをKMLからDBに入出力する際に楽をしたいとか

そんなケースだと幾何データ型は対応できませんが、PostGISだと対応できるので、「幾何データ型がある
のに何故PostGISができたか」というあたりを考えても、地理データを使うのならば、しかもわざわざ
PostgreSQLを導入して、なのであれば、PostGISを使うことを個人的にはお勧めします。

2009/07/02 21:02 に wat<watan...@gmail.com> さんは書きました:
Reply all
Reply to author
Forward
0 new messages