Calculating distance between two X, Y coordinates in PHP

Question

I am writing a tool for a game that involves calculating the distance between two coordinates on a toroidal plane 500 units across. That is, [0,0] through [499,499] are valid coordinates, and [0,0] and [499,499] are also right next to each other.

Currently, in my application, I am comparing the distance between a city with an [X,Y] location respective to the user's own [X,Y] location, which they have configured in advance.

To do this, I found this algorithm, which kind of works:

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

Because sorting a paged list by distance is a useful thing to be able to do, I implemented this algorithm in a MySQL query and have made it available to my application using the following part of my SELECT statement:

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

This works fine for many calculations, but does not take into account the fact that [0,0] and [499,499] are kitty-corner to one another.

Is there any way I can tweak this algorithm to generate an accurate distance, given that 0 and 499 are adjacent?

Answer 1

I assume you mean wrapping coordinates and nothing spherical shaped. Like a flat piece of paper where the ends are magically connected to each other.

That means that for a map sized 500x500, the distance in the x (or y) direction is at most 250. (If it would be more than 250 steps, we could better walk 500-x steps backward.)

A simple way to fix this, would be

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 );

Answer 2

Update (torus):

OK, from your own comments, it seems that you do mean the torus -- the surface of a donut -- and not the sphere. (This is a big difference, and you should edit your question: calling it a sphere is wrong.)

For this, the answer is fairly simple -- the cartesian formula you give is more or less correct. However, you need to wrap distances around so that anything greater than or equal to 250=500/2 gets translated down to between 0 and 250.

So the answer is something like (I don't know PHP at all, so this may need to be modified for syntax)

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

(This assumes that you have defined dx and dy to be the absolute value of the differences.)

Just found this routine which implements the same calculation in a nicely-packaged function.

Original Answer (sphere):

You haven't explained how your (x,y) coordinates map to points on the sphere!

There are (literally) an infinite number of choices, each corresponding to a different map projection, and the formula is different for each of them. Note that no matter what choice you make, the meaning of the two coordinates is very different.

If your (x,y) are really longitude and latitude, for example, there are plenty of canned formulae (i.e., haversine) but you'll have to first translate 0->499 to 0->360 degrees for longitude and -90->90 degrees for latitude. (Note that lon and lat behave very differently on the sphere!)

But I emphasize that any choice you make will distort from the flat geometry that you get if you plot in (x,y) versus the way it really looks on the sphere.

(Finally, if you really mean that the top edge is the same as the bottom and the right the same as the left, then you probably have a torus and not a sphere!)

Answer 3

If you know latitude and longitude of two points - you could use haversine formula to compute distance between two points on sphere.

But as I understood you want formula which is accurate for nearly antipodal points. Haversine formula fails here. In such case you need Vincenty's formula which is accurate even in antipodal cases.

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

Answer 4

It sounds like you are simply using a special finite Cartesian space that is "tiled". In this case each object does not have a unique position. Instead of (x, y) it is (x + i*w, y + j*h) for all possible integer values i and j and where w and h are the widths and heights of your "window" respectively.

Obviously then the distance is not unique but the minimum distance is which is just min(d(p1,p2))) over all i, j.

If your coordinates are wrapped then you just need to compute it for i=-1,0,1 and j=-1,0,1 then take the smallest one.

Answer 5

I am writing answer if two coordinates are in 2 dimensional plane where ends are not meeting each other which OP has not asked. But it might help someone in future.

If your points are in a 2 dimensional plane, the distance between points (x1, y1) and (x2, y2) is given by the Pythagorean theorem:

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

In PHP,

$x1 = $y1 = 2;
$x2 = $y2 = 5;
$distance = sqrt( pow(($x2-$x1),2) + pow(($y2-$y1),2) );
echo $distance;              // 4.2426406871193

Answer 6

That general algorithm is fine for rectangular coordinate systems or very sort distances in spherical coordinates, but it's not appropriate for a spherical coordinate system.

I think a better approach would be based on latitude and longitude, like this:

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

MySQL has geo-coding built into it. Why not use that?

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

Answer 7

Although some of the answers here were very close, the problem was finally solved with this SELECT segment:

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