編集:タイトルを変更しました。2 つのセグメントが同じであることにはあまり関心がありませんが、特定の許容範囲内で互いに同一線上にある場合はそうです。その場合、線は 1 つのセグメントとしてまとめてクラスター化する必要があります。
編集:これを簡単に言うと、同様の線分を効率的な方法でまとめようとしています。
線分があるf
(fx0, fy0)
とします(fx1, fy1)
and and and g
(gx0, gy0)
and(gx1, gy1)
これらは、コンピューター ビジョン アルゴリズムのエッジ検出器のようなものから得られます。場合によっては、2 つの線は基本的に同じですが、ピクセル許容誤差のために 2 つの異なる線としてカウントされます。
いくつかのシナリオがあります
f
g
まったく同じエンドポイントを共有します。例:f = (0,0), (10,10) g = (0,0), (10,10)
f
g
ほぼ同じエンドポイントとほぼ同じ長さを共有します。たとえば、次のようになります。f = (0,0.01), (9.95,10) g = (0,0), (10,10)
f
は のサブセットですg
。つまり、その終点はセグメント内にあり、g
セグメントと同じ勾配を共有しg
ます。ペンを前後に動かして太くしたラフな線を考えてみてください。例:f = (4.00, 4.02), (9.01, 9.02) g = (0,0), (10,10)
以下は同じとは見なされません。
f
g
一定以上の勾配差があるtolerance
f
とg
は同じ勾配を持っているかもしれませんが、 を超える距離だけ離れていますtolerance
。つまり、平行線です。f
とg
同じ平面と同じ勾配にありますが、まったく重なっていません...つまり、破線内の一連のセグメントです。
それらが同じかどうかを判断する最も簡単な方法は、if gx1 - fx1 <= tolerance
(他の 3 つの点について繰り返します) ですが、場合によっては、線が線f
よりも短い場合がありますg
(これも、ピクセルの違いや写真のスキャンが不十分なためです)。
では、2 つの線分を極座標に変換して角度を比較したほうがよいのでしょうか? その場合、2 つの rho は許容範囲内になります。ただし、2 つの線分が同じ「方向」を持っていることを確認する必要があります。これは、デカルト座標または極座標で計算するのは簡単です。
これは方法を理解するのは簡単ですが、私が長い間忘れていた線形代数に基づいた、よりクリーンな方法があるかどうか疑問に思っています。