3

500単位のトロイダル平面上の2つの座標間の距離を計算するゲーム用のツールを作成しています。つまり、[0,0]から[499,499]は有効な座標であり、[0,0]と[499,499]も互いに隣接しています。

現在、私のアプリケーションでは、ユーザーが事前に構成した[X、Y]の場所に対応する[X、Y]の場所を持つ都市間の距離を比較しています。

これを行うために、私はこのアルゴリズムを見つけました。

Math.sqrt ( dx * dx + dy * dy );

ページリストを距離で並べ替えることは便利なことなので、このアルゴリズムをMySQLクエリに実装し、SELECTステートメントの次の部分を使用してアプリケーションで使用できるようにしました。

SQRT( POW( ( ".strval($sourceX)." - cityX ) , 2 ) + POW( ( ".strval($sourceY)." - cityY ) , 2 ) ) AS distance

これは多くの計算で問題なく機能しますが、[0,0]と[499,499]が互いにキティコーナーであるという事実を考慮していません。

0と499が隣接している場合、このアルゴリズムを微調整して正確な距離を生成する方法はありますか？

4

7 に答える 7

7

座標を折り返すことを意味し、球形のものは何もないと思います。端が魔法のように互いに接続されている平らな紙のように。

つまり、500x500のサイズの地図の場合、x（またはy）方向の距離は最大で250です（250ステップを超える場合は、500xステップ後方に歩く方がよいでしょう）。

これを修正する簡単な方法は、

dx = Math.abs(dx);
dy = Math.abs(dy);
if (dx > 250)
  dx = 500 - dx;
if (dy > 250)
  dy = 500 - dy;
distance = Math.sqrt ( dx * dx + dy * dy );
于 2011-01-02T11:33:03.213 に答える
5

更新（トーラス）：

OK、あなた自身のコメントから、あなたはトーラス（ドーナツの表面）を意味しているように見えますが、球ではありません。（これは大きな違いであり、質問を編集する必要があります。球と呼ぶのは間違っています。）

このため、答えはかなり単純です-あなたが与えるデカルト式は多かれ少なかれ正しいです。ただし、250 = 500/2以上のものが0〜250に変換されるように、距離をラップする必要があります。

したがって、答えは次のようになります（PHPはまったくわからないので、構文を変更する必要があるかもしれません）

dx1 = min(dx, 500-dx)
dy1 = min(dy, 500-dy);
distance = Math.sqrt(dx1*dx1 + dy1*dy1);

（これは、dxとdyを差の絶対値として定義したことを前提としています。）

うまくパッケージ化された関数で同じ計算を実装するこのルーチンを見つけました。

元の回答（球）：

（x、y）座標が球上の点にどのようにマッピングされるかを説明していません！

（文字通り）選択肢は無限にあり、それぞれが異なる地図投影法に対応しており、式はそれぞれ異なります。どの選択を行っても、2つの座標の意味は大きく異なることに注意してください。

たとえば、（x、y）が実際に経度と緯度である場合、定型式（つまり、半正矢関数）はたくさんありますが、最初に経度と-90を0->499から0->360度に変換する必要があります。 -緯度は90度を超えます。（lonとlatは、球上で非常に異なる動作をすることに注意してください！）

ただし、（x、y）でプロットした場合に得られるフラットなジオメトリと、球上で実際に見える方法では、どのような選択を行っても歪むことを強調します。

（最後に、上端が下端と同じで、右が左と同じであることを本当に意味する場合は、球ではなくトーラスがある可能性があります！）

于 2011-01-02T11:48:56.863 に答える
1

2点の緯度と経度がわかっている場合は、半正矢関数を使用して、球上の2点間の距離を計算できます。

しかし、私が理解したように、ほぼ対蹠点に対して正確な式が必要です。半正矢関数はここで失敗します。このような場合、対蹠の場合でも正確なVincentyの式が必要です。

http://en.wikipedia.org/wiki/Great-circle_distance#Formulae

于 2011-01-02T11:37:07.880 に答える
1

「タイル張り」の特別な有限デカルト空間を使用しているように聞こえます。この場合、各オブジェクトには一意の位置がありません。（x、y）の代わりに、すべての可能な整数値iとjに対して（x + i * w、y + j * h）であり、ここでwとhはそれぞれ「ウィンドウ」の幅と高さです。

明らかに、距離は一意ではありませんが、最小距離は、すべてのi、jにわたってmin（d（p1、p2）））です。

座標がラップされている場合は、i=-1,0,1およびj=-1,0,1について計算し、最小のものを使用する必要があります。

于 2011-01-02T21:48:05.437 に答える
0

この一般的なアルゴリズムは、球面座標系または球面座標での非常にソートされた距離には適していますが、球面座標系には適していません。

より良いアプローチは、次のように緯度と経度に基づくと思います。

http://jan.ucc.nau.edu/~cvm/latlongdist.html

MySQLにはジオコーディングが組み込まれています。使ってみませんか？

http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

于 2011-01-02T11:09:29.487 に答える
0

ここでの回答のいくつかは非常に近いものでしたが、問題はこのSELECTセグメントで最終的に解決されました。

SQRT( POW( LEAST( ABS($sourceXstr-cityX), ( 500 +LEAST($sourceXstr,cityX)-GREATEST($sourceXstr,cityX))) , 2 ) + POW( LEAST( ABS($sourceYstr-cityY), ( 500 +LEAST($sourceYstr,cityY)-GREATEST($sourceYstr,cityY))) , 2 ) ) AS distance

于 2011-01-08T11:38:29.347 に答える
0

OPが求めていない2つの座標が2次元平面にあり、両端が互いに一致していない場合、私は答えを書いています。しかし、それは将来誰かを助けるかもしれません。

点が2次元平面にある場合、点（x1、y1）と（x2、y2）の間の距離は、ピタゴラスの定理によって与えられます。

ピタゴラスの公式

d = squareroot( square(x2 - x1) + square(y2 - y1) )

PHPでは、

$x1 = $y1 = 2;
$x2 = $y2 = 5;
$distance = sqrt( pow(($x2-$x1),2) + pow(($y2-$y1),2) );
echo $distance;              // 4.2426406871193
于 2016-07-27T09:20:50.900 に答える