如何使用Shapely计算形状间平均距离？求N个多边形最近邻平均距离最快方法

1. 能否使用Shapely计算一组形状之间的平均距离？ #

可以实现，但Shapely没有直接的内置函数，需要手动计算所有形状对的距离后取平均。核心思路是利用Shapely内置的distance()方法（返回两个几何对象间的最小距离），结合遍历逻辑完成统计：

• 若计算无序对平均（即A-B和B-A视为同一对，避免重复计算），用组合遍历；若计算有序对平均，用笛卡尔积遍历（包含自身距离，值为0）
• 收集所有距离值后求和，除以总对数得到平均值

示例代码：

from shapely.geometry import Polygon
import itertools

# 生成示例多边形集合
polygons = [
    Polygon([(0,0), (0,1), (1,1), (1,0)]),
    Polygon([(2,2), (2,3), (3,3), (3,2)]),
    Polygon([(5,5), (5,6), (6,6), (6,5)])
]

# 计算所有无序对的距离（无重复）
distances = []
for poly1, poly2 in itertools.combinations(polygons, 2):
    distances.append(poly1.distance(poly2))

# 计算平均距离
average_distance = sum(distances) / len(distances)
print(f"平均距离: {average_distance}")

2. 对于一组N个多边形，如何以最快方式计算所有多边形与其最近邻的平均距离？ #

需根据多边形数量N的规模选择方案：

小N场景（N<1000）：暴力遍历 #

实现简单，直接遍历每个多边形与其他所有多边形的距离，记录最小非自身距离，最后求平均值。时间复杂度为O(N²)，小数据量下效率可接受。

示例代码：

min_distances = []
for i, poly in enumerate(polygons):
    min_dist = float('inf')
    for j, other_poly in enumerate(polygons):
        if i == j:
            continue
        dist = poly.distance(other_poly)
        if dist < min_dist:
            min_dist = dist
    min_distances.append(min_dist)

average_min_distance = sum(min_distances) / len(min_distances)
print(f"最近邻平均距离: {average_min_distance}")

大N场景（N≥1000）：空间索引（R-tree）优化 #

暴力遍历效率会急剧下降，此时用R-tree空间索引筛选候选邻近多边形，避免与所有对象计算距离，时间复杂度可降至接近O(N log N)。核心逻辑是：

1. 用多边形的边界框构建R-tree索引
2. 对每个多边形，查询边界框相交/接近的候选多边形
3. 仅在候选集中计算实际距离，找到最近邻
4. 极端情况（无候选结果）下，回退到暴力遍历

示例代码：

from rtree import index

# 构建R-tree索引，存储多边形的边界框与对应索引
idx = index.Index()
for i, poly in enumerate(polygons):
    idx.insert(i, poly.bounds)

min_distances = []
for i, poly in enumerate(polygons):
    min_dist = float('inf')
    # 查询边界框与当前多边形重叠的候选对象索引
    candidate_indices = list(idx.intersection(poly.bounds))
    for j in candidate_indices:
        if i == j:
            continue
        other_poly = polygons[j]
        dist = poly.distance(other_poly)
        if dist < min_dist:
            min_dist = dist
    # 处理无候选的极端情况
    if min_dist == float('inf'):
        for j, other_poly in enumerate(polygons):
            if i == j:
                continue
            dist = poly.distance(other_poly)
            if dist < min_dist:
                min_dist = dist
    min_distances.append(min_dist)

average_min_distance = sum(min_distances) / len(min_distances)
print(f"最近邻平均距离: {average_min_distance}")

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