javascript - 閉じたパスの多角形近似を見つける

Question

閉じたパスの最適な多角形近似を見つけられるようにしたいのですが (画像から引き出されているため、任意のパスである可能性があります)、それを見つけるアルゴリズムのコーディング方法に問題があります。

私は単純なアプローチを考えることができます: パスに沿ったピクセルの x 量ごとに、それらのピクセルに最適な線を選択し、次にさまざまな開始オフセットと長さに対してブルート フォースを適用し、最小量で最小二乗誤差を最小化するものを見つけます。行の。

もっとエレガントなものがあるはずです。何か知ってる人いますか？また、（うんざりする）しかし、これは私が本当に必死にならない限り、JavaScriptで実装される予定です。そのため、あなたのために何かをする素晴らしいライブラリはほとんど除外されています（たとえば、opencvにはポリゴンフィッターがあります）。

Answer 1

ここでは、 Ramer–Douglas–Peuckerアルゴリズムが適切であるように思われ、実装は簡単です。許容可能なエラーはこのアルゴリズムへの入力であることに注意してください。したがって、ターゲットの行数がある場合は、エラーパラメーターを使用してバイナリ検索してターゲットをヒットできます。

Answer 2

D3.js 1には、使用できるアダプティブ リサンプリングコードが含まれています。使用されているアルゴリズムの図解説明もあります(Visvalingam のアルゴリズム)。