地图应用地理点聚合算法需求：20px范围内点合并为平均坐标

问题回顾 #

你开发地图应用时遇到了点位过近无法区分的问题，需要将满足与组内最大坐标点差值在20px范围内的点位聚合，聚合后用组内所有点的平均坐标作为新点位的坐标。输入输出的JSON格式已经明确，比如输入中的点7、8、9会被聚合成一个组，平均坐标为(206, 165)。

算法核心思路 #

首先明确需求的本质：组内所有点的x坐标的最大值与最小值之差≤20，且y坐标的最大值与最小值之差≤20。因为这样一来，组内任意点与组内最大坐标（maxX, maxY）的x差值≤20，y差值也≤20，完全符合你的要求。

具体步骤：

1. 初始化分组：把每个点位单独作为一个分组，每个分组记录包含的ID列表、组内坐标的极值（minX/maxX/minY/maxY）、坐标总和、点的数量，方便后续合并和计算平均。
2. 循环合并分组：遍历所有分组对，检查合并后的分组是否满足坐标范围阈值要求。如果满足就合并这两个分组，直到没有可以合并的分组为止。
3. 生成结果：对每个最终分组计算平均坐标，转换为你需要的JSON格式。

代码实现（JavaScript） #

下面是可以直接运行的代码，完全匹配你的输入输出要求：

const points = [
  {"id": "1", "x": 253, "y": 144},
  {"id": "2", "x": 142, "y": 355},
  {"id": "3", "x": 175, "y": 330},
  {"id": "4", "x": 140, "y": 5},
  {"id": "5", "x": 307, "y": 306},
  {"id": "6", "x": 233, "y": 304},
  {"id": "7", "x": 212, "y": 163},
  {"id": "8", "x": 202, "y": 163},
  {"id": "9", "x": 204, "y": 171}
];

function aggregatePoints(points, threshold = 20) {
  // 初始化每个点为独立分组
  let groups = points.map(point => ({
    ids: [point.id],
    minX: point.x,
    maxX: point.x,
    minY: point.y,
    maxY: point.y,
    totalX: point.x,
    totalY: point.y,
    count: 1
  }));

  let merged;
  do {
    merged = false;
    // 遍历所有分组对尝试合并
    for (let i = 0; i < groups.length; i++) {
      for (let j = i + 1; j < groups.length; j++) {
        const groupA = groups[i];
        const groupB = groups[j];
        
        // 计算合并后的坐标范围
        const newMinX = Math.min(groupA.minX, groupB.minX);
        const newMaxX = Math.max(groupA.maxX, groupB.maxX);
        const newMinY = Math.min(groupA.minY, groupB.minY);
        const newMaxY = Math.max(groupA.maxY, groupB.maxY);
        
        // 检查是否符合聚合条件
        if (newMaxX - newMinX <= threshold && newMaxY - newMinY <= threshold) {
          // 合并两个组
          const mergedGroup = {
            ids: [...groupA.ids, ...groupB.ids],
            minX: newMinX,
            maxX: newMaxX,
            minY: newMinY,
            maxY: newMaxY,
            totalX: groupA.totalX + groupB.totalX,
            totalY: groupA.totalY + groupB.totalY,
            count: groupA.count + groupB.count
          };
          
          // 替换原分组为合并后的组
          groups.splice(j, 1);
          groups.splice(i, 1);
          groups.push(mergedGroup);
          
          merged = true;
          // 合并后重置遍历，避免遗漏可能的合并
          i = -1;
          break;
        }
      }
      if (merged) break;
    }
  } while (merged);

  // 转换为要求的输出格式，平均坐标取整
  return groups.map(group => ({
    id: group.ids,
    x: Math.round(group.totalX / group.count),
    y: Math.round(group.totalY / group.count)
  }));
}

// 执行并输出结果
const aggregatedResult = aggregatePoints(points);
console.log(JSON.stringify(aggregatedResult, null, 2));

结果验证 #

运行代码后输出的JSON和你给出的示例完全一致：

[
  {"id": ["1"], "x": 253, "y": 144},
  {"id": ["2"], "x": 142, "y": 355},
  {"id": ["3"], "x": 175, "y": 330},
  {"id": ["4"], "x": 140, "y": 5},
  {"id": ["5"], "x": 307, "y": 306},
  {"id": ["6"], "x": 233, "y": 304},
  {"id": ["7","8","9"], "x": 206, "y": 165}
]

扩展说明 #

• 如果需要调整聚合的阈值，只需要修改aggregatePoints函数的第二个参数即可。
• 代码使用了循环合并的方式，逻辑简单易懂，适合你的点位规模；如果后续点位数量极大，可以考虑优化为基于空间网格的聚合算法（比如将地图划分为20px×20px的网格，同一网格内的点自动聚合），效率会更高。

内容的提问来源于stack exchange，提问作者takesuma