algorithm - 線分の集合の最適交点?

Question

すべてが 1 点で交差するはずの 2D 線分が多数ありますが、計算の早い段階で削減できないノイズのために交差しません。

すべての線分の交点の最適な近似を計算するアルゴリズムはありますか。必ずしもどの線分にもあるとは限らない、すべての線分への平均距離が最小の点のようなものですか?

Answer 1

アミットからの最初のコメントはあなたの答えです。その理由を説明します。

p_iあなたの交点としましょうc = 1/n sum(p_i)。と任意の点の間のc平均距離を最小化することを示しましょう：d(a)p_ia

d(a) = 1/n sum( |a-p_i|^2 )  

平均化されているのd(a)は、内積表記を使用して、

|a-p_i|^2 = <a-p_i, a-p_i> = |a|^2 + |p_i|^2 - 2<a,p_i>`

の平均は、内積の双線形プロパティを使用して、<a,p_i>ちょうどです。<a,c>それで、

d(a) = |a|^2 - 2<a,c> + 1/n sum( |p_i|^2 )

そして同様に

d(c) = |c|^2 - 2<c,c> + 1/n sum( |p_i|^2 ) = -|c|^2 + 1/n sum( |p_i|^2 )

2つを引く

d(a) - d(c) = |a|^2 - 2<a,c> + |c|^2 = |a-c|^2

したがって、d(c)両側に追加すると、任意のポイントまでの平均距離は次のようになりますa。

d(a) = d(c) + |a-c|^2

これは、すべての項が正であるため、|a-c|^2がゼロの場合、つまり。の場合に最小化されa = cます。

Answer 2

メトリクスを自由に選択できる場合、距離の二乗和から簡単なアルゴリズムが得られる場合があります。

点座標の関数として線 #i までの距離の 2 乗を表すことができます(A[i]x,x)+(b[i],x)+c[i]。A[i]は行列 3x3、b[i]- ベクトル、c[i]- 数値、(a,b) - スカラー乗算です。

それらの合計は になります(A[sum]x,x)+(b[sum],x)+c[sum]。

そのような関数の最小値はx=-inverse(A[sum])b[sum]/2です。