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 those who want to calculate the distance between the points taking into account the streets (which is quite different from the distance between the points in a straight line). However, it has a limit for free use and to use more than the quota, you have to pay. However, if your project will have little access, or is financially viable to use this API, go ahead!
Example provided by Google: https://jsfiddle.net/api/post/library/pure/
2) Haversine’s formula - calculation of distance between points in a straight line
Great option for Calculating distance between two points, however the calculation should be performed for each new two points existing 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 website: https://stackoverflow.com/a/1502821/7113404
3) Geohash - calculation of 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 complex calculations on the client computer. Also, by not making a mathematical calculation for each distance value request, it is extremely efficient in distance calculations with many Cartesian points.
The geohash algorithm proposal 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), dividing it now into four parts. Give the square located the position equivalent to the northwest the bits 00 (first 0 indicates the west position, the second 0 indicates north 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 on the map:
0010110101011100011000110001111000110111, or
00101 10101 01110 00110 00110 00110 11110 00111, or,
using character representation (32-bit encoding):
5(00101) p(10101) f(01110) 6(00110) 6(00110) 6(00110) y(11110) 7(00111)
To know the distance between the points, one should compare the geohash of the points from left to right. The more these characters coincide, the closer the points are. Already to know which points are at a certain distance from one another, just calculate the geohash of the central point and look for the points that coincide from left to right, considering the table of approximation of distances to follow:
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 the site: http://www.movable-type.co.uk/scripts/geohash.html
A problem found in this algorithm occurs in cases where points that are close to each other are at the margins of different cells (represented by a string). For example, imagine two points near Greenwich, but one is in the western hemisphere and the other is in the eastern hemisphere. In this case, the generated string may erroneously state that the dots are more distant than they actually are. To solve this problem, algorithms must search for points in adjacent squares.
To illustrate and try to clarify further the theme, follows an algorithm taken from the site http://www.movable-type.co.uk/scripts/geohash.html:
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* 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:
- http://www.movable-type.co.uk/scripts/geohash.html
- http://www.bigfastblog.com/geohash-intro
- https://en.wikipedia.org/wiki/Geohash
I believe that the best way to solve this problem is by using geohash. Take a look at this site: http://www.bigfastblog.com/geohash-intro
– L. Cafezeiro
There are some algorithms ready in javascript on the internet that you can use as a basis.
– L. Cafezeiro
You can turn into cardinals, normalize the
Z
and calculate the distance between the two points in space. For nearby elements, the influence of the curvature of the Earth will not greatly affect the relative distance of the points. When it comes to distant things (I don’t know, more than 2º?), the curvature of the Earth plays a significant role and may interfere in the ordering relative to distance. Behold in this answer how to transform spherical coordinates into spatial cartesians (I do not deal with the normalization of theZ
meanwhile)– Jefferson Quesado
@L.Cafezeiro could cite one as an example?
– Jorge.M
@Jeffersonquesado could give me some example site? I believe that it will not be so complex because it is only locations in Brazil
– Jorge.M
@Jorge the answer that I Linkei already does this
– Jefferson Quesado