1つの平面に点の配列があります。それらは何らかの形を形成します。この形状の直線のみを形成する点をこの配列から抽出する必要があります。
現時点ではアルゴリズムがありますが、うまく機能しません。最初の 2 点を取り、直線を作成してから、次の点が許容範囲内にあるかどうかを確認します。しかし、問題があります。直線を形成する点は実際には直線上になく、多少のずれがあります。この偏差値はかなり大きいです。私のアルゴリズムで、直線部分からポイントを取得するのに十分な大きさの偏差を作成した場合、わずかに曲がった部分にあるが、偏差が指定よりも小さい他のポイントも抽出されます。
そのようなタスクを実行する方法についてのアイデアを探しています。
ここに写真があります：
丸の中は抽出したい部分です。赤い点は、私のアプローチで抽出できた部分です。公差を大きくすると、まっすぐなピースも逃してしまいます。
まず、ポイントの候補サブセットが既にあり、それらが直線上にあるかどうかを確認したい場合。線形回帰の形式を使用して最適な線を特定し、それがどの程度適合しているかを確認し、それに基づいてこの特定のセグメントが線形であるという仮説を受け入れるか拒否します。
これを行う最も標準的な方法の 1 つは、最小二乗法を使用することです。
サブセットを特定することは別の問題であり、最善の解決策は、所有しているデータの種類と目的に大きく依存します。データ量が極端に大きくない場合は、すべてのセグメントを列挙することが良い出発点になることをお勧めします。これは立方時間以内に実行できるはずです。
確かに適用できるいくつかの近似値があります。たとえば、シーケンス内のポイントを選択し、セグメントが許容しきい値内で線形のままである限り、どちらかの側にポイントを繰り返し追加することによってサブセットを構築します。セグメントが十分に長い場合にそれを受け入れるか拒否するよりも.
ここでは、曲線が座標の 1 つによってパラメーター化可能であると仮定します。そうでない場合、たとえば曲線が閉じている場合は、曲線をパラメータ化可能なセグメントに分割するために追加の手順が必要になる場合があります。
編集: セグメントがまっすぐであることを確認する方法 いくつか のオプションがあります。
まず、直線の場合、新しいポイントを追加しても平均偏差はほぼ同じであると予想されます。その後、データが与えられた場合に合理的なしきい値を簡単に見つけることができます。
2 番目のオプションは、サブセットをさらに固定数 (たとえば 2) の部分に分割し、それぞれに最適な線を見つけてからこれらを比較することです。直線の場合はほぼ同じラインが予測されるはずですが、曲線の場合は異なります。
3 番目のオプションは、非線形曲線フィッティングを実行することです。たとえば、2 次曲線をフィッティングし、2 次項の係数をチェックします。線が直線の場合、0 に近いはずです。
いずれの場合も、もちろん、セグメント サイズとそのセグメントからのポイントの偏差との間にはトレードオフがあります。極端な場合、偏差が非常に大きい 1 つの巨大な線形セグメントか、偏差が 0 の 2 点セグメント全体が存在します。偏差の実際のしきい値、正接曲線間の差、または 2 次項の大きさ (好みのオプションに応じて) を、必要に応じて特定のデータセットに対して選択する必要があります。プロットを見ると、長さ 10 程度のセグメントを許容するようにしきい値を選択する必要があると言えます。