はじめに

Graphics Gem1 の「AN ALGORITHM FOR AUTOMATICALLY FITTING DIGITIZED CURVES」
の改良案です。
とりあえず確実に効果のあった手法3つを記載します。
「AN ALGORITHM FOR AUTOMATICALLY FITTING DIGITIZED CURVES」についてはこちらで解説してあります。

点列の分割法

許容誤差を満たさない点列を分割するとき、対象とならない残りの点列はまとめる。

Original algorithm

\begin{aligned}
&1:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ}_{target\ \rightarrow\ \times}\\
&2:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\ \circ}_{target\ \rightarrow\ \times}\\
&\hspace{110px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\ \circ}_{stack[0]}\\
&3:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ}_{target\ \rightarrow\ \circ}\\
&\hspace{59px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\ \circ}_{stack[0]}\\
&\hspace{110px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\ \circ}_{stack[1]}\\
&4:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ}_{\circ}\\
&\hspace{59px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\ \circ}_{target\ \rightarrow\ \circ}\\
&\hspace{110px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\ \circ}_{stack[0]}\\
&5:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ}_{\circ}\\
&\hspace{59px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\ \circ}_{\circ}\\
&\hspace{110px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\ \circ}_{target\ \rightarrow\ \circ}\\
\end{aligned}

New algorithm

\begin{aligned}
&1:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ}_{target\ \rightarrow\ \times}\\
&2:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\ \circ}_{target\ \rightarrow\ \times}\\
&\hspace{110px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\ \circ}_{stack[0]}\\
&3:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ}_{target\ \rightarrow\ \circ}\\
&\hspace{59px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ}_{stack[0]}\\
&4:\ \underbrace{\circ\circ\circ\circ\circ\circ\circ}_{\circ}\\
&\hspace{59px}\underbrace{\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ\circ}_{target\ \rightarrow\ \circ}\\
\end{aligned}

最大回数まで弧長パラメータを更新し、フィッティングする

maxIterations まで計算すれば基本的に誤差は小さくなる。
しかし、maxIterations に対して誤差関数は単調減少ではないので、誤差が増えるようなら処理を中断する。
許容誤差を満たしたら、それを採用するのは勿体ない。

再フィッティング

点列を分割し、3次ベジェ曲線列を作成した後の処理である。
元の点列の端点以外の点は通る必要は無いので、隣り合う3つベジェ曲線をG1連続でフィッティングしなおす。

\begin{aligned}
&1:\ \underbrace{\circ\circ\circ\circ\circ\circ\color{cyan}{\circ}\circ\circ\circ\circ\circ\color{cyan}{\circ}}_{fit\ \sharp 0\ and\ \sharp 1}\circ\circ\circ\circ\circ\color{cyan}{\circ}\circ\circ\circ\circ\circ\circ\\
&2:\ \circ\circ\circ\circ\circ\circ\underbrace{\color{cyan}{\circ}\circ\circ\circ\circ\circ\color{cyan}{\circ}\circ\circ\circ\circ\circ\color{cyan}{\circ}}_{fit\ \sharp 1\ and\ \sharp 2}\circ\circ\circ\circ\circ\circ\\
&3:\ \circ\circ\circ\circ\circ\circ\color{cyan}{\circ}\circ\circ\circ\circ\circ\underbrace{\color{cyan}{\circ}\circ\circ\circ\circ\circ\color{cyan}{\circ}\circ\circ\circ\circ\circ\circ}_{fit\ \sharp 2\ and\ \sharp 3}\\
&4:\ \circ\circ\circ\circ\circ\circ\underbrace{\color{cyan}{\circ}\circ\circ\circ\circ\circ\color{cyan}{\circ}\circ\circ\circ\circ\circ\color{cyan}{\circ}}_{fit\ \sharp 1\ and\ \sharp 2}\circ\circ\circ\circ\circ\circ\\
&5:\ \underbrace{\circ\circ\circ\circ\circ\circ\color{cyan}{\circ}\circ\circ\circ\circ\circ\color{cyan}{\circ}}_{fit\ \sharp 0\ and\ \sharp 1}\circ\circ\circ\circ\circ\color{cyan}{\circ}\circ\circ\circ\circ\circ\circ\\
\end{aligned}

"fit #0 and #1" では ${\bf p}_1,{\bf p}_2,{\bf p}_3,{\alpha}_0,{\alpha}_2$ を更新し、${\bf p}_0,{\bf q}_3$ の位置ベクトルと ${\bf q}_2-{\bf q}_3$ の方向ベクトルは固定する。
"fit #1 and #2" では $\beta_0,{\bf p}_2,{\bf p}_3,{\alpha}_0,{\alpha}_2$ を更新し、${\bf p}_0,{\bf q}_3$ の位置ベクトルと ${\bf p}_1-{\bf p}_0,{\bf q}_2-{\bf q}_3$ の方向ベクトルは固定する。
"fit #2 and #3" は点列を逆転させれば、fit #0 and #1 と同様の処理である。
"fit #0 and #1"、"fit #1 and #2" の最適化時の目的関数は凸ではないので、「準ニュートン法」などで解くのがよい。

${\alpha_0},{\alpha_2},{\beta_0}$ は $||{\bf q}_1 - {\bf q}_0||,||{\bf q}_2 - {\bf q}_3||,||{\bf p}_1 - {\bf p}_0||$ のことである。

最後に

こちらの記事にあるようにQiitaは変な仕様で書いていてイライラする。