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

[Daisuke YOSHIDA]

帝塚山の吉田です。

下記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 at 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 at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/osgeojapan-discuss
>
>



--
吉田 大介
帝塚山学院大学 リベラルアーツ学部
589-8585 大阪狭山市今熊2-1823
TEL 072.365.0865 FAX 072.365.5628