Optimizing Distance Calculation (lon/lat), Optimizing Trig

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
akreider
Forum Commoner
Posts: 46
Joined: Mon May 22, 2006 3:54 pm
Location: USA

Optimizing Distance Calculation (lon/lat), Optimizing Trig

Post by akreider »

I'm working on a script that I'll release as open source for generating a Heat Map for google maps.

Coal Plants Example:
http://www.energyjustice.net/map/server ... ample.html

I divide the lower-48 states of the US into grid squares. Then I calculate the distance between the center point of a grid square at each facility (in my case coal power plant). The heat is proportional to the MW of the power plant / (distance*distance).

The problem is that I want high resolution. If I divide the US into mile by mile squares, and have 500 power plants - then I have around 2 billion distance calculations. I'm running this on a windows vista computer, wampserver, apache/mysql/php, with an Intel Q6600 - and high resolution can take several hours to a day.

Here is my distance formula:
function getDistanceBetweenPointsNew($latitude1, $longitude1, $latitude2, $longitude2, $fLat1_sin, $fLat1_cos, $fLat2_sin, $fLat2_cos)
{
$theta = $longitude1 - $longitude2;
$distance = ($fLat1_sin * $fLat2_sin) +
($fLat1_cos * $fLat2_cos *
cos(deg2rad($theta)));
$distance = acos($distance);
return ($distance);
}

I pre-calculate as many of the sin/cos as I can - so that they are only done once per grid point or per facility. However there are some values that I cannot precalculate.

I removed the actual calculation of distance: $distance=69.09 * rad2deg($distance)
As my algorithm works fine with relative distances.

I tried creating a trig lookup table so I wouldn't have to use the trig functions, but that wasn't any faster. Is the rounding function as slow as sin or cos? I had to round the values before I could use the lookup.

Could I get PHP to spawn 3 other processes, so I'd use all four of my cpu cores?
(Or should I do it with javascript?)

Could I get PHP to trade accuracy for speed? I''ve considered using a non-trig distance function (aka pythagoras), however that would be too inaccurate. My guess is that PHP is using floats with lots of decimal places, and I don't need that much accuracy.

Would it be a lot faster in another programming language?

What can I do to dramatically improve the speed?
akreider
Forum Commoner
Posts: 46
Joined: Mon May 22, 2006 3:54 pm
Location: USA

Re: Optimizing Distance Calculation (lon/lat), Optimizing Tr

Post by akreider »

Small improvements
-Replace deg2rad with multiply by 0.017453292.
-Got rid of the function call - so I internalized the code for calculating the distance inside the loop. This really helped.
akreider
Forum Commoner
Posts: 46
Joined: Mon May 22, 2006 3:54 pm
Location: USA

Re: Optimizing Distance Calculation (lon/lat), Optimizing Tr

Post by akreider »

One possibility is to replace the sin/cos functions with approximations:

http://www.devmaster.net/forums/showthread.php?t=5784

(Though this doesn't work for acos)

I tried the approximation for cos() and it was actually 5-20% slower.

So my latest function is:
$theta = $fLon1 - $fLon2;
$distance = ($fLat1_sin * $fLat2_sin) +
($fLat1_cos * $fLat2_cos *
cos(0.017453292*$theta));
$fDistance = acos($distance);
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Optimizing Distance Calculation (lon/lat), Optimizing Tr

Post by Eran »

All sine / cosine calculations are approximations, it's just a matter of precision. If you want a real performance benefit you should probably forget about those micro-optimizations and implement this in C.
Post Reply