CODEWITHSUNDEEP
ruby-on-railsruby
Charlie Davies
Charlie Davies

Reputation: 1834

Distance on Two Lat / Lngs in Ruby

Given the problem that you have 2000 lat / lngs that need to calculate their distance to another 2000 lat / lngs in pairs. i.e. 1 to 1. What would be the fastest way to get this done in ruby.

Could a C extension be quicker? or java. At the moment I am using the GeoKit gem and it is a little slow for so many points.

EDIT 1:

The time is over 30 seconds at the moment.

Upvotes: 1

Views: 128

Answers (2)

Pasted
Pasted

Reputation: 864

If you're using PostgreSQL as your database you could have a look at http://postgis.refractions.net/

It would require reloading the Lat/Lng points back into a database table with PostGIS point datatypes, but as a bonus the database should now be able to handle shapefiles for things like borders and boundaries.

SQL Function to find distance between two geoms

http://postgis.refractions.net/documentation/manual-1.5/ST_Distance.html

Installation

http://postgis.refractions.net/documentation/manual-1.5/ch02.html

EDIT:

If these are only stored in memory I suppose you could use something like spawn (or roll your own version) https://github.com/tra/spawn, https://github.com/rfc2822/spawn to split the calculations up into groups. Since it sounds like the distance calculations are just between matched pairs it should be pretty straight-forward to merge the results back together at the end (as Karel suggests).

You could stream the results back to the client as they are finished (if they don't need to be ordered - although the final ordering could be done client side when the final results are recieved).

Upvotes: 0

Jonas Elfström
Jonas Elfström

Reputation: 31428

How do you use GeoKit? On my machine it takes 0.016s to calculate the distance between 2000 points.

require 'benchmark'
require 'geokit'

ll_arr = 2000.times.map {|i| 
              [Geokit::LatLng.new(rand(-180..180), rand(-180...180)),
               Geokit::LatLng.new(rand(-180..180), rand(-180...180))]}

distances = []

Benchmark.bm do |x|
  x.report do 
    ll_arr.each do |ll|
      distances << ll[0].distance_from(ll[1], :units=>:kms)
    end
  end
end

10.times do |n|
  m = n * 200
  puts "ll #{m} from: #{ll_arr[m][0]} to: #{ll_arr[m][1]} distance: #{distances[m]}"
end

Outputs:

user     system      total        real
0.016000   0.000000   0.016000 (  0.015624)

And the results seems reasonable (in kilometers):

ll 0 from: -180,71 to: 111,164 distance: 10136.21791028502
ll 200 from: 40,-127 to: -62,-23 distance: 14567.00843599676
ll 400 from: 23,-178 to: -163,-140 distance: 16014.598170496456
ll 600 from: 85,155 to: 25,3 distance: 7727.840511097989
ll 800 from: -26,57 to: 145,-36 distance: 11384.743155770688
ll 1000 from: -111,-137 to: 5,-5 distance: 9007.969496928148
ll 1200 from: 118,-98 to: -153,179 distance: 12295.886774709148
ll 1400 from: 44,-139 to: -91,-134 distance: 15024.485920445308
ll 1600 from: 48,126 to: -37,-92 distance: 16724.015574628884
ll 1800 from: -174,-77 to: -69,75 distance: 7306.820947156828

Upvotes: 1

Related Questions