私は2D座標セットのコレクション（各セットに100K〜500Kポイントのスケールで）を持っており、1つのセットと他のセットの類似性を測定する最も効率的な方法を探しています。私はいつものことを知っています：Cosine、Jaccard / Tanimotoなど。しかし、類似性を測定するための高速で効率的なもの、特に類似性によってクラスター化できるものについての提案を期待しています。
編集1：画像は私がする必要があることを示しています。すべての赤、青、緑を形や向きなどでクラスター化する必要があります。
K-meansアルゴリズムを試してください。各クラスターの重心を動的に計算し、すべてのポインターまでの距離を計算して、それらを最も近いクラスターに関連付けます。
解決策の最初のステップは、絶対位置に関係なく比較できるように、各形状の図心または他の基準点を見つけることであるように思われます。
頭に浮かぶアルゴリズムの1つは、図心に最も近い点から開始し、最も近い隣接点まで歩くことです。比較するセット間で、（重心からの）これらの隣接ノードのオフセットを比較します。重心の次に近い近傍、または以前に比較したものの最も近い未比較の近傍まで歩き続け、2つの形状間の総計の差（おそらくRMS？）を追跡します。また、このプロセスの各ステップで、2つの形状を最も近い位置に配置する回転オフセットを計算します[ミラーリングもそれに影響するかどうか]。終了すると、セットのペアごとに3つの値が得られます。これには、直接の類似性、相対的な回転オフセット（ほとんどの場合、回転後の類似性が高い場合にのみ役立ちます）、および回転後の類似性が含まれます。
クラスタリングは形状への近さのメトリックに基づいているため、おそらく何らかの形の連結成分のラベル付けが必要です。UNION-FINDは、高速な基本セットプリミティブを提供します。
ユニオンのみの場合は、異なるセットのすべてのポイントを開始し、ローカルの共直線性の影響を受けて、近接性の基準を満たしている場合はそれらをマージします。これは、それが重要であると思われるためです。次に、マージがどれほど難しいかというしきい値を超える条件を通過するまで、マージを続けます。それを線成長のように扱うと（それらの端で物事を結合するだけです）、いくつかのデータ構造はより単純になります。すべてのクラスターは直線と曲線を開いていますか？円のような閉じた曲線はありませんか？
交差線は正しく理解するのが難しいです。何らかの方法でマージしてから分割する必要があります。または、マージ基準を非常に共直線性を優先するように設定して、交差線を幸運にします。
