将纬度和经度按距离排序，并根据容差进行分组。

Question

目标

---

有两个目标：

1. 按距离排序纬度和经度
2. 基于公差将纬度和经度分组

期望结果

---

按照距离的顺序对纬度和经度进行排序，并根据公差进行分组。

实际结果

---

纬度和经度按距离排序，但分组感觉不太正确。

尝试过的方法

---

我使用了几个 StackOverflow 答案中的Haversine 公式，例如 示例 1、示例 2、示例 3，并成功地按照距离排序了位置（目标 #1 - 我认为）。我尝试使用 Math.abs(lat - lastLat) < tolerance 来通过公差进行分组，但我不确定它是否有效或灵活（目标 #2）。

代码

---

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);

- Paddy

Answer 1

这是我最终采用的解决方案。如有需要，欢迎您进行微调和完善（发布自己的方案来帮助他人）。我知道有很多实现方法。

我的尝试

---

如上所示，第一种方法使用了中心点（0, 0）并通过Haversine公式测量每个引脚之间的距离。下一个解决方案使用算法计算每个点之间的射线角度，使用三角函数（非常感谢这个答案）。

const getSortedByDistance = (
  coordinates,
  centerPoint
) => {
  const points = [...coordinates]; // Copy the array, sort modifies it
  const angles = {};

  // Calculate the angle of the ray between that center point and each point, using inverse trigonometric functions
  points.forEach((point) => {
    angles[getCoordinateKey(point.latitude, point.longitude)] = Math.atan2(
      point.latitude - centerPoint.latitude,
      point.longitude - centerPoint.longitude
    );
  });

  // Filter the order based on the angle
  points.sort(
    (pointA, pointB) =>
      angles[getCoordinateKey(pointA.latitude, pointA.longitude)] -
      angles[getCoordinateKey(pointB.latitude, pointB.longitude)]
  );

  return points;
};

虽然这样分组的坐标比较好，但并不能保证它们的顺序是正确的，在某些情况下可能会导致最后一组检查失败。

我的做法

---

经过一番思考，最好的选择是使用Haversine公式来测量点与点之间的距离，从而创建准确的分组。唯一的缺点是完整计算的性能成本。

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;
};

const getGroupsByDistance = (coordinates, tolerance) => {
    const coordinatesToleranceMap = Array(coordinates.length).fill(1); // 1 = true

    return coordinates.reduce(
        (groups, coordinate, index) => {
            // The tolerance map contains true/false (0/1) values, ignore anything with 0
            if (coordinatesToleranceMap[index] === 0) return groups;

            const { latitude, longitude } = coordinate;

            // This will return the current listing because it's the same lat/lng. We don't need to check it's length because it always has one
            const coordinatesWithinTolerance = coordinates.filter(
                (coordinate, index) => {
                    // We're not interested in any listing that have been filtered out already
                    if (coordinatesToleranceMap[index] === 0) {
                        return false;
                    }

                    const isSameLatLng =
                        latitude === coordinate.latitude &&
                        longitude === coordinate.longitude;

                    // Measure distance using Haversine formula
                    const isWithinTolerance =
                        isSameLatLng ||
                        getDistance(
                            latitude,
                            longitude,
                            coordinate.latitude,
                            coordinate.longitude
                        ) <= tolerance;

                    // Ignore the current listing on the next filter
                    if (isWithinTolerance) coordinatesToleranceMap[index] = 0;

                    return isWithinTolerance;
                }
            );

            groups.push({
                latitude,
                longitude,
                properties: coordinatesWithinTolerance
            });

            return groups;
        },
        []
    );
};

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 tolerance = 0.01;

const t0 = performance.now();
const groupsByDistance = getGroupsByDistance(locations, tolerance);
const t1 = performance.now();

console.log('Time:', t1 - t0);
console.log(groupsByDistance);

性能

---

随着数据集的增长，该函数执行所需的时间将变得更长。需要对其进行拆分以减少执行时间。或者，减少循环次数可能会导致显著的改进。

改进

---

如果有人可以提出更好的答案（改进/新逻辑），使其性能更佳，请在下面添加。

- Paddy

Answer 2

对于非常大的数据集，可以通过将两个答案的组合来显著减少迭代次数。其逻辑如下：

- O(n) - 计算每个经纬度与固定点之间的距离。在下面的示例中，原点经纬度（0,0）被用作固定点。 - O(n log n) - 按升序距离对该数组进行排序。 - O(nm) - 现在，类似于冒泡排序，使用一对嵌套循环遍历此数组，使得当内部循环距离原点仍在外部循环距离原点的容差范围内时，执行昂贵的getDistance检查以确定坐标是否确实在容差范围内。在内部循环中继续，直到距离原点的差异不再在容差范围内，否则从内部循环中退出，因为比容差更远的距离已知，没有比较的意义。通过这种方式，算法只检查了一些在容差范围内的距离。

O(nm)中的“m”是在容差范围内的位置的平均数量，对于大量位置来说，应该相对于“n”而言相对较小，假设某些位置的分布和容差很小。当容差很大时，“m”当然会接近“n”，然后算法将以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 );
    

- Trentium

---

这是一些有趣/高质量的工作！谢谢你的回复。我注意到容差似乎不能将多个属性分组。是这样吗？ - Paddy

我冒昧地将位置从其自身的属性列表中排除，因此结果（基于示例数据）仅显示一个分组属性。如果在内部循环中将j = i + 1更改为j = i，则内部循环将从将位置与自身进行比较开始，属性将包括自身，结果将与您一直看到的相匹配... - Trentium

再次感谢您的回答。我已经有机会尝试它，它确实将迭代次数减少了约50-55％。您是否建议使用传统的for循环而不是reduce/filter？我知道旧方法应该更快，但在运行一些performance.now()测试后，它因实现方法而异。我喜欢新语法的可读性。 - Paddy

通常当我提出涉及算法的答案时，我仅仅为了可读性而使用传统的循环结构，特别是为了更清晰地解释大O符号。Reduce/Filter也可以达到同样的效果，但要注意当前内部循环的短路是节省时间的源泉。也就是说，如果在内部循环中使用过滤器，则会扫描整个位置列表以查找那些distanceFromOrigin在公差范围内的位置，并在此基础上创建一个新数组(!)... - Trentium