双线性插值：如何选取包含目标点的最小网格矩形（修复边界问题）

我明白你现在的困扰——双线性插值在规则网格上实现起来看似简单，但边界场景的处理确实容易掉坑。你手里有排序后的规则网格顶点列表，写的代码在非边界情况可能没问题，但碰到网格边缘的点就失效了，核心问题其实是如何准确找到包含目标点(x,y)的最小矩形的四个顶点。

先看一下你给出的原始代码：

def f(x, y, points): 
    for i in range(len(points)-1, -1, -1): 
        if (x>points[i][0])and(y>points[i][1]): 
            break 
    try: 
        pp = [points[i], points[i+1]] 
    except IndexError: 
        pp = [points[i], points[i-1]] 
    for j in range(len(points)): 
        if (x<points[j][0])and(y<points[j][1]): 
            break 
    pp.append(points[j-1]) 
    pp.append(points[j]) 
    (x1, y1, q11), (_x1, y2, q12), (x2, _y1, q21), (_x2, _y2, q22) = pp 
    return (q11 * (x2 - x) * (y2 - y) + q21 * (x - x1) * (y2 - y) + q12 * (x2 - x) * (y - y1) + q22 * (x - x1) * (y - y1)) / ((x2 - x1) * (y2 - y1))

这段代码的问题在于：

• 手动遍历查找顶点的逻辑太脆弱，尤其是边界场景（比如目标点在网格最左/最右列、最上/最下行），很容易出现索引越界或者选到错误的顶点；
• 没有利用规则网格的核心特性：x和y坐标都是有序且重复出现的，完全可以用更高效、更可靠的方式定位顶点。

正确的解决思路：利用有序序列查找+坐标映射 #

既然是规则网格，我们可以先提取出所有唯一的x、y坐标（因为是规则的，同一列x相同，同一行y相同），这些坐标必然是有序的。然后用二分查找快速定位目标点所在的x区间和y区间，再找到对应的四个顶点。

具体实现步骤如下：

1. 预处理网格坐标：提取并排序所有唯一的x、y坐标，同时建立坐标到z值的映射（避免每次查找都遍历整个顶点列表）。
2. 二分查找定位区间：用bisect模块快速找到目标点(x,y)所在的x左右边界和y上下边界。
3. 获取四个顶点：通过坐标映射直接取出四个顶点的z值，代入插值公式计算。

改进后的代码 #

import bisect

def bilinear_interpolation(x, y, points):
    # 预处理：提取有序的唯一x、y坐标，建立坐标到z值的映射
    x_coords = sorted({p[0] for p in points})
    y_coords = sorted({p[1] for p in points})
    coord_to_z = {(p[0], p[1]): p[2] for p in points}
    
    # 先判断点是否在网格范围内（可选，根据需求处理外插场景）
    if x < x_coords[0] or x > x_coords[-1] or y < y_coords[0] or y > y_coords[-1]:
        raise ValueError("目标点超出网格边界，请检查输入")
    
    # 用二分查找找到x所在的区间索引
    x_idx = bisect.bisect_left(x_coords, x)
    # 处理x等于最大x的情况
    if x_idx == len(x_coords):
        x_idx -= 1
    x_left = x_coords[x_idx - 1] if x_idx > 0 else x_coords[x_idx]
    x_right = x_coords[x_idx]
    
    # 同理处理y坐标
    y_idx = bisect.bisect_left(y_coords, y)
    if y_idx == len(y_coords):
        y_idx -= 1
    y_bottom = y_coords[y_idx - 1] if y_idx > 0 else y_coords[y_idx]
    y_top = y_coords[y_idx]
    
    # 获取四个顶点的z值
    q11 = coord_to_z[(x_left, y_bottom)]  # 左下
    q12 = coord_to_z[(x_left, y_top)]     # 左上
    q21 = coord_to_z[(x_right, y_bottom)] # 右下
    q22 = coord_to_z[(x_right, y_top)]    # 右上
    
    # 计算双线性插值结果（处理分母为0的特殊情况，比如点在网格线上）
    denominator = (x_right - x_left) * (y_top - y_bottom)
    if denominator == 0:
        return q11
    
    return (q11 * (x_right - x) * (y_top - y) +
            q21 * (x - x_left) * (y_top - y) +
            q12 * (x_right - x) * (y - y_bottom) +
            q22 * (x - x_left) * (y - y_bottom)) / denominator

为什么这段代码能解决边界问题？ #

• bisect模块专门用于有序序列的查找，能准确处理目标点等于边界坐标的情况；
• 我们加入了明确的边界判断，提前拦截超出网格的点（你也可以改成外插逻辑，比如直接返回边界顶点的z值）；
• 坐标映射的方式避免了遍历整个顶点列表，既高效又不会因为索引错误选到错误的顶点。

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