3

我正在为一个游戏编写一个工具，该工具涉及计算 500 个单位的环形平面上两个坐标之间的距离。也就是说，[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 步，我们最好向后走 500-x 步。）

解决此问题的一种简单方法是

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

更新（环面）：

好的，从您自己的评论来看，您似乎确实指的是圆环 - 甜甜圈的表面 - 而不是球体。（这是一个很大的区别，你应该编辑你的问题：称它为球体是错误的。）

为此，答案相当简单——你给出的笛卡尔公式或多或少是正确的。但是，您需要环绕距离，以便任何大于或等于 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) 坐标如何映射到球体上的点！

（字面意思）有无数种选择，每种选择对应不同的地图投影，并且每种选择的公式都不同。请注意，无论您做出何种选择，这两个坐标的含义是非常不同的。

例如，如果您的 (x,y) 确实是经度和纬度，则有很多固定公式（即半正弦），但您必须首先将经度和 -90 的 0->499 转换为 0->360 度-> 90 度的纬度。（请注意，lon 和 lat 在球体上的行为非常不同！）

但我强调，如果你在 (x,y) 中绘制的平面几何图形与它在球体上的真实外观相比，你所做的任何选择都会扭曲。

（最后，如果你真的是说顶边和底边一样，右边和左边一样，那么你可能有一个圆环而不是一个球体！）

于 2011-01-02T11:48:56.863 回答
1

如果您知道两点的纬度和经度 - 您可以使用半正弦公式来计算球体上两点之间的距离。

但据我了解，您需要对几乎对映点准确的公式。Haversine 公式在这里失败。在这种情况下，您需要Vincenty 的公式，即使在对映的情况下也是准确的。

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

于 2011-01-02T11:37:07.880 回答
1

听起来您只是在使用“平铺”的特殊有限笛卡尔空间。在这种情况下，每个对象都没有唯一的位置。对于所有可能的整数值 i 和 j ，而不是 (x, y) 它是 (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

尽管这里的一些答案非常接近，但最终通过这个 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

该通用算法适用于直角坐标系或球坐标系中的非常排序的距离，但不适用于球坐标系。

我认为更好的方法是基于纬度和经度，如下所示：

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

如果两个坐标位于 OP 未要求的两端不相遇的二维平面中，我正在写答案。但它可能会在未来帮助某人。

如果您的点位于二维平面中，则点 (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 回答