著者

結城 匡人 徳山 豪

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2003, no.53, pp.9-16, 2003-05-23

---

地図製作やコンピュータグラフィックスの分野では、曲線を表現するのに、その上のサンプル点の列を使用するが、データ量を圧縮するために、曲線の単純化が必要となる。多角形曲線を単純化する近似アルゴリズムとして、Frechet distanceを利用したFrechetSimp法を使用し、二分探索法を用いて、O(nlog n)で計算できる。FrechetSimp法を実装し、複雑に折れ曲がった曲線でも、その特徴を残したまま単純化できることを紹介する。FrechetSimp is an approximation algorithm for that applies the concept of Frechet distance. The algorithm is based on binary search and its complexing is O(n log n). We implement this algorithm and report some experimental results.