4

1 つの 2D ライン (ループなどを含む曲線でもかまいません) と、複数の同様のパスがあります。最初のパスと残りのパスを比較し、どれが最も類似しているかを判断したいと考えています (可能であればパーセンテージで)。

パスをビットマップに変換してから、ライブラリを使用してビットマップを比較することを考えていましたが、それはやり過ぎのようです。私の場合、点で構成された中断のないパスのみがあり、異なる色などはありません。

誰でも私を助けることができますか?

編集:

したがって、最初の行は黒い行です。他のすべての行をそれと比較します。赤い線は 90% 正確です (ほぼ同じ形をしており、黒い線に近いため)。青い線は 5% の正確さです - このパーセンテージはこの例のために作られています... - 形状は似ていますが、小さく、黒いパスに近くないためです。

したがって、類似性の基準は次のようになります。

  • 線が互いにどれだけ近いか
  • 彼らはどんな形をしていますか
  • 彼らはどれくらいの大きさですか

(色は問いません)

これらすべてを考慮したライブラリを見つけるのは不可能であることはわかっています。しかし、最も重要な比較は、形状とサイズが同じかどうかです。自分で計算できる距離。 ここに画像の説明を入力

4

1 に答える 1

5

2 つの線 N (点 p0、p1...pr 間の直線セグメントとして定義) M (q0、q1、...qs 間の直線セグメント) 間の類似性を表す 2 つの尺度を考えることができます。p0 と q0 は常に p0 と qs よりも近いと仮定します。

1) 面積

N と M で囲まれた面積の合計を使用します。N と M は、面積が大きくなるほど大きく異なります。N と M で閉じた形状を形成するには、p0 と q0 および pr と qs を直線セグメントで接続する必要があります。囲まれた領域の表面を計算できるようにするには、N と M のセグメント間の交点に新しい点を導入して、穴や自己交差のない 1 つ以上の単純な多角形を取得します。このような多角形の面積は比較的簡単に計算でき (Web で「多角形面積計算」を検索してください)、面積を合計すると、(非) 類似度の尺度が得られます。

2) サンプリング

N 上にある事前定義された数 (たとえば 1000) のサンプル ポイント O を取得します (ライン全体に対して等間隔、または N の各ライン セグメント上で等間隔)。O 内の各サンプル ポイント o について、M 上の最も近い対応するポイントまでの距離を計算します。結果は、これらの距離の合計です。次に、役割を逆にします。M からサンプル ポイントを取得し、N 上の最も近い対応する各ポイントを計算し、それらの距離を合計します。これら 2 つのうち最小の合計を生成するもの (それらは同じではない可能性があります!) が (非) 類似度の尺度です。
ノート: M 上の最も近い対応する点を見つけるには、M のすべての直線セグメントの最も近い点を見つけます (これは単純な代数です。Google で「点と直線セグメント間の最短距離」を検索します)。o までの距離が最も小さいセグメントの結果を使用します。

比較

方法 1 を実装するには、いくつかのジオメトリ プリミティブ (点、線分、ポリゴン) とそれらに対する操作 (交点やポリゴン領域の計算など) が必要です。これは手間がかかりますが、より堅牢な結果が得られ、多数の線分で構成される線の最適化が容易になります。

方法 2 では、「正確な」数のサンプル ポイントを選択する必要があります。これは、線に詳細がほとんどない部分と詳細が多い部分 (つまり、多数の線分が近接している) が交互にある場合は困難であり、その実装はすぐに実行される可能性があります。多数のサンプル ポイントを使用すると (非常に) 遅くなります (すべてのサンプル ポイントをすべての線分と照合するのは 2 次演算です)。利点として、多くの幾何学的操作を必要とせず、実装が比較的簡単です。

于 2013-09-12T19:53:04.757 に答える