How to solve the distance between two points on the map:
1) Using Google's Distance Matrix API
This API is simple to use and very efficient. Probably the best option for anyone who wants to calculate the distance between the points taking into consideration the streets (which is quite different from the distance between the points in a straight line). However, you have a limit for free use and to use more than the quota, you have to pay. However, if your project has little access, or is financially viable to use this API, go ahead!
Example provided by Google: link
2) Haversine formula - calculating distance between points in a straight line
Great option for calculating distance between two points, but the calculation must be performed for each new two points on the map. If your list of points is too large, it can be a computationally costly and consequently time-consuming procedure for client computers.
How to use this solution has already been explained on this site: link
3) Geohash - calculating the approximate distance between points in a straight line
Geohash is an algorithm created by Gustavo Niemeyer and aims to calculate distances between positions on the map. This solution does not require performing complex calculations on the client computer. In addition, because it does not make a mathematical calculation for each distance value request, it is extremely efficient in distance calculations with many Cartesian points.
The proposed geohash algorithm is as follows:
Make a vertical cut on the map, dividing it into two parts (at first it would be the equivalent of Greenwich) and give the western hemisphere bit 0, and the eastern hemisphere bit 1;
Then make a horizontal cut on the map (at first it would be the equivalent of the equator line), dividing it now into four quarters. Give the square the equivalent position to the northwest the bits 00 (first 0 indicates the western position, the second 0 indicates northern position). Following the pattern, the squares positioned in the northeast, southwest and southeast receive the bits 01,11,10;
Repeat this procedure until each small square is represented by 32 bits.
By way of example, at the end of the algorithm we could have the following sequence of bits representing a space in the map:
0010110101011100011000110001101111000111, or
00101 10101 01110 00110 00110 00110 11110 00111 or further,
using the character representation (32-bit encoding): 5 (00101) p (10101) f (01110) > 6 (00110) 6 (00110) 6 (00110) and (00111)
To know the distance between the points, one must compare the geohash of the points from left to right. The more these characters coincide, the greater the proximity between the points. In order to know which points are at a certain distance from another, simply calculate the geohash of the center point and look for the points that coincide from left to right, considering the distance approximation table below: >
Geohash length Cell width Cell height
1 ≤ 5,000km × 5,000km
2 ≤ 1,250km × 625km
3 ≤ 156km × 156km
4 ≤ 39.1km × 19.5km
5 ≤ 4.89km × 4.89km
6 ≤ 1.22km × 0.61km
7 ≤ 153m × 153m
8 ≤ 38.2m × 19.1m
9 ≤ 4.77m × 4.77m
10 ≤ 1.19m × 0.596m
11 ≤ 149mm × 149mm
12 ≤ 37.2mm × 18.6mm
Table taken from site: link
A problem found in this algorithm happens in cases where points that are close to the edge of cells (represented by a string) are different. For example, imagine two points near Greenwich, but one is in the Western Hemisphere and one Eastern. In this case, the generated character sequence may erroneously inform that the points are further from what they actually are. To solve this problem, algorithms must search for points in adjacent squares.
To illustrate and try to further clarify the subject, follow an algorithm taken from link :
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* Geohash encoding/decoding and associated functions (c) Chris Veness 2014-2016 / MIT Licence */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
'use strict';
/**
* Geohash encode, decode, bounds, neighbours.
*
* @namespace
*/
var Geohash = {};
/* (Geohash-specific) Base32 map */
Geohash.base32 = '0123456789bcdefghjkmnpqrstuvwxyz';
/**
* Encodes latitude/longitude to geohash, either to specified precision or to automatically
* evaluated precision.
*
* @param {number} lat - Latitude in degrees.
* @param {number} lon - Longitude in degrees.
* @param {number} [precision] - Number of characters in resulting geohash.
* @returns {string} Geohash of supplied latitude/longitude.
* @throws Invalid geohash.
*
* @example
* var geohash = Geohash.encode(52.205, 0.119, 7); // geohash: 'u120fxw'
*/
Geohash.encode = function(lat, lon, precision) {
// infer precision?
if (typeof precision == 'undefined') {
// refine geohash until it matches precision of supplied lat/lon
for (var p=1; p= lonMid) {
idx = idx*2 + 1;
lonMin = lonMid;
} else {
idx = idx*2;
lonMax = lonMid;
}
} else {
// bisect N-S latitude
var latMid = (latMin + latMax) / 2;
if (lat >= latMid) {
idx = idx*2 + 1;
latMin = latMid;
} else {
idx = idx*2;
latMax = latMid;
}
}
evenBit = !evenBit;
if (++bit == 5) {
// 5 bits gives us a character: append it and start over
geohash += Geohash.base32.charAt(idx);
bit = 0;
idx = 0;
}
}
return geohash;
};
/**
* Decode geohash to latitude/longitude (location is approximate centre of geohash cell,
* to reasonable precision).
*
* @param {string} geohash - Geohash string to be converted to latitude/longitude.
* @returns {{lat:number, lon:number}} (Center of) geohashed location.
* @throws Invalid geohash.
*
* @example
* var latlon = Geohash.decode('u120fxw'); // latlon: { lat: 52.205, lon: 0.1188 }
*/
Geohash.decode = function(geohash) {
var bounds = Geohash.bounds(geohash); // =0; n--) {
var bitN = idx >> n & 1;
if (evenBit) {
// longitude
var lonMid = (lonMin+lonMax) / 2;
if (bitN == 1) {
lonMin = lonMid;
} else {
lonMax = lonMid;
}
} else {
// latitude
var latMid = (latMin+latMax) / 2;
if (bitN == 1) {
latMin = latMid;
} else {
latMax = latMid;
}
}
evenBit = !evenBit;
}
}
var bounds = {
sw: { lat: latMin, lon: lonMin },
ne: { lat: latMax, lon: lonMax },
};
return bounds;
};
/**
* Determines adjacent cell in given direction.
*
* @param geohash - Cell to which adjacent cell is required.
* @param direction - Direction from geohash (N/S/E/W).
* @returns {string} Geocode of adjacent cell.
* @throws Invalid geohash.
*/
Geohash.adjacent = function(geohash, direction) {
// based on github.com/davetroy/geohash-js
geohash = geohash.toLowerCase();
direction = direction.toLowerCase();
if (geohash.length === 0) throw new Error('Invalid geohash');
if ('nsew'.indexOf(direction) == -1) throw new Error('Invalid direction');
var neighbour = {
n: [ 'p0r21436x8zb9dcf5h7kjnmqesgutwvy', 'bc01fg45238967deuvhjyznpkmstqrwx' ],
s: [ '14365h7k9dcfesgujnmqp0r2twvyx8zb', '238967debc01fg45kmstqrwxuvhjyznp' ],
e: [ 'bc01fg45238967deuvhjyznpkmstqrwx', 'p0r21436x8zb9dcf5h7kjnmqesgutwvy' ],
w: [ '238967debc01fg45kmstqrwxuvhjyznp', '14365h7k9dcfesgujnmqp0r2twvyx8zb' ],
};
var border = {
n: [ 'prxz', 'bcfguvyz' ],
s: [ '028b', '0145hjnp' ],
e: [ 'bcfguvyz', 'prxz' ],
w: [ '0145hjnp', '028b' ],
};
var lastCh = geohash.slice(-1); // last character of hash
var parent = geohash.slice(0, -1); // hash without last character
var type = geohash.length % 2;
// check for edge-cases which don't share common prefix
if (border[direction][type].indexOf(lastCh) != -1 && parent !== '') {
parent = Geohash.adjacent(parent, direction);
}
// append letter for direction to parent
return parent + Geohash.base32.charAt(neighbour[direction][type].indexOf(lastCh));
};
/**
* Returns all 8 adjacent cells to specified geohash.
*
* @param {string} geohash - Geohash neighbours are required of.
* @returns {{n,ne,e,se,s,sw,w,nw: string}}
* @throws Invalid geohash.
*/
Geohash.neighbours = function(geohash) {
return {
'n': Geohash.adjacent(geohash, 'n'),
'ne': Geohash.adjacent(Geohash.adjacent(geohash, 'n'), 'e'),
'e': Geohash.adjacent(geohash, 'e'),
'se': Geohash.adjacent(Geohash.adjacent(geohash, 's'), 'e'),
's': Geohash.adjacent(geohash, 's'),
'sw': Geohash.adjacent(Geohash.adjacent(geohash, 's'), 'w'),
'w': Geohash.adjacent(geohash, 'w'),
'nw': Geohash.adjacent(Geohash.adjacent(geohash, 'n'), 'w'),
};
};
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
if (typeof module != 'undefined' && module.exports) module.exports = Geohash; // CommonJS, node.js
sources:
