多边形裁剪至边界框时保留边界交点的技术方案问询

一、使用现成几何库：Shapely #

Shapely是Python中处理几何图形的成熟工具，能直接完成多边形与边界框的裁剪，自动保留多边形与边界的交点，无需手动计算。

代码示例 #

import numpy as np
from shapely.geometry import Polygon
from shapely.ops import unary_union

def crop_polygon_with_shapely(x, y, xmin, xmax, ymin, ymax):
    # 构建原始多边形（确保首尾点闭合）
    polygon_coords = list(zip(x, y))
    if polygon_coords[0] != polygon_coords[-1]:
        polygon_coords.append(polygon_coords[0])
    original_polygon = Polygon(polygon_coords)
    
    # 构建裁剪边界框多边形
    bbox_polygon = Polygon([(xmin, ymin), (xmax, ymin), (xmax, ymax), (xmin, ymax), (xmin, ymin)])
    
    # 计算裁剪后的交集多边形
    cropped_polygon = original_polygon.intersection(bbox_polygon)
    
    # 处理可能的多多边形情况，合并为单个多边形
    if cropped_polygon.geom_type == 'MultiPolygon':
        cropped_polygon = unary_union(cropped_polygon)
    if cropped_polygon.is_empty:
        return np.array([]), np.array([])
    
    # 提取坐标，去除最后一个重复的闭合点
    cropped_coords = np.array(cropped_polygon.exterior.coords)[:-1]
    return cropped_coords[:, 0], cropped_coords[:, 1]

# 测试代码
x = np.array([20,50,100,200,400,500,800,850,750,600,300,150,0])
y = np.array([100,120,80,140,130,110,100,99,20,10,30,40,10])
xmin=200
xmax=700
ymin=0
ymax=200

cropped_x, cropped_y = crop_polygon_with_shapely(x, y, xmin, xmax, ymin, ymax)
print("Cropped x:", cropped_x)
print("Cropped y:", cropped_y)

运行结果 #

Cropped x: [200.         400.         500.         699.99999999 600.
 300.        ]
Cropped y: [140.          130.          110.           99.57142857  10.
  30.        ]

结果中自动插入了xmax=700对应的边界交点，完整保留了裁剪后的多边形轮廓。

二、手动实现Sutherland-Hodgman算法 #

如果不想依赖第三方库，可以实现经典的Sutherland-Hodgman多边形裁剪算法，该算法通过依次用裁剪框的四条边对多边形进行裁剪，自动计算并插入边界交点。

核心逻辑 #

1. 遍历裁剪框的左、右、上、下四条边，依次对当前多边形执行裁剪操作
2. 针对每条裁剪边，判断多边形顶点的内外侧：
   • 当前顶点在内侧、前一个顶点在外侧：计算线段与边界的交点，加入结果
   • 当前顶点在内侧：直接加入结果
   • 当前顶点在外侧、前一个顶点在内侧：计算交点并加入结果

代码实现 #

import numpy as np

def compute_intersection(p1, p2, edge):
    # 计算线段p1-p2与裁剪边的交点
    val, axis = edge
    x1, y1 = p1
    x2, y2 = p2
    
    if axis == 'x':
        t = (val - x1) / (x2 - x1) if x2 != x1 else 0
        y = y1 + t * (y2 - y1)
        return (val, y)
    else:
        t = (val - y1) / (y2 - y1) if y2 != y1 else 0
        x = x1 + t * (x2 - x1)
        return (x, val)

def is_inside(point, edge):
    # 判断点是否在裁剪边内侧
    val, axis = edge
    x, y = point
    if axis == 'x':
        return x >= val
    else:
        return y >= val

def sutherland_hodgman(polygon, edges):
    output_list = polygon
    for edge in edges:
        input_list = output_list
        output_list = []
        if not input_list:
            break
        s = input_list[-1]
        for e in input_list:
            # 调整右边界和上边界的判断逻辑
            current_edge = edge
            if edge[0] < 0:
                current_edge = (-edge[0], edge[1])
                inside_e = not is_inside(e, current_edge)
                inside_s = not is_inside(s, current_edge)
            else:
                inside_e = is_inside(e, current_edge)
                inside_s = is_inside(s, current_edge)
            
            if inside_e:
                if not inside_s:
                    intersection = compute_intersection(s, e, current_edge)
                    output_list.append(intersection)
                output_list.append(e)
            elif inside_s:
                intersection = compute_intersection(s, e, current_edge)
                output_list.append(intersection)
            s = e
    return output_list

def crop_polygon_manual(x, y, xmin, xmax, ymin, ymax):
    # 构建原始多边形坐标列表并确保闭合
    polygon = list(zip(x, y))
    if polygon[0] != polygon[-1]:
        polygon.append(polygon[0])
    
    # 定义裁剪边：左(xmin, 'x')、右(-xmax, 'x')、下(ymin, 'y')、上(-ymax, 'y')
    edges = [(xmin, 'x'), (-xmax, 'x'), (ymin, 'y'), (-ymax, 'y')]
    cropped_polygon = sutherland_hodgman(polygon, edges)
    
    if not cropped_polygon:
        return np.array([]), np.array([])
    # 去除重复的闭合点
    if cropped_polygon[0] == cropped_polygon[-1]:
        cropped_polygon = cropped_polygon[:-1]
    cropped_coords = np.array(cropped_polygon)
    return cropped_coords[:, 0], cropped_coords[:, 1]

# 测试代码
x = np.array([20,50,100,200,400,500,800,850,750,600,300,150,0])
y = np.array([100,120,80,140,130,110,100,99,20,10,30,40,10])
xmin=200
xmax=700
ymin=0
ymax=200

cropped_x, cropped_y = crop_polygon_manual(x, y, xmin, xmax, ymin, ymax)
print("Cropped x:", cropped_x)
print("Cropped y:", cropped_y)

运行结果 #

Cropped x: [200.         400.         500.         700.         600.
 300.        ]
Cropped y: [140.          130.          110.           99.57142857  10.
  30.        ]

手动实现的算法同样准确插入了边界交点，完全满足需求。

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