http://qs321.pair.com?node_id=866607

Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All,
Late last night, I had the task of determining the distance between two points identified by longitude and latitude in decimal degrees. I immediately installed Geo::Distance because I clearly remember it being recommended here or on #perl (Freenode) anytime someone asks how to solve this problem. I wrote a simple test script and then went to google driving directions to verify. The distance from BWI airport to LAX was off by about 220 miles. Since roads are not straight (or great arcs), I knew they would not be exact. What surprised me though was that google actually showed the shorter distance. The module provides several methods for calculating distance but they were all off and some by even more.

After asking around what the problem might be, I had two possibilities. The first was that google better understood that the earth wasn't a perfect sphere and the other (thanks to tye) was that Geo::Distance was lousy at what it claimed to do. After doing some quick calculations by hand using the Great-circle_distance method, I agreed with tye.

In further reading the documentation, I realized I had missed the great big decommissioned sign which said new development should be done using GIS::Distance. I am pretty sure (but not positive) that it gave the correct response but after waiting for 10 minutes or more for it to install, I realized it was too heavy weight for something that should be fairly trivial.

I was able to get through my project, thanks in large part to tye sharing his quick implementation, but I am left wondering - what do other people use for this? Does the author know the values are so far off? I checked the open bug reports but I didn't see anything. Why should something that should be simple be so hard?

Update: I made a bonehead mistake and I am an idiot.I should not write code while up late at night and pressed for time. I swapped long/lat. This was further complicated by tye's method having in the same order as I was using which produces the correct result. I need to have my JAPH card revoked. Please forgive my gigantic stupidity.

Cheers - L~R

Replies are listed 'Best First'.
Re: Alternatives To Geo::Distance (hack)
by tye (Sage) on Oct 21, 2010 at 19:22 UTC

    Just for reference, here is the quick and dirty implementation I threw together after consulting several pages at Wikipedia:

    sub acos { atan2( sqrt(1-$_[0]*$_[0]), $_[0] ) } sub asin { atan2( $_[0], sqrt(1-$_[0]*$_[0]) ) } my $pi= atan2(0,-1); my @c= ( 33.943603, -118.408189, 39.17965, -76.668824 ); my $lat1= $c[0]/180*$pi; my $lat2= $c[2]/180*$pi; my $dlong= ($c[1]-$c[3])/180*$pi; my $ang= acos( sin($lat1)*sin($lat2) + cos($lat1)*cos($lat2)*cos($dlong) ); my $max= $ang * 3_963.19059; my $min= $ang * 3_949.90257; printf "%.1f .. %.1f miles (%.2f range)\n", $min, $max, $max-$min; my $h1= sin(($lat1-$lat2)/2); my $h2= sin($dlong/2); $ang= 2*asin( sqrt( $h1*$h1 + cos($lat1)*cos($lat2)*$h2*$h2 ) ); $max= $ang * 3_963.19059; $min= $ang * 3_949.90257; printf "%.1f .. %.1f miles (%.2f range)\n", $min, $max, $max-$min; __END__ 2318.6 .. 2326.4 miles (7.80 range) 2318.6 .. 2326.4 miles (7.80 range)

    And if somebody tells you that a >10% error is due to Earth being an oblate spheroid, tell them that such a discrepancy would be less than 0.34%.

    - tye        

      It seems to rapidly screw up as you move north.

      The distance from (0,0)-(10,10) should be the same as from (80,0)-(90,10) as shown by the Geo::Distance output. Or should it?

      [0,0][10,10] geo: 974.731395416589 972.5 .. 975.7 miles (3.27 range) 972.5 .. 975.7 miles (3.27 range) [10,0][20,10] geo: 974.731395416589 957.7 .. 960.9 miles (3.22 range) 957.7 .. 960.9 miles (3.22 range) [20,0][30,10] geo: 974.731395416589 929.4 .. 932.5 miles (3.13 range) 929.4 .. 932.5 miles (3.13 range) [30,0][40,10] geo: 974.731395416589 889.9 .. 892.9 miles (2.99 range) 889.9 .. 892.9 miles (2.99 range) [40,0][50,10] geo: 974.731395416589 842.7 .. 845.5 miles (2.84 range) 842.7 .. 845.5 miles (2.84 range) [50,0][60,10] geo: 974.731395416589 792.8 .. 795.5 miles (2.67 range) 792.8 .. 795.5 miles (2.67 range) [60,0][70,10] geo: 974.731395416589 746.2 .. 748.7 miles (2.51 range) 746.2 .. 748.7 miles (2.51 range) [70,0][80,10] geo: 974.731395416589 709.6 .. 712.0 miles (2.39 range) 709.6 .. 712.0 miles (2.39 range) [80,0][90,10] geo: 974.731395416589 689.4 .. 691.7 miles (2.32 range) 689.4 .. 691.7 miles (2.32 range)

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
        The distance should go down closer to the pole. (90,10) and (90,0) are the same point.

        If you start at the north pole and walk one mile to the south and then one mile to the west you are still one mile to the south of the north pole. At the equator you will get a hypotenuse.

Re: Alternatives To Geo::Distance
by gray (Beadle) on Oct 21, 2010 at 23:52 UTC

    Speaking as the author of Geo-Distance-XS, I consider it to be actively developed. Even though Geo-Distance might be considered decommissioned by it's author, he probably will accept patches via its github repo. As will I for Geo::Distance::XS at its its repo.

    A good reason to use Geo::Distance::XS:

    ---- [ Formula: hsin ] ------------------------------------ perl - distance from BWI to LAX: 2324.06319758555 miles xs - distance from BWI to LAX: 2324.06319758555 miles gis::fast - distance from BWI to LAX: 2324.06319758555 miles Benchmark: running gis::fast, perl, xs for at least 1 CPU seconds... gis::fast: 1 wallclock secs ( 1.05 usr + 0.01 sys = 1.06 CPU) @ 23 +866.04/s (n=25298) perl: 1 wallclock secs ( 1.05 usr + 0.00 sys = 1.05 CPU) @ 78 +019.05/s (n=81920) xs: 2 wallclock secs ( 1.12 usr + -0.01 sys = 1.11 CPU) @ 12 +45236.94/s (n=1382213) Rate gis::fast perl xs gis::fast 23866/s -- -69% -98% perl 78019/s 227% -- -94% xs 1245237/s 5118% 1496% -- ---- [ Formula: polar ] ------------------------------------ perl - distance from BWI to LAX: 2652.59252292455 miles xs - distance from BWI to LAX: 2652.59252292455 miles gis::fast - distance from BWI to LAX: 2652.59252292455 miles Benchmark: running gis::fast, perl, xs for at least 1 CPU seconds... gis::fast: 1 wallclock secs ( 1.08 usr + 0.00 sys = 1.08 CPU) @ 18 +962.96/s (n=20480) perl: 1 wallclock secs ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 80 +736.45/s (n=86388) xs: 2 wallclock secs ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 15 +09051.75/s (n=1720319) Rate gis::fast perl xs gis::fast 18963/s -- -77% -99% perl 80736/s 326% -- -95% xs 1509052/s 7858% 1769% -- ---- [ Formula: cos ] ------------------------------------ perl - distance from BWI to LAX: 2324.06319758555 miles xs - distance from BWI to LAX: 2324.06319758555 miles gis::fast - distance from BWI to LAX: 2324.06319758555 miles Benchmark: running gis::fast, perl, xs for at least 1 CPU seconds... gis::fast: 1 wallclock secs ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 23 +642.99/s (n=25298) perl: 1 wallclock secs ( 1.06 usr + 0.00 sys = 1.06 CPU) @ 77 +282.08/s (n=81919) xs: 0 wallclock secs ( 1.00 usr + 0.00 sys = 1.00 CPU) @ 13 +10719.00/s (n=1310719) Rate gis::fast perl xs gis::fast 23643/s -- -69% -98% perl 77282/s 227% -- -94% xs 1310719/s 5444% 1596% -- ---- [ Formula: gcd ] ------------------------------------ perl - distance from BWI to LAX: 0 miles xs - distance from BWI to LAX: 2324.06319758555 miles gis::fast - distance from BWI to LAX: 0 miles Benchmark: running gis::fast, perl, xs for at least 1 CPU seconds... gis::fast: 1 wallclock secs ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 18 +270.09/s (n=19549) perl: 2 wallclock secs ( 1.07 usr + 0.00 sys = 1.07 CPU) @ 73 +080.37/s (n=78196) xs: 1 wallclock secs ( 1.05 usr + 0.01 sys = 1.06 CPU) @ 12 +98354.72/s (n=1376256) Rate gis::fast perl xs gis::fast 18270/s -- -75% -99% perl 73080/s 300% -- -94% xs 1298355/s 7006% 1677% -- ---- [ Formula: mt ] ------------------------------------ perl - distance from BWI to LAX: 2324.06319758555 miles xs - distance from BWI to LAX: 2324.06319758555 miles gis::fast - distance from BWI to LAX: 2324.06319758555 miles Benchmark: running gis::fast, perl, xs for at least 1 CPU seconds... gis::fast: 1 wallclock secs ( 1.12 usr + 0.01 sys = 1.13 CPU) @ 17 +300.00/s (n=19549) perl: 1 wallclock secs ( 1.06 usr + 0.00 sys = 1.06 CPU) @ 67 +621.70/s (n=71679) xs: 2 wallclock secs ( 1.07 usr + 0.01 sys = 1.08 CPU) @ 12 +74311.11/s (n=1376256) Rate gis::fast perl xs gis::fast 17300/s -- -74% -99% perl 67622/s 291% -- -95% xs 1274311/s 7266% 1784% -- ---- [ Formula: tv ] ------------------------------------ perl - distance from BWI to LAX: 2328.95218785171 miles xs - distance from BWI to LAX: 2324.51147636132 miles gis::fast - distance from BWI to LAX: 2328.95218785171 miles Benchmark: running gis::fast, perl, xs for at least 1 CPU seconds... gis::fast: 2 wallclock secs ( 1.09 usr + 0.01 sys = 1.10 CPU) @ 21 +720.91/s (n=23893) perl: 1 wallclock secs ( 1.09 usr + 0.00 sys = 1.09 CPU) @ 16 +439.45/s (n=17919) xs: 2 wallclock secs ( 1.05 usr + 0.00 sys = 1.05 CPU) @ 77 +1011.43/s (n=809562) Rate perl gis::fast xs perl 16439/s -- -24% -98% gis::fast 21721/s 32% -- -97% xs 771011/s 4590% 3450% --
    Benchmarking script:
    #!/usr/bin/env perl use strict; use warnings; use Benchmark qw(cmpthese timethese); use Geo::Distance::XS; use GIS::Distance; # When benchmarking, need to have it call import/unimport before the # code is executed. my $orig_timethis_sub = \&Benchmark::timethis; { no warnings 'redefine'; *Benchmark::timethis = sub { my $sub = ('perl' eq $_[2] ? 'un' : '') . 'import'; Geo::Distance::XS->$sub(); $orig_timethis_sub->(@_); }; } # Lon, Lat my @coord = (-76.668851, 39.179689, -118.408618, 33.943532); my $geo = Geo::Distance->new; my $gis = GIS::Distance->new; my %gis_formula = ( hsin => 'Haversine', polar => 'Polar', cos => 'Cosine', gcd => 'GreatCircle', mt => 'MathTrig', tv => 'Vincenty', ); sub geo { my $d = $geo->distance(mile => @coord); } sub gis { my $d = $gis->distance(@coord[ 1, 0, 3, 2 ]); return $d->mile; } for my $formula (qw(hsin polar cos gcd mt tv)) { print "---- [ Formula: $formula ] -------------------------------- +----\n"; $geo->formula($formula); $gis->formula($gis_formula{$formula}); Geo::Distance::XS->unimport; printf "perl - distance from BWI to LAX: %s miles\n", geo(); Geo::Distance::XS->import; printf "xs - distance from BWI to LAX: %s miles\n", geo(); printf "gis::fast - distance from BWI to LAX: %s miles\n", gis(); print "\n"; my $benchmarks = timethese - 1, { perl => \&geo, xs => \&geo, 'gis::fast' => \&gis, }; cmpthese $benchmarks; print "\n"; }
      gray,
      ...he probably will accept patches via

      I have emailed the author. I would like to offer a patch but I am not sure what the problem is. I was in a hurry to get my project complete so I could go to sleep.

      A good reason to use Geo::Distance::XS

      First, thanks! I admit that I didn't try it for a few reasons. The first is that I assumed one was just an XS implementation of the other to include the bug. The second reason is that in the environment where this needed to run, XS is not an easy option. Without going into a lot of detail - local politics have created technical hurdles I didn't want to jump through (I was tired). It is also the reason I didn't use GIS::Distance. I was pretty sure (and you confirmed) that it produces correct results but the litany of dependencies without an internet connection was unreasonable.

      I am happy that there are working solutions out there. I guess after reflecting on my lamentation, what I really should have asked is: Does anyone know of a Geo::Distance::Lite that works?

      Regarding your benchmark. First, I suspect you didn't "You can stick with the pure Perl version by setting the GEO_DISTANCE_PP environment variable before using this module" This is because Geo::Distance gave the correct answer which it I know it doesn't (the point of this thread). Second, it would only be fair to add tye's version which avoids the whole OO overhead.

      Cheers - L~R

        Regarding your benchmark. First, I suspect you didn't "You can stick with the pure Perl version by setting the GEO_DISTANCE_PP environment variable before using this module" This is because Geo::Distance gave the correct answer which it I know it doesn't (the point of this thread).

        $ENV{GEO_DISTANCE_PP} just triggers Geo::Distance::XS->unimport(), which my benchmark script calls directly. I also checked the results by hiding Geo::Distance::XS with Test-Without-Module and they were consistent. Note also the results for the 'gcd' formula- both Geo::Distance and GIS::Distance::Fast failed, whereas Geo::Distance::XS produced a reasonable result. Perhaps if you posted your test script we could dig further.

Re: Alternatives To Geo::Distance
by Khen1950fx (Canon) on Oct 22, 2010 at 01:09 UTC
    I tried Geo::Ellipsoid. I used all the different ellipsoids just to see what would happen. I was looking for the miles from SFO to LAX.
    #!/usr/bin/perl use strict; use warnings; use Geo::Ellipsoid; my @ellipsoids = ( 'AIRY', 'AIRY-MODIFIED', 'AUSTRALIAN', 'BESSEL-1841', 'CLARKE-1880', 'EVEREST-1830', 'EVEREST-MODIFIED', 'FISHER-1960', 'FISHER-1968', 'GRS80', 'HOUGH-1956', 'HAYFORD', 'IAU76', 'KRASSOVSKY-1938', 'NAD27', 'NWL-9D', 'SOUTHAMERICAN-1969', 'SOVIET-1985', 'WGS72', 'WGS84' ); foreach my $ellipsoid(@ellipsoids) { my $geo = Geo::Ellipsoid->new( ellipsoid => $ellipsoid, units => 'degrees', distance_units => 'mile', longitude => 1, bearing => 1, ); my @origin = ( 37.619002, -122.374843 ); my @dest = ( 33.942536, -118.408074 ); my ( $range, $bearing ) = $geo->to( @origin, @dest ); my ($lat, $lon) = $geo->at( @origin, 2000, 45.0); my ($x, $y) = $geo->displacement( @origin, $lat, $lon ); my @pos = $geo->location( $lat, $lon, $x, $y ); print my $dist = $geo->range( @origin, @dest ), "\n"; }