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?
Optimizing Distance Calculation (lon/lat), Optimizing Trig
Moderator: General Moderators
Re: Optimizing Distance Calculation (lon/lat), Optimizing Tr
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.
-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.
Re: Optimizing Distance Calculation (lon/lat), Optimizing Tr
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);
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);
Re: Optimizing Distance Calculation (lon/lat), Optimizing Tr
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.