Re: [OSGeoJapan-discuss] Douglas-Peukerなどを用いた簡素化についてのアルゴリズムを教えてください。

[wakasa masao]

山手さん、吉田さん

返答ありがとうございました。
GRASSのソース追えばいいんですね。
そうですよね。そこに知が詰まってますよね。ちょっと見てみることにします。

吉田さんにご紹介いただいたコードはやはり普通に間引きするだけのような動作のように思えます。実行してないのでなんですが、これが正しい？Douglas-Peukerの方法なんですね。
ではPostGISのST_Simplifyは何をやっているんだろう・・。
クライアントにST_Simplifyの綺麗な間引きを見せてしまったばっかりに、結局は出来上がりが（数値的に）違う事になるのでなんともなぁと思っていまして。

もうちょっといろいろ見てみます。
ありがとうございました。

------------
wakasa masao



2010年6月26日22:53 Daisuke YOSHIDA <nro2dai ＠ gmail.com>:
> 帝塚山の吉田です。
>
> 下記URLのPHPプログラムを実装したことがあります。
> http://www.fonant.com/demos/douglas_peucker/algorithm
> GPSトラックの単純化に使用しました。
> PostgreSQLで検索されたポイントを
> このPHPプログラムで単純化し、OpenLayersで表示するようなプログラムです。
>
> Python版プログラム（Songさん作）を持っていますが、PHP版の方が格段に早いですね。
> GRASSのv.generalizeと比較しましたが、結果はほぼ同じです。
>
> 山手さんのメールに書かれていますが、GRASSのv.generalizeコマンドには
> 普通のDouglas-Peukerアルゴリズムの他に、いろいろとオプションを付けれます。
> http://grass.itc.it/gdp/html_grass64/v.generalize.html
>
> 確かにSQLで行うのは、ちょっと微妙ですね。
>
> 2010/6/26 wakasa masao <machio ＠ mac.com>:
>> 若狭です。
>>
>> ラインの単純化を行うPostGISのST_SimplifyのようなものをJava及びJavaScriptの２言語で行おうとうしています。
>> Douglas-Peukerを用いてるというのはマニュアルにもあるので、このアルゴリズムが実装出来ればいいのかなと思っています。
>> ですが、Googleで検索しても、アルゴリズムとしては紹介されるものの、どのようなものなのかが探しきれませんでした。
>> なんとか下記のようなActionScriptで作られたものを見つけて、このコードを元に移植してみました。
>> http://www.lostinactionscript.com/blog/index.php/2007/07/11/douglas-peuker-line-generalization/
>>
>> ところが、同じデータを投入したところでST_Simplifyと自作プログラムの性能の差が出ました。
>> ST_Simplifyの方が５倍以上圧縮されなおかつ綺麗にできています。
>> 上記の参考にしたプログラムは、ポイントポイントに単にフラグを立てて類似ものを消すという間引きの動作のようですが、
>> ST_Simplifyで出来上がったものを見ると、渡したデータでは存在してない点にポイントが打たれたり、
>> 似たような図形を描画するためにという動作に見えます。
>> 参考にしたコードがDouglas-Peukerを実装されてるのかどうかも定かではないのでなんですが。
>>
>> なので、ご存知でしたら
>> ・ST_Simplifyに近い簡略化ができるようなアルゴリズム
>> ・Douglas-Peukerを利用したライブラリやソースコードなど
>> はどのようなものがあるでしょうか？
>>
>> 私自身このあたりの学術的な知識が無く、ご存知の方がいらっしゃいましたら、お教えください。
>>
>> ちなみにPostGISを使えば解決なのですが
>> ・Javaで作る必要性は、簡略化の為にSQL書くのは、速度的にも負荷的にも高くなってしまう
>> ・JSで作る必要性は、大きめのデータを渡してフロント側で簡略化し表示負荷及びネットワーク負荷を下げたい
>> という理由でなんとかしたい状態です。
>>
>> よろしくお願いします。
>>
>> ------------
>> wakasa masao
>>
>> _______________________________________________
>> OSGeoJapan-discuss mailing list
>> OSGeoJapan-discuss ＠ lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/osgeojapan-discuss
>>
>>
>
>
>
> --
> 吉田 大介
> 帝塚山学院大学 リベラルアーツ学部
> 589-8585 大阪狭山市今熊2-1823
> TEL 072.365.0865 FAX 072.365.5628
>
> _______________________________________________
> OSGeoJapan-discuss mailing list
> OSGeoJapan-discuss ＠ lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/osgeojapan-discuss
>
>