Howfar It Is from Here to There

My redistricting algorithm selects census blocks based on their distance from the district center. The coordinates of the district center and of the next census block are given in latitude and longitude integer tenmillionths degrees. Of the many methods to calculate that distance, which is best?

A first method assumes the earth is flat, and calculates a hypotenuse using the Pythagorean equation of the square root of the sum of the squares. The calculation is reasonably quick, but is accurate only for very small distances.
A second method assumes the earth is a sphere, and uses spherical trigonometry. Because the answer comes from taking the arccosine, the accuracy is impaired for very small distances.
A third method that must have been used by my Grandfather uses haversines, which was developed to avoid being impaired for small distances. This method also assumes the earth is a sphere, and uses spherical trigonometry. Unfortunately, the greater complexity of this method means that a greater amount of computer time would be needed to do each calculation.
A fourth method used by the Federal Communications Commission in 47CFR73.208 is to multiply the horizontal and vertical distances by correction factors, then calculate the hypotenuse using the square root of the sum of the squares. The FCC specified that this method was only good up to 475 kilometers. I had hoped that this distance limit was imposed based on the interested distance of signal wave propagation, and that the method was actually good for greater distances. After playing with the numbers, that hope is dimmed.
Other methods exist today that are splendidly accurate, but recursively complex, meaning too much computer time would be needed for my purposes.

To meet my goal of quickness, I tried to use a different method similar to the fourth method. Instead of calculating the correction factors by a trigonometric Taylor series, use a lookup table. The table lists for every positive integer degree of latitude: a horizontal correction factor and a vertical correction factor. To improve accuracy, simple linear interpolation is used. I fudged together a table for a distance range up to 2000 kilometers. The resulting accuracy for this method was only under 1000 parts per million. The biggest contribution to error seems to be the difference between the assumed corrected shape and the actual shape of planet Earth.

Perhaps trading off some quickness to gain accuracy would be a good idea. If most distances are short, then the lookup table could be used for quickness. For longer distances, the second method taking the arccosine could be used to maintain accuracy. To decide whether the distance is short or long, get a really rough distance based on my blog of October 2010. Since the correction factors in the current table were meant to cover up to 2000 kilometers, a new table is needed calibrated to shorter distances. How much shorter depends on the cross over range between short and long, which should also be determined carefully for the best trade-off between quickness and accuracy.

The problem then is to write a new FORTRAN howfar function with a crossover and create a new table of correction factors. To save time and improve accuracy, one way to solve the problem would be to write a computer program specific to the task. The technique of writing a robot computer program whose purpose is computer programming is not new. Although the computer programming is FORTRAN, another computer language such as BASIC could be used for the robot computer program. I prefer interpreted instead of compiled, and high-level language to lower level language. Presumably, it would be best for other people though if FORTRAN was also used for the robot computer program.

The robot computer program could set the vertical distance to zero. The actual distance can be computed, for example by modifying {http://geographiclib.sourceforge.net/html/Fortran/index.html}. Substituting into the FCC equation will yield a value for a horizontal correction factor. It is similar in shape to the cosine, and the interpolation line is below the curve. Therefore the error due to the cosine curve is plus. Adding slightly to the horizontal correction factor can reduce that error magnitude by making that cosine curve error plus and minus. Rounding should be done to the horizontal correction factor to better match the actual accuracy. Accuracy calculations could set the crossover range.

Reality of course is that because of limited time, I will simply ignore this problem. I am still ignoring writing a cake cutter algorithm, and that has higher priority. The summer of California’s dangerous drought and wicked wildfires is finally winding down, and Silicon Valley actually had light rain. Time to prepare for whatever winter may bring.

Advertisements

Post a Comment

Required fields are marked *

*
*

%d bloggers like this: