Umopepisdn Umopepisdn - 1 year ago 51
MySQL Question

Calculating distance between two X,Y coordinates

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 Source

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