8

edit 誰かが指摘したように、私が探しているのは、実際には他のすべてのポイント間の合計測地線距離を最小化するポイントです

私のマップは、パックマンやアステロイドのものと地形的に似ています. 上を過ぎると下にワープし、左を過ぎると右にワープします。

マップ上に (同じ質量の) 2 つのポイントがあり、それらの重心を見つけたいとします。基本的にmidpointである従来の定義を使用できます。

ただし、2 つの点が質量の反対側にあるとします。いわば、「周りを包む」ことによって形成される別の重心があります。基本的に、それは他の両方のポイントから等距離にあるポイントですが、エッジを「ラップアラウンド」することでリンクされています。

例

b . O . . a . . O .

2点O。それらの「古典的な」中点/重心は、 とマークされた点aです。ただし、別の中点もb(bは、ラップアラウンドにより、両方の点から等距離にあります) にあります。

私の状況では、2 点間の平均距離が短い方を選択したいと考えています。この場合、a3 つのステップの 2 点間の平均距離があります。 bの平均距離は 2 歩です。だから私は選ぶだろうb。

2 点の状況を解決する 1 つの方法は、単純に従来の中点と最短のラップアラウンド中点の両方をテストし、平均距離が短い方を使用することです。

でも！これを 3 点、4 点、5 点、またはn点に簡単に一般化することはできません。

これを見つけるために使用できる数式またはアルゴリズムはありますか?

(すべての点が常に等しい質量であると仮定します。私がやろうとしていることを大まかに説明するために知っていた唯一の用語であるため、「重心」のみを使用します)

私の説明が不明確な場合は、より適切に説明しようとします。

4

4 に答える 4

4

重心の概念は、アフィン空間に関連する概念です。n 次元トーラスにはアフィン構造がありません。

必要なのは、他のすべてのポイントまでの (測地線) 距離を最小化するポイントです。

私は次のことを提案します: x_1...x_n を d 次元のトーラス (またはその目的のための他の距離空間) 上の点の集合とします。

あなたの問題：

sum(dist(mu, x_k)^2) が最小になるような点 mu を見つけます。

アフィン・ユークリッドの場合、通常の重心の概念が得られます。

これは、この場合にうまく機能する共役勾配アルゴリズムを使用して解決できる問題です (たとえば、おそらくより良いオプションがあります) 。アルゴリズムは空間に n^2 、時間に n^3 を必要とするため、適度な n (たとえば n < 10^3)​​ が必要であることに注意してください。

おそらく、平方和の最小化に合わせて調整されたレーベンバーグ・マルカート アルゴリズムの方が適しています。

適切な初期推定 (たとえば、トーラスではなく R^d 内の点として見られる点の通常の重心) がある場合、この方法はより速く収束することに注意してください。

編集: (x1...xd) と (y1...yd) がトーラス上の点である場合、距離は dist(x, y)^2 = alpha1^2 + ... + alphad^2 で与えられます

ここで、alphai = min((xi - yi) mod 1, (yi - xi) mod 1)

于 2010-09-14T11:18:55.140 に答える
3

関連する関数の良さをチェックする小さなプログラムを作成したところ、最小化プロセスには細心の注意を払う必要があることがわかりました。

以下に、点の分布、ユークリッドのケースで最小化する関数、および「トーリック メトリック」に対応する関数を示す 2 つのプロット セットを示します。

代替テキスト

おわかりのように、ユークリッド距離は非常に適切に機能しますが、トーリックは、グローバル ミニマムの発見を困難にするいくつかのローカル ミニマムを示します。また、トーリックの場合のグローバル最小値は一意ではありません。

念のため、Mathematica のプログラムは次のとおりです。

Clear["Global`*"];

(*Define  non wrapping distance for dimension n*)
nwd[p1_, p2_, n_] := (p1[[n]] - p2[[n]])^2;

(*Define wrapping distance for dimension n *)
wd[p1_, p2_, max_,n_] := (max[[n]] - Max[p1[[n]], p2[[n]]] + Min[p1[[n]], p2[[n]]])^2;

(*Define minimal distance*)
dist[p1_, p2_, max_] :=
  Min[nwd[p1, p2, 1], wd[p1, p2, max, 1]] +
  Min[nwd[p1, p2, 2], wd[p1, p2, max, 2]];

(*Define Euclidean distance*)
euclDist[p1_, p2_, max_] := nwd[p1, p2, 1] + nwd[p1, p2, 2];

(*Set torus dimensions *)
MaxX = 20; 
MaxY = 15;

(*Examples of Points sets *)
lCircle = 
  Table[{10 Cos[fi] + 10, 5 Sin[fi] + 10}, {fi, 0, 2 Pi - .0001, Pi/20}];

lRect = Join[
   Table[{3, y}, {y, MaxY - 1}],
   Table[{MaxX - 1, y}, {y, MaxY - 1}],
   Table[{x, MaxY/2}, {x, MaxY - 1}],
   Table[{x, MaxY - 1}, {x, MaxX - 1}],
   Table[{x, 1}, {x, MaxX - 1}]];

(*Find Euclidean Center of mass *)
feucl = FindMinimum[{Total[
    euclDist[#, {a, b}, {MaxX, MaxY}] & /@ lRect], 0 <= a <= MaxX, 
             0 <= b <= MaxY}, {{a, 10}, {b, 10}}]

(*Find Toric Center of mass *)
ftoric = FindMinimum[{Total[dist[#, {a, b}, {MaxX, MaxY}] & /@ lRect],
         0 <= a <= MaxX, 0 <= b <= MaxY}, {{a, 10}, {b, 10}}]
于 2010-09-15T21:23:04.440 に答える
2

1 次元の場合、問題は平均角度を見つけることに似ています。角度 a と b の平均は次のように計算できます。

平均 = 剰余( a + 剰余( ba, C)/2.0, C) ここで、C は円全体の測定値です (つまり、ラジアンを使用している場合は 2*PI)。

n 個の角度 a[] がある場合、平均は次のように計算できます。

意味 = [0]; for i=1..n 平均=剰余( 平均 + 剰余( a[i]-平均, C)/(i+1), C)

だから私は計算します

meanX = X[0]; 平均Y = Y[0]

i=1..n の場合

 meanX = remainder( meanX + remainder( X[i]-meanX, W)/(i+1), W)
 meanY = remainder( meanY + remainder( Y[i]-meanY, H)/(i+1), H)

仕事をするかもしれません。

ただし、これは -W/2<=meanX になることに注意してください

于 2010-09-14T11:18:31.323 に答える
0

IANAトポロジロジスト、そして私がこれで自分自身をどれだけ明確にしているかはわかりませんが、価値があるので、これらは問題に関するいくつかの考えです:

質量と重力を使用してこの種のものを計算することは、実際にはエレガントかもしれません.ISTRは、多数のライブラリと、任意の数の質量の重力ベクトルを見つけるための効率的なアルゴリズムがあることを示しています。

球面マップを使用している場合は、球内で N 質点の実際の重心を見つけることをお勧めします。次に、この内側の重心を中心から外側に向かって線を引き、質量点が集まりたい球の表面上の点を見つけます。

ただし、トロイダル マップではこれが難しくなります。

私の提案は、マップを平坦化してコピーし、3 x 3 のマップのキルトを作成することです (マップの無限フィールドを使用すると、より良い結果が得られますが、やり過ぎになる可能性があります)。座標 (0, 0) から (2, 2) を割り当てます。(1, 1) がソース マップです。内側のマップ (1, 1) の質点が引き付けられるポイントを見つけます。それらがすべてマップの中央に向かっている場合は、問題ありません。重心を見つけたことになります。そうでない場合、エッジに近いポイントの 1 つが内側のマップの外側、たとえばマップ (2, 1) の質量蓄積に向かっている場合、重心を計算するときにこの質量ポイントを破棄します。代わりに、反対側のマップ (この場合は (0, 1)) の質点を使用して、中央のマップに移動します。

これらの質点の加速度ベクトルを追加すると、トーラスの重心が得られます。終わり。

于 2010-09-14T11:04:29.883 に答える