Umopepisdn - 1 year ago 73
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?

Thanks,
-Umo

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.