如何在Python中不使用sklearn库找出50英里内的最小经纬度坐标簇

核心步骤说明 #

1. 实现Haversine距离计算函数 #

经纬度属于球面坐标，不能直接用欧氏距离计算，得用Haversine公式算出两点间的球面距离，再转换为英里单位。代码实现如下：

import math

def haversine_distance(lat1, lon1, lat2, lon2):
    # 将度数转为弧度
    lat1_rad = math.radians(lat1)
    lon1_rad = math.radians(lon1)
    lat2_rad = math.radians(lat2)
    lon2_rad = math.radians(lon2)
    
    # 计算经纬度差值
    dlat = lat2_rad - lat1_rad
    dlon = lon2_rad - lon1_rad
    
    # 应用Haversine公式
    a = math.sin(dlat/2)**2 + math.cos(lat1_rad) * math.cos(lat2_rad) * math.sin(dlon/2)**2
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    
    # 地球半径取3956英里，计算最终距离
    earth_radius_miles = 3956
    return earth_radius_miles * c

2. 生成连通图并找出所有簇 #

把每个坐标看作图的节点，若两点距离≤50英里，就在节点间连一条边。接着用广度优先搜索（BFS）找出所有连通子图，每个子图就是一个符合条件的簇：

def find_clusters(coordinates, max_distance=50):
    n = len(coordinates)
    # 构建邻接表存储节点间的连接关系
    adjacency = [[] for _ in range(n)]
    for i in range(n):
        lat1, lon1 = coordinates[i]
        for j in range(i+1, n):
            lat2, lon2 = coordinates[j]
            dist = haversine_distance(lat1, lon1, lat2, lon2)
            if dist <= max_distance:
                adjacency[i].append(j)
                adjacency[j].append(i)
    
    # 遍历所有节点，找出所有连通分量
    visited = [False] * n
    clusters = []
    for i in range(n):
        if not visited[i]:
            queue = [i]
            visited[i] = True
            current_cluster = []
            while queue:
                node = queue.pop(0)
                current_cluster.append(coordinates[node])
                # 遍历当前节点的所有邻居
                for neighbor in adjacency[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
            clusters.append(current_cluster)
    
    return clusters

3. 筛选最小簇 #

得到所有簇后，找出其中规模最小的（如果有多个规模相同的最小簇，会全部返回）：

def find_smallest_clusters(clusters):
    if not clusters:
        return []
    min_size = min(len(cluster) for cluster in clusters)
    return [cluster for cluster in clusters if len(cluster) == min_size]

完整使用示例 #

# 示例坐标列表（格式：(纬度, 经度)）
sample_coords = [
    (40.7128, -74.0060),  # 纽约
    (40.7306, -73.9352),  # 布鲁克林
    (34.0522, -118.2437), # 洛杉矶
    (34.0689, -118.4452), # 圣莫尼卡
    (41.8781, -87.6298),  # 芝加哥
    (41.9028, -87.6278)   # 芝加哥市中心
]

# 找出所有50英里内的簇
all_clusters = find_clusters(sample_coords)
# 筛选最小簇
smallest_clusters = find_smallest_clusters(all_clusters)

print("所有符合条件的簇：")
for idx, cluster in enumerate(all_clusters):
    print(f"簇 {idx+1}: {cluster}")

print("\n最小的簇：")
for idx, cluster in enumerate(smallest_clusters):
    print(f"最小簇 {idx+1}: {cluster}")

注意事项 #

• 若某个坐标和其他所有点的距离都超过50英里，它会被单独划分为一个簇（规模为1）。如果需求是最小簇至少包含2个点，只需在筛选时修改：min_size = min(len(c) for c in clusters if len(c)>=2)
• 当坐标数量很大时（比如上千个），双重循环构建邻接表的时间复杂度为O(n²)，效率较低。此时可先对坐标进行网格划分（按经纬度分块），只计算同块或相邻块内的点距离，减少计算量。

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