基于Shapely的含兴趣点最大无相交轴对齐矩形求解算法咨询

问题描述 #

给定一张包含若干（不一定为凸）多边形的图像，以及一个兴趣点，需要找到最大的轴对齐矩形（平行于图像坐标轴，不旋转），要求该矩形包含兴趣点且不与任何多边形相交。若存在多个解，可返回任意合理结果，优先选择更大的矩形，若简化代码导致偶尔偏大也可接受。

你的初步思路（中文翻译） #

xmin = 0
xmax = 1000  # 平面为1000x1000像素
ymin = 0
ymax = 1000
while True:
    for poly in polygons:
        intersection = poly.intersects(rect(xmin, xmax, ymin, ymax))
        if intersection:
            # 调整xmin/ymin增大，或xmax/ymax减小，确保不包含相交区域但仍覆盖兴趣点
            xmin += 1  # 示例调整方式，实际需根据相交位置处理
            # 或 xmax -= 1 / ymin += 1 / ymax -= 1
    # 遍历所有多边形后无相交则结束循环
    if all(not poly.intersects(box(xmin, ymin, xmax, ymax)) for poly in polygons):
        break

可行优化算法与实现 #

核心思路 #

1. 初始边界设定：以图像全局范围作为初始矩形边界，确保兴趣点在矩形内。
2. 约束边界计算：对每个多边形，计算它在兴趣点四个方向（左、右、下、上）的最近阻碍边界，快速缩小可行范围。
3. 验证与微调：根据约束得到初步矩形后，验证是否与多边形相交，若相交则向兴趣点方向微调边界，直到无相交。
4. 效率优化（可选）：用二分法替代逐像素调整，快速定位每个方向的最大可行边界。

完整代码实现 #

from shapely.geometry import Polygon, Point, box

def find_max_valid_rect(polygons, interest_point, img_dim=(1000, 1000)):
    px, py = interest_point.x, interest_point.y
    # 初始化全局边界
    x_min, x_max = 0, img_dim[0]
    y_min, y_max = 0, img_dim[1]

    # 第一步：计算所有多边形的约束边界
    for poly in polygons:
        # 跳过完全不与初始矩形相交的多边形，无约束作用
        if not poly.intersects(box(x_min, y_min, x_max, y_max)):
            continue
        
        # 处理x方向左约束：多边形中位于兴趣点左侧的最大x值（靠近兴趣点的左边界）
        left_x_coords = [coord[0] for coord in poly.exterior.coords if coord[0] < px]
        if left_x_coords:
            candidate_left = max(left_x_coords)
            if candidate_left > x_min:
                x_min = candidate_left
        
        # 处理x方向右约束：多边形中位于兴趣点右侧的最小x值（靠近兴趣点的右边界）
        right_x_coords = [coord[0] for coord in poly.exterior.coords if coord[0] > px]
        if right_x_coords:
            candidate_right = min(right_x_coords)
            if candidate_right < x_max:
                x_max = candidate_right
        
        # 处理y方向下约束：多边形中位于兴趣点下方的最大y值（靠近兴趣点的下边界）
        bottom_y_coords = [coord[1] for coord in poly.exterior.coords if coord[1] < py]
        if bottom_y_coords:
            candidate_bottom = max(bottom_y_coords)
            if candidate_bottom > y_min:
                y_min = candidate_bottom
        
        # 处理y方向上约束：多边形中位于兴趣点上方的最小y值（靠近兴趣点的上边界）
        top_y_coords = [coord[1] for coord in poly.exterior.coords if coord[1] > py]
        if top_y_coords:
            candidate_top = min(top_y_coords)
            if candidate_top < y_max:
                y_max = candidate_top

    # 第二步：验证并微调边界，确保完全无相交
    current_rect = box(x_min, y_min, x_max, y_max)
    intersecting = True
    while intersecting:
        intersecting = False
        for poly in polygons:
            if current_rect.intersects(poly):
                intersecting = True
                # 根据相交区域方向微调
                # 左半部分相交则右移左边界
                if poly.intersects(box(x_min, y_min, px, y_max)):
                    x_min += 1
                # 右半部分相交则左移右边界
                if poly.intersects(box(px, y_min, x_max, y_max)):
                    x_max -= 1
                # 下半部分相交则上移下边界
                if poly.intersects(box(x_min, y_min, x_max, py)):
                    y_min += 1
                # 上半部分相交则下移上边界
                if poly.intersects(box(x_min, py, x_max, y_max)):
                    y_max -= 1
                current_rect = box(x_min, y_min, x_max, y_max)
                break  # 调整后重新检查所有多边形

    return current_rect

# 测试示例
if __name__ == "__main__":
    # 定义测试多边形
    poly1 = Polygon([(150, 150), (250, 150), (250, 250), (150, 250)])
    poly2 = Polygon([(750, 750), (850, 750), (850, 850), (750, 850)])
    # 定义兴趣点
    interest_pt = Point(500, 500)
    
    max_rect = find_max_valid_rect([poly1, poly2], interest_pt)
    print("最大有效矩形边界：", max_rect.bounds)

算法说明 #

• 初始约束计算阶段通过提取多边形的关键坐标点，快速缩小矩形范围，避免了无意义的循环调整。
• 微调阶段针对相交区域的方向进行精准收缩，确保矩形始终包含兴趣点。
• 若需要更高效率，可将微调阶段替换为二分法：比如在x左边界的[初始x_min, px]区间内，二分查找最大的x值使得左半矩形不与任何多边形相交，其他方向同理。

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