「点p＝（Ｘp，Ｙp）と、多角形の頂点qi＝（Ｘi，Ｙi）が与えられた時、
　多角形の各辺について、Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1)を計算して
　これが負である場合のみ、
  　 Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}を求めて
　その符号( Ｍ２＜０のとき１、Ｍ２＞０のとき０）の和を求め、
　これが偶数であるとき、与えられた点pは多角形で囲まれる領域の外部にあり、
　奇数であるときには内部にあると判定する」

です。上は特許のようですが、商用利用はしないので、この理論を元に、javascriptでコーディングして、googleマップ上のある
Glatlng地点がGpolygon領域内にあるかを判定する関数を作ってみました。もっとも、この理論は2次元平面座標系の理論だから、地球面上の
地図に適用させると、領域の頂点間の距離が大きくなると誤差がでます。また、北半球かつ東半球の緯度経度でないと正常結果が得られません。南緯や西経に
対応させるのは全点に90と180を加えてから計算すればよいはずです。球面への対応は、球面三角法で座標の計算をしなおせばいいような気がします。
今の所、肝はjavascriptやphpやｖｂで簡単に出来るといったところです。
以下が作成した領域判定の関数です。
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;

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

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

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

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

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

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

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

一点だけ

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

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

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

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

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

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

ここに

16.5.4. Functions for Testing Spatial Relations Between Geometric Objects

ただ、単に幾何図形を扱うのではなく、地理情報を扱うのであれば、今回のユースケースは幾何データ型で
済むとしても、将来的にでてくるかもしれないユースケースを考えると、同じ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<watanabe...@gmail.com> さんは書きました: