计算点到点、线段、多边形距离的高效实现方法咨询

性能瓶颈分析 #

• 核心原因是双层嵌套for循环：当前逻辑时间复杂度为O(10000 * 40401)，累计超过4亿次运算，Python原生循环本身执行开销很高，必然导致耗时过长
• 重复创建Shapely Point 对象：每次循环都实例化Point类，初始化开销被放大了数百万倍
• 无空间剪枝逻辑：每个点都要遍历全部4万个圆心，没有提前过滤掉大范围明显不符合距离要求的对象，算力浪费严重

优化方案 #

方案1：Numpy向量化改造（适配当前点到点匹配场景） #

点到点的欧氏距离计算完全可以用Numpy广播机制代替循环，不需要重复创建Shapely对象，改造后代码运行效率可以提升上千倍，从小时级降到秒级：

from timeit import default_timer as timer
import numpy as np

start = timer()

# 生成10000个随机点
points = np.random.rand(10000, 2)
# 生成圆心网格（代替原本的循环赋值）
linspace = np.linspace(-1, 1, num=201)
x_grid, y_grid = np.meshgrid(linspace, linspace)
circles = np.column_stack([x_grid.ravel(), y_grid.ravel()])

result = np.empty([10000, 2], dtype=object)
threshold = 0.005
# 阈值提前取平方，后续计算距离平方即可，避免开根号开销
threshold_sq = threshold ** 2

for i in range(points.shape[0]):
    # 向量化计算当前点到所有圆心的距离平方
    dist_sq = np.sum((points[i] - circles)**2, axis=1)
    match_idx = np.argwhere(dist_sq < threshold_sq)
    if len(match_idx) > 0:
        result[i] = circles[match_idx[0][0]]

end = timer()
print(end - start)

方案2：空间索引改造（适配后续加线段、多边形的复杂场景） #

如果后续需要支持点到线段、多边形的距离计算，推荐使用Shapely自带的STRtree空间索引，提前对所有几何对象（点、线段、多边形）建索引，每次查询仅判断和目标点空间邻近的少量对象，不需要遍历全量数据：

from timeit import default_timer as timer
import numpy as np
from shapely.geometry import Point
from shapely.strtree import STRtree

start = timer()

# 生成10000个随机点
points = np.random.rand(10000, 2)
# 生成圆心网格
linspace = np.linspace(-1, 1, num=201)
x_grid, y_grid = np.meshgrid(linspace, linspace)
circles = np.column_stack([x_grid.ravel(), y_grid.ravel()])

# 所有几何对象（后续要加的线段、多边形都可以直接放进这个列表）转成Shapely对象
geoms = [Point(xy) for xy in circles]
# 构建空间索引
tree = STRtree(geoms)

threshold = 0.005
result = np.empty([10000, 2], dtype=object)

for i in range(points.shape[0]):
    p = Point(points[i])
    # 先查空间索引，只返回距离小于阈值的候选对象，仅遍历候选即可
    candidates = tree.query(p.buffer(threshold))
    for cand in candidates:
        if p.distance(cand) < threshold:
            result[i] = (cand.x, cand.y)
            break

end = timer()
print(end - start)

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