Sorting latitude and longitude by distance and grouping them based on tolerance

Goal

There are two goals:

Sort latitude and longitude by distance
Group the latitude and longitude based on a tolerance

Expected

Latitude and longitude are sorted in order of distance and grouped by tolerance.

Actual

Latitude and longitude are sorted in order of distance but the grouping does not feel right.

What I've tried

I've used the Haversine formula from several StackOverflow answers e.g. example 1, example 2, example 3, and managed to sort the locations by distance (goal #1 - I think 🤔). I attempted to group them using a tolerance via Math.abs(lat - lastLat) < tolerance but I'm not confident it's working or flexible (goal #2).

Code

const locations = [
  { lat: 77.62279999, lng: 12.95248389 },
  { lat: 77.62517676, lng: 12.95027966 },
  { lat: 77.62753442, lng: 12.93745478 },
  { lat: 77.62217671, lng: 12.93353553 },
];

const distance = (lat1, lon1, lat2, lon2) => {
  const radlat1 = (Math.PI * lat1) / 180;
  const radlat2 = (Math.PI * lat2) / 180;

  const theta = lon1 - lon2;
  const radtheta = (Math.PI * theta) / 180;

  let dist =
    Math.sin(radlat1) * Math.sin(radlat2) +
    Math.cos(radlat1) * Math.cos(radlat2) * Math.cos(radtheta);
  dist = Math.acos(dist);
  dist = (dist * 180) / Math.PI;
  dist = dist * 60 * 1.1515;
  dist = dist * 1.609344;

  return dist;
};

const sortedLocationsByDistance = locations.sort(function (a, b) {
  return distance(0, 0, a.lat, a.lng) - distance(0, 0, b.lat, b.lng);
});

console.log('Sorted:', sortedLocationsByDistance);

const groupedLocationsByTolerance = {};

const tolerance = 0.001;

sortedLocationsByDistance.forEach(({ lat, lng }, index) => {
  if (
    Object.keys(groupedLocationsByTolerance).length && 
    Math.abs(lat - sortedLocationsByDistance.slice(-1)[0].lat) < tolerance &&
    Math.abs(lng - sortedLocationsByDistance.slice(-1)[0].lng) < tolerance
  ) {
    groupedLocationsByTolerance[Object.keys(groupedLocationsByTolerance).slice(-1)[0]].push({ lat, lng });
    return;
  }

  groupedLocationsByTolerance[index] = groupedLocationsByTolerance[index] || [];
  groupedLocationsByTolerance[index].push({ lat, lng });
});

console.log('Grouped:', groupedLocationsByTolerance);

Solution

For very large sets, the number of iterations can be reduced significantly by a combination of both(!) of your answers. The logic is thus...

O( n ) - Calculate the distance of every lat/long from a fixed point. In the example below, the origin lat/long of ( 0, 0 ) is used as the fixed point.
O( n log n ) - Sort this array by ascending distance.
O( nm ) - Now, similar to a bubble sort, walk this array with a nested pair of loops such that while the inner loop distance from origin is still within the tolerance of the outer loop distance from origin, perform the expensive getDistance check to determine if the coordinates are indeed within tolerance. Continue in the inner loop while the distance from origin difference is still within the tolerance, otherwise break from the inner loop, as there is no sense in comparing the distances now known to be further apart than the tolerance. In this way, the algorithm is only checking a handful of distances that are within range of the tolerance.

The "m" in O( nm ) is the average number of locations within tolerance, and for large numbers of locations, should be relatively small compared to "n", assuming some distribution of the locations and a small tolerance. For large tolerances, of course, "m" will approach "n" and then the algorithm is performing at O( n^2 )...

const locations = [
  { latitude: 77.62279999, longitude: 12.95248389 },
  { latitude: 77.62279999, longitude: 12.95248389 },
  { latitude: 78.62217671, longitude: 12.93353553 },
  { latitude: 77.62517676, longitude: 12.95027966 },
  { latitude: 77.62753442, longitude: 12.93745478 },
  { latitude: 77.62752442, longitude: 12.93745478 },
  { latitude: 77.62214671, longitude: 12.93353553 },
];

const getDistance = (lat1, lon1, lat2, lon2) => {
    const radlat1 = (Math.PI * lat1) / 180;
    const radlat2 = (Math.PI * lat2) / 180;

    const theta = lon1 - lon2;
    const radtheta = (Math.PI * theta) / 180;

    let dist =
        Math.sin(radlat1) * Math.sin(radlat2) +
        Math.cos(radlat1) * Math.cos(radlat2) * Math.cos(radtheta);
    dist = Math.acos(dist);
    dist = (dist * 180) / Math.PI;
    dist = dist * 60 * 1.1515;
    dist = dist * 1.609344;

    return dist;
};


for ( let loc of locations ) {
  loc.distanceFromOrigin = getDistance( loc.latitude, loc.longitude, 0, 0 );
}

console.log( 'Sorted by closest to origin:' );
locations.sort( ( a, b ) => a.distanceFromOrigin - b.distanceFromOrigin );
console.log( locations );

let tolerance = 0.01;
let results = [];

for ( let i = 0; i < locations.length; i++ ) {
  let loci = locations[ i ];
  for ( let j = i + 1; j < locations.length; j++ ) {
    let locj = locations[ j ];
    if ( locj.distanceFromOrigin - loci.distanceFromOrigin <= tolerance ) {
      if ( getDistance( loci.latitude, loci.longitude, locj.latitude, locj.longitude ) <= tolerance ) {
        loci.properties = loci.properties ?? [];
        loci.properties.push( locj );
      }
    } else {
      break;
    }
  }
  if ( loci.properties ) {
    results.push( loci );
  }
}

console.log( `Closest by tolerance of ${tolerance}:` );
console.log( results );