以前に調べた折れ線を簡略化する方法は線分の途中の点を省いて軽量化する方法で、線分のままだった。 それとは違い、曲線を当てはめるアルゴリズムを調べた。
ベジェ曲線フィットを動かしてみる
ブックマークを掘り返してたらpaper.jsのPath Simplificationというマウスで描いた軌跡を曲線化するサンプルがあった。
どういう仕組みなんだろうと思ってソースを見てみると、path.simplify()から呼び出しているPathFitterクラスのコメントに
// An Algorithm for Automatically Fitting Digitized Curves
// by Philip J. Schneider
// from "Graphics Gems", Academic Press, 1990
// Modifications and optimizations of original algorithm by Jürg Lehni.
と書かれていた。 Graphics Gemsは過去に出版された本で、関する情報はRealtime Renderingのサイトで管理されている。 オリジナルのソースはGithubで公開されている：FitCurve.c
Paper.jsは指定のキャンバスに自動的に描画されてしまうので自分で使うためにPathFitterを抜き出そうとしたが依存するクラスが多くて難しかった。
他のソースを探したところ
点列をベジェ曲線でフィッティングするライブラリをフォークしてTypeScriptで書き直してみた - イワモト・カイドウからfit-curveの型情報を省いてJavaScriptに変更した。
動かしてみると、だいぶうまくフィットするベジェ曲線を生成できることがわかる。 許容できる誤差で精度を調整できるので都合がいい。
うまく使えば点群の削減にもなると思うが「折れ線の簡略化」とは少し用途が違うというか（当然ながら…）、フォントデータなどを曲線に変換して拡大しても綺麗という用途に使用するのがよさげ。
fitCurveで求めたベジェ曲線を自分で描画するのはなかなか難しそうだけど、CanvasのAPIがあった： bezierCurveTo- 与える許容誤差は距離の二乗と比較するので、例えば100なら10ピクセルということになる
An Algorithm for Automatically Fitting Digitized Curves
件のアルゴリズムを完全に理解はしてないんだけど、大まかには
- 全体に対して３次ベジェ曲線の当てはめを考える
- 実際の点とのずれが許容内だったら終了
- 誤差が最大の点で分割し、前半と後半で再帰
ということらしい。 ３次ベジェ曲線をどうやって当てはめるかは、
- 折れ線の長さから各点の割合(0.0~1.0)を求める(Chord-length parameterization)
- ベジェ曲線の制御点は先頭と末尾の点の接線上におく
- 接線上のどこにおくかは、すべての点の二乗誤差を微分して0と置いて解くと求まるらしい
- さらにニュートン・ラフソン法で反復して精度を高めるとか
詳しくは理解してない。
- 区間を区切るにしても向きは連続させてるはずなのに、急な角も再現できるのはどうなってるんだろうか？ 縮退されたベジェ区間ができてるんだろうか？
- ３次ベジェ曲線同士が滑らかにつながるかどうかで連続ではなく連続、隣あう制御点同士の長さが異なることを許容することで自由度がどうとか…
リンク
他
- スプライン、ベジェ曲線の連続に関してなど、反射が不連続になるから車体の曲面で重要とかおもろい