仕様・定義に関するディスカッション
sa2da
sa2da
sa2da
> GeoHex3D化に向けての議論まとめhttp://togetter.com/li/58428
また、GeoHexV2のコード体系を含む仕様に関する要望や
追加リクエスト受付は一旦10月いっぱいまでとさせていただきます。
ご質問等もお気軽にどうぞ。
@sa2da
-------------------------------------------------------
GeoHexディスカッショングループ
http://groups.google.co.jp/group/geohex
sa2da
突然のヒアリングのお願いですが、
10月いっぱいで要望受付を終えましたので、
11月中にGeoHex v2.* の仕様アップデートをクローズし、
各種ドキュメントの整備に移りたいと思います。
以下、今回仕様の見直しをすべきか否か検討している事項です。
特に、すでに開発頂いてる方への影響もあるため、
メリットも踏まえた上で仕様変更に対してのヒアリング結果に
沿って方針を選択していこうと考えています。
開発者の皆様の視点でご意見・フィードバックをいただければ
非常に助かります。
（１.座標系について）
・GeoHexの座標は緯度経度の0度を原点に、左右対称の30度の
斜形座標系を採用しています。
[課題]
X,Y値による範囲検索を行うと菱形の範囲を表すことになり、
等距離の演算などは別途処理が必要となる。
[解決案]
縦方向に1軸（Z）を加えると六角形の範囲検索が可能になり、
等距離の検索等においてロジックが非常にシンプルになる。
また、90度回転した座標系を組み合わせることで、
上位ヘックスに対する下位ヘックス演算がさらに容易になる
といったメリットも。
X,Y値はそのまま使える拡張仕様です。
[質問事項]
座標体系の仕様変更に対する是非
ａ）仕様を変更したほうがいい
ｂ）すでに開発したものに手を加えたくないためNG
ｃ）どちらでもいいが、特に必要と思わない
ｄ）よく分からない
ｅ）もっといい方法がある
（2.ヘックスコードについて）
・座標系からヘックスコードへのエンコードにおいて、
座標値の符号により(+)は奇数・(-)は偶数といった形で交互に
ヘックスコードを割り当てています。
[課題]
between等のsql文などを単純に実行すると反対符号が混じって
しまうため、別途演算処理が必要となる。
[解決案]
変換文字列の中央値（60進の30、31番目の文字）を中央値として
符号（ー）は30以下、（＋）は31以降を割り振ることで、
0、60の境界値のみ判定を行えばよくなる。
[質問事項]
コード体系の仕様変更に対する是非
ａ）仕様を変更したほうがいい
ｂ）すでに開発したものに手を加えたくないためNG
ｃ）どちらでもいいが、特に必要と思わない
ｄ）よく分からない
ｅ）もっといい方法がある
上記以外のご質問等でも結構です。
期日は今週末までとさせていただきます。
ご協力のほど何卒よろしくお願い致します。
以下も参考まで。
第1回GeoHex勉強会発表資料
http://www.slideshare.net/sa2da/geohex-20100903-5126785
第2回GeoHex勉強会発表資料
http://www.slideshare.net/sa2da/geohex1
-------------------------------------------------------
GeoHexディスカッショングループhttp://groups.google.co.jp/group/geohex
OHTSUKA Ko-hei
お疲れ様です。
書き始めてから「開発者」と書かれていたのに気付きましたが、v2には開発者としては
関わってませんがよいでしょうか。
v2はロジック追ってなくて概念だけで意見言ってきてますので…。
2010年11月3日2:10 sa2da <tdys...@gmail.com>:
検索というのが、
1)ロジック上の距離計算
2)SQLでの等距離内ヘクス一括検索
3)GeoHashのような、下位桁を切り捨てての空間インデックス的用途
のどれを指しているのかが不明瞭ですが、
1)の場合、
Z軸は結局X,Yの関数なので、逆関数は求められX,Yの条件に落とせるのでそこまで
難解ではないですし、それにその辺はAPIで吸収する事だと思うので、API開発者だけ
理解していればよいと思います。
2)の場合、
XY軸、或いはXYZ軸で範囲検索といっても、DBに格納する際にコードを分解して各軸
要素毎に格納するならば別ですが、1カラムに入れてしまうのであれば、各軸での範囲
検索はそもそもできないのでは？
単にSQLが書ければいいのであればsubstrとか使えばできますが、インデクス効かない
ので実用速度出ないです。
3)の場合、
上位桁前方一致での空間インデクス効果を狙う場合、形状は割とどうでもよくて、下位
桁を落とした場合のクラスタ度合いが適切かの方が重要だと思います。
現行の60x60=3600分木というのは空間インデクスとして使うにはあまりにも大き過ぎる
ので、前方一致での空間インデクス効果をどうしても視野に入れたく、かつコード長の
増加をためらわないのであれば、Z軸導入よりも座標の進数を30進数とか20進数とかに
落として上位桁でのクラスタ度合いを下げる方がよいと思います。
よって、1～3いずれの視点からも、Z軸は不要かなと。
> （2.ヘックスコードについて）
> ・座標系からヘックスコードへのエンコードにおいて、
> 座標値の符号により(+)は奇数・(-)は偶数といった形で交互に
> ヘックスコードを割り当てています。
> [課題]
> between等のsql文などを単純に実行すると反対符号が混じって
> しまうため、別途演算処理が必要となる。
> [解決案]
> 変換文字列の中央値（60進の30、31番目の文字）を中央値として
> 符号（ー）は30以下、（＋）は31以降を割り振ることで、
> 0、60の境界値のみ判定を行えばよくなる。
> [質問事項]
> コード体系の仕様変更に対する是非
> ａ）仕様を変更したほうがいい
> ｂ）すでに開発したものに手を加えたくないためNG
> ｃ）どちらでもいいが、特に必要と思わない
> ｄ）よく分からない
> ｅ）もっといい方法がある
ロジック読んでなかったんですが赤道が原点だったのですね。
v1と同様に、南極付近に原点0があると思ってました。
「between等のsql文」とあるようなGeoHexの直接範囲検索には懐疑的ですが、
現行ロジックだと最上位桁とそれ以下の桁でコード文字割り当てのロジックが
大きく異なってしまうので、解決案の方がよいと個人的には思います。
>
> 上記以外のご質問等でも結構です。
>
> 期日は今週末までとさせていただきます。
> ご協力のほど何卒よろしくお願い致します。
>
> 以下も参考まで。
> 第1回GeoHex勉強会発表資料
> http://www.slideshare.net/sa2da/geohex-20100903-5126785
> 第2回GeoHex勉強会発表資料
> http://www.slideshare.net/sa2da/geohex1
>
> -------------------------------------------------------
> GeoHexディスカッショングループhttp://groups.google.co.jp/group/geohex
>
> --
> このメールは Google グループのグループ「GeoHexディスカッショングループ」の登録者に送られています。
> このグループに投稿するには、geo...@googlegroups.com にメールを送信してください。
> このグループから退会するには、geohex+un...@googlegroups.com にメールを送信してください。
> 詳細については、http://groups.google.com/group/geohex?hl=ja からこのグループにアクセスしてください。
>
>
--
HTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT
株式会社ATR-Promotions ミュージアムメディア事業部
プロデューサ
大塚 恒平
〒619-0228「けいはんな学術学研都市」光台2-2-2
TEL：0774-95-2636 FAX：0774-95-1191
Mail：koht...@atr-p.com
HTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHTHT
sa2da
大塚さん、早速のレスありがとうございます。
まさしく、お聞きしたいことズバリ。さすが。
1については、その3つ共を意図しており、更に掘り下げられたらと思ってます。
空間インデックスとしての効果は期待出来ないが、API使う側としてあった方が楽とか、多少sql書くのが楽でも結構ですので皆様のご意見下さい。
空間インデックスとしての分割数とコードの桁数のバランスや、Base32やBase64へ準拠すべきか等も議論できれば幸いです。
また、逆にヘックス座標でDB格納するので、コード体系はさほど重要ではない、その点からすると、z軸はあった方がいい、なくてもいい、といったご意見もあれば是非。
2についても1が関係してきますが、改修しても構わないという反応であれば是非変えたいと思います。
よろしくお願いいたします。
iPhoneから送信
Haruyuki SEKI
基本的なスタンスとして、コードの変更が伴なう改変は特に問題としません。
ポーチティング元のJSバージョンとテストケースは欲しいですが。
z 軸は特に必要性を感じませんでしたが、前方一致での空間インデクス効果は魅力ですね。
2 は変更してもいいんじゃないでしょうか。
--
Haruyuki Seki
2010/11/4 sa2da <tdys...@gmail.com>:
sa2da
関さん、ありがとうございます。
変更点、バージョン、テストケースは共有させて頂きます。
残念ながら他の方からのリアクションがなさそうですので、この辺で〆ます。
まとめると、
・z軸は今回は見送ります
・符号区分はエンコード配列の中央値に変更
・空間インデックスに有効な分割ロジックを再検討
ということで、最後の分割方法について再度ご意見ください。
・GeohashはBase32エンコード
（1文字省略すると、32倍のサイズ）
・現GeoHexは60進エンコード
（1文字省略すると、60倍のサイズ）
アルファベットの大文字、小文字を区別しない環境の場合もBase32の方が適してます。
更に空間インデックスとして32分木でも差が大きいのであれば、6,8,16進辺りにするかですね。
その分ヘックスコードは長くなりますが、仮に現アルゴリズムで16進にした場合、x,yそれぞれ最大（最小ヘックスサイズ）2桁ずつ、合計4桁増えるので13⇒17桁。それより大きなヘックスだど桁数減りますので、この位の差であれば16進にするのもありしょうか？
iPhoneから送信
OHTSUKA Ko-hei
> （1文字省略すると、32倍のサイズ）
> ・現GeoHexは60進エンコード
> （1文字省略すると、60倍のサイズ）
これ、ちがうんじゃなかったでしたっけ。
GeoHashは2軸でBase32だったと思いますが、GeoHexは1軸60進なので、2軸だと3600進になるのでは？
2010年11月5日9:51 sa2da <tdys...@gmail.com>:
sa2da
すいません、Geohash勘違いな説明しました。
交互に2の5乗をビットエンコードしてるので1文字切ると交互に縦か横に長くなるんでした。
（4×8と8×4のケースが交互）
GeoHexのエンコードは各軸独立しているので、軸ごとに60進。
1文字削ると1方の軸だけ60倍、を交互に。
ということで、
ここから本題に。
各軸4倍ずつで4×4の16進か、8×8でBase64 にするか
iPhoneから送信
後藤俊介
sa2da
iPhoneから送信
sa2da
iPhoneから送信
Mage Whopper
2010年11月5日19:03 sa2da <tdys...@gmail.com>:
> sa2daです。
> 改めて再考しました。
> さっきのは誤りかもしれないので、改めて家で考えてみます。
> 4×4単位か、8×8単位か、その中間値か、その選択が空間インデックスのサイズに直結しますので、なるべく差が開きすぎないように、かつコード体型も長くなりすぎないように（と、議論の流れでふれたと思います）したいですね。
> ※ヘックスサイズ（レベル）は1サイズに固定し、そのレベルの空間におけるインデックス有効化をはかるコード体系です。
>
よくわかっていないので
ちょっとまとめてみました。
http://magemap.blogspot.com/2010/11/geohex.html
sa2daさんのおっしゃっている
19個のHexを表すコードとは、
あるXY値について、
今より小さい値のレベル(大きなHex)を
現状のcodeの存在にかかわらず定義する形のIndex、
という意味に聞こえましたがこの理解で正しいでしょうか。
現状で、あるレベルのHexコード(=XY値)は
それよりも細かいレベルのXY値(x*2^d, y*2^d)と
その周辺のXY(x*2^d+{-1,0,+1}, y*2^d+{-1,0,+1})を含んでおり、
周辺Hexのxy値は中心Hexのxy値に加減算で求めることができます。
ずらしたHexをIndexとして用意するのは
絵的に面白いと思います。
一方で、異なる中心点のIndex同士の領域重複を扱うのは
複数の原点を持つ座標系を同時に扱う形にもなり、
厄介な点もありそうです。
複数の原点座標については
素人的にはcodeにある物とindexにあるもののルールを決めれば
問題なさそうかな、と思います。
しかしそもそもの理解が浅く、
利点と欠点をきちんと挙げられている気が全くしていません。
正直、Indexの使い道もよく分かっていません。
特に、大きなHex使うのとの違いがよく分かっていません。
そんなレベルですみません。。
現時点でのコード体型の変化に関しては
個人的には問題ないと思います。
大きい変化があるときにも
コード体系のバージョンを取得できるインターフェース（API?)
を用意しておけば、
相互変換が作れる限り、今後も対応できるように思います。
そのために開発できる人が揃うかどうかは大問題なので
変更大歓迎という訳にはいきませんが。。
Mage Whopper
magew...@gmail.com
sa2da
ども、sa2daです。
ディスカッションへのご参加、ありがとうございます。
勉強会の資料では結構踏み込んで仕様の説明資料を公開しているのですが、
まだWeb化していないものが多いのでMageさんにその辺おさらいしていただき
恐縮です。
Hex座標系に落としてしまえば演算は容易なのですが、
空間インデックスを有効にするには、
コード体系として前方一致を可能な体系にする必要がある、
という理解で議論を進めています。
そもそもその理解であっていますか？ ＞皆様
ヘックスコードの1文字を削ると現在は
X、Y交互に60倍ずつになるようになっています。
元々Geohashのことを知らずにスタートしたプロジェクト
だったということもあり、
独自にも二乗分割をビット化してエンコードする方法は
思いついていたのですが、
上位レベルに下位レベルは完全には内包しないこと、
60進の方が圧縮効率が高いと考えて現仕様にいたってます。
一定範囲ずつ分解していく際、
仮に1文字にXYを同じ割合で盛り込んだとして、
横長の菱形形状になります。
そこで、ヘックス座標系とエンコードアルゴリズムを
完全に別として考えるのもありかな？と、試行錯誤してみました。
…最初に立ち返り、内包関係を無視して
同レベルのヘックス座標系のみ有効になる分割アルゴリズム
（Geohash型）がいいのかもしれません。。
2010年11月6日3:52 Mage Whopper <magew...@gmail.com>:
seikoudoku2000
前の勉強会でお話を聞いてから、試しにhex内検索をできる画面を作成してみていますので、
遅ればせながらですが、作りながら思ったことを入れながら、この議論を見て思ったことを投稿させていただきます。
ちなみに↓で開発してます。
---
http://geohexseikoudoku2000.appspot.com/?mode=1
---
(chromeとiPadでも一応動きますが、mapのdraggable=falseにしていたり、
特にtouch系はイベントの制御があまり出来ていなかったりと、作り中です。。)
>また、逆にヘックス座標でDB格納するので、コード体系はさほど重要ではない、
>その点からすると、z軸はあった方がいい、なくてもいい、といったご意見もあれば是非。
（今はappengineのbig tableの検索の制限により、XYを結合させた文字列を２５フィールドに格納。）
深く仕様を理解できているわけではないですが、将来的な機能拡張の時にそっちのほうが
小回りが利きそうかな～と、直感的に思いました。
逆に現状だとコードでしかできないことが無いように思うので、変更はしちゃったほうが良いと思います。
>空間インデックスを有効にするには、
>コード体系として前方一致を可能な体系にする必要がある、
⇒内包関係を実現した前方一致検索が行えると魅力的ですね。統計結果表示なんかで使えそうです。
ただ、Hexのレベルを上げてもできないことがコード体型の変更によってできるようになるというのが
魅力的な気がするので、辺の重複や隙間が出来るという制限が付くと、使う側からすると逆に混乱してしまい、、、
な気がします。
使い方はだいぶ分かってきたのですが、内部仕様になるとまだまだ理解が及んでいないところがあるので、、
的はずれなこと言ってたらすいません。
作ってて楽しいので、内部的な仕様も頑張ってコード読んだりしてキャッチアップしていくようにします。
>
> > Mage Whopperです。
>
> > 2010年11月5日19:03 sa2da <tdys....@gmail.com>:
> > --
> > このメールは Google グループのグループ「GeoHexディスカッショングループ」の登録者に送られています。
> > このグループに投稿するには、geo...@googlegroups.com にメールを送信してください。
> > このグループから退会するには、geohex+un...@googlegroups.com にメールを送信してください。
> > 詳細については、http://groups.google.com/group/geohex?hl=jaからこのグループにアクセスしてください。
>
>
>
> 193K表示ダウンロード
sa2da
ディスカッショングループへのご参加、ありがとうございます。
指でなぞるの、うまくイベント拾えたんですね。イイですね、これ。
ヘックスは指のサイズにもマッチするので、タッチUIに向いてます。
座標系の値で直接管理するのは確かに融通効きますね。
重複等なくインデックスの効きそうなコード体系についてはもうしばらく検討を続けてみようと思います。
よろしくお願いします。
iPhoneから送信
m.misaki
ML参加は、はじめてな三浦＠yukainaです。
jsや、javaにポーティングされたのを参考に
PostgreSQLでストアドにしてみたりして勉強させてもらっています。
まだ、内容理解が足りていないこともあり
こちらでディスカッションは、見ているだけですが、
質問させていただくこともあるかと思いますので
よろしくお願いします。
sa2da
sa2daです。
MLにご参加いただきありがとうございます。
ご質問お気軽にどうぞ。
本題からそれますが、GeoHex PostGIS対応プロジェクトメンバーを
募集したいと思います。
お力添えいただけるようでしたら是非。
よろしくお願いします。
iPhoneから送信
m.misaki
三浦です。
PostGIS対応の方、お誘いいただきありがとうございます。
お役に立てるかはともかく、ぜひ参加したいです。
よろしくお願いします。
sa2da
Twitter上では告知していましたが、GeoHexグループの方に正式に告知していなかったので少し日が経ってしまいましたが改めてお知らせします。
V3では新たに3の累乗分割（V2は2の累乗分割）ロジックを設計し、前方一致型のコード体系を定義しました。
▼V3仕様はこちら
http://geogames.net/geohex/v3
早速@chshiiさんにJava版を対応していただきました。
https://github.com/chsh/geohex4j
V3版を作るにあたり、拡張関数はいったん全て外し
エンコード／デコードのコア関数のみ実装しています。
テストケースは以下をご利用ください。
http://groups.google.com/group/geohex/web/test-casev3