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 次演算です)。利点として、多くの幾何学的操作を必要とせず、実装が比較的簡単です。