# How to compute distance between 4500 points fast?

I am working on a location problem with 150 customers (points) and 30 facilities (points). I have determined the location of any customer and facility by google earth and then saved them in a KMZ file. I need to compute the distance between any pair of customers and facilities. So I should compute 150*30=4500 values by ruler tool in Google Earth. Is there any other way to obtain these values faster and easier? Even by converting the KMZ file to a layer in ArcGIS 10?

One of the fastest and easiest possible solutions uses a short program written with the free open source program `R` (the R project for statistical computing). The following code computes the distance matrix (using spherical distances) between two arrays of (lon, lat) coordinates named `customers` and `facilities` and stores it in an array `distances` (with rows for customers and columns for facilities).

``````dist <- function(x, y=c(0,0), radius=6366710) {
# `x` and `y` are both (lon, lat) in radians.
# `x` is an `n` by 2 matrix.
# Returns distances on a sphere of radius `radius`; the default value
# is a spherical model in meters.
return (2 * radius * asin( sqrt(sin((x[,2]-y)/2)^2 +
cos(x[,2])*cos(y)*(sin(x[,1]-y)/2)^2)))
}
distances <- apply(facilities * pi/180, 1, function(y) dist(customers * pi/180, y)
``````

It runs reasonably quickly: your problem with 150 customers and 30 facilities generates a matrix of all 150*30 = 4500 distances in 2.5 milliseconds.

To extract the coordinates from a Google Earth file, save the locations directly in KML format or unzip the KMZ file (which will produce a KML version). This is an ASCII file containing (lon, lat) coordinates.. The maptools package reads such files directly. Here is a working example that reads KML files of customers and facilities and computes all distances between them.

``````read.kml <- function(s) {
require(maptools)
x <- getKMLcoordinates(s, ignoreAltitude=TRUE)
return (matrix(unlist(x), ncol=2))
}
distances <- apply(facilities * pi/180, 1, function(y) dist(customers * pi/180, y))
``````

At this point you can perform just about any kind of calculation you might like with the distances and--of course--you can write them to a file for post-processing on another platform.

• Thanks a lot. I think that your suggestion is one of the best possible ways. I am familiar with MATLAB programming. So I just need to have the coordinates of any point in a file – hasti Jan 3 '14 at 17:25
• Thanks a lot. I think that your suggestion is one of the best possible ways. I am familiar with MATLAB programming. So I just need to have the coordinates of any point in a file. Sorry for asking another question. Is it possible to transform the coordinates directly from google earth to an Excel file? – hasti Jan 3 '14 at 17:31
• Sarah, it certainly is possible for Excel to read a KML file. For instance, when I open a KML file directly in Excel (just by dragging it from Windows Explorer and dropping it into an open new workbook) I get one line per point starting on line 3 and the coordinates are stuffed into the cells of column R, separated by commas. Using the `Text to columns` function converts them into two separate columns of coordinates. If you wished to do everything in Excel, you could even translate this `R` code into a VBA macro to generate your distance matrix from a pair of such KML files. – whuber Jan 3 '14 at 18:12

If you need ruler distance, You can use the distance matrix tool in Quantum GIS. Quantum GIS can read your KMZ files. Then you can easily compute the distance matrix. Here is tutorial http://qgis.spatialthoughts.com/2013/04/tutorial-nearest-neighbor-analysis.html

import your KMZ in arcGIS using "KML to Layer".

you can then use the "near" tool in arcgis.(http://resources.arcgis.com/en/help/main/10.1/index.html#//00080000001q000000) for "straight line" distances.

For real distance, you need the Network analyst extension and the road network in a vector format as well (see http://help.arcgis.com/en%20/arcgisdesktop/10.0/help/index.html#//00470000004r000000) for distance matrix. Note that there are open source alternatives to Network analyst if you go outside of ArcGIS (e.g. http://pgrouting.org/).

• Thanks for your prompt answer. Unfortunately I am a beginner with GIS and I am not familiar with network analyst. Is there any way to find the straight line distances in google earth easier and faster? – hasti Jan 3 '14 at 9:42
• I'm afraid that there is no quicker way in google earth. Computing a distance matrix between points is extremely simple however. – Rob Lodge Jan 3 '14 at 10:09
• OK . could you please give me a simple clue to compute the distance matrix in GIS ? – hasti Jan 3 '14 at 10:16
• convert your kmz to a kml (either by extracting it or re-saving it in google earth), open it in qgis as a vector layer, then compute your distance matrix by following the tutorial suggested in neogeomat's answer. – Rob Lodge Jan 3 '14 at 12:46
• I really appreciate your help Rob and neogeomat. I will try this. The internet speed is too low in my town and I could not download qgis yet after 7 times downloading from different links! – hasti Jan 3 '14 at 17:17