如何在闭合多边形内寻找指定中心的最大面积等腰梯形？

核心约束梳理 #

明确问题的硬性规则：

• 等腰梯形的两条平行边必须水平，中心与指定点完全重合
• 梯形中心为上下底中点连线的中点（因平行边水平，竖直中线为对称轴，中心即几何中心）
• 多边形可为凸/凹，梯形所有顶点及腰边必须在多边形内部或边界上

问题参数化简化 #

设指定中心坐标为(x0, y0)，将梯形用3个变量完全描述：

• h：梯形的高（上下底的垂直距离），则上底y坐标为y0 + h/2，下底y坐标为y0 - h/2
• a：上底半长，上底两端点为(x0±a, y0+h/2)
• b：下底半长，下底两端点为(x0±b, y0-h/2)

梯形面积公式简化为：S = (a + b) * h，目标是最大化S，同时满足所有几何约束。

分步解决方案 #

1. 计算水平扫描线的有效区间

对任意给定的h，分别计算两条水平扫描线y = y0+h/2和y = y0-h/2与多边形的交点：

• 遍历多边形所有边，找出扫描线与边的交点，将交点按x坐标排序
• 交点两两组成扫描线在多边形内的有效x区间，找到包含x0的区间
• 该区间内，x0到左右边界的最小距离即为当前扫描线对应的最大半长（a_max或b_max）

2. 二分法搜索最优高h

h的取值范围受限于多边形的y边界：

• 最小h为0（退化为线段），最大h为2 * min(y0 - y_min, y_max - y0)（y_min/y_max为多边形的最小/最大y坐标）
• 在[h_low, h_high]区间内二分搜索：
  • 对中间值h_mid，计算a_max和b_max
  • 验证腰边（(x0+a_max, y0+h_mid/2)到(x0+b_max, y0-h_mid/2)及对称边）是否完全在多边形内
  • 若有效，计算面积并更新最大值，尝试更大的h；若无效，尝试缩小h或按比例缩减a/b直到腰边有效

3. 凹多边形的特殊处理

凹多边形可能出现顶点在多边形内但腰边穿出的情况，需通过以下步骤验证：

• 检查腰边与多边形所有边是否存在非端点的交点
• 若存在交点，逐步缩小a和b的比例，直到腰边完全在多边形内
• 若缩小到一定比例仍无效，则放弃当前h，尝试更小的高

相对于矩形算法的改进点 #

之前改编矩形算法灵活性不足，核心原因是矩形强制a = b，而等腰梯形允许a ≠ b。本方案通过：

• 释放a = b的约束，独立计算上下底的最大半长
• 增加腰边的有效性检测，适配凹多边形场景
• 保留中心对称的核心逻辑，同时扩展参数维度，提升算法的适配性

参考伪代码 #

def max_area_isosceles_trapezoid(polygon, center):
    x0, y0 = center
    max_area = 0
    best_h, best_a, best_b = 0, 0, 0

    # 确定h的初始上下界
    y_coords = [p[1] for p in polygon]
    y_min, y_max = min(y_coords), max(y_coords)
    h_high = 2 * min(y0 - y_min, y_max - y0)
    h_low = 0

    # 二分搜索，精度控制到1e-6
    while h_high - h_low > 1e-6:
        h_mid = (h_low + h_high) / 2
        y_top = y0 + h_mid / 2
        y_bottom = y0 - h_mid / 2

        # 获取上底扫描线的最大对称半长
        top_intervals = get_horizontal_intervals(polygon, y_top)
        a_max = get_symmetric_extent(top_intervals, x0)
        if a_max <= 0:
            h_high = h_mid
            continue

        # 获取下底扫描线的最大对称半长
        bottom_intervals = get_horizontal_intervals(polygon, y_bottom)
        b_max = get_symmetric_extent(bottom_intervals, x0)
        if b_max <= 0:
            h_high = h_mid
            continue

        # 验证腰边是否在多边形内
        top_right = (x0 + a_max, y_top)
        bottom_right = (x0 + b_max, y_bottom)
        top_left = (x0 - a_max, y_top)
        bottom_left = (x0 - b_max, y_bottom)
        if is_segment_inside(top_right, bottom_right, polygon) and is_segment_inside(top_left, bottom_left, polygon):
            current_area = (a_max + b_max) * h_mid
            if current_area > max_area:
                max_area = current_area
                best_h, best_a, best_b = h_mid, a_max, b_max
            h_low = h_mid
        else:
            # 尝试缩小a/b比例，直到腰边有效
            scale = 1.0
            valid = False
            while scale > 0.1:
                a_scaled = a_max * scale
                b_scaled = b_max * scale
                tr_scaled = (x0 + a_scaled, y_top)
                br_scaled = (x0 + b_scaled, y_bottom)
                tl_scaled = (x0 - a_scaled, y_top)
                bl_scaled = (x0 - b_scaled, y_bottom)
                if is_segment_inside(tr_scaled, br_scaled, polygon) and is_segment_inside(tl_scaled, bl_scaled, polygon):
                    current_area = (a_scaled + b_scaled) * h_mid
                    if current_area > max_area:
                        max_area = current_area
                        best_h, best_a, best_b = h_mid, a_scaled, b_scaled
                    valid = True
                    break
                scale -= 0.1
            h_low = h_mid if valid else h_high

    # 生成最终梯形顶点
    y_top = y0 + best_h / 2
    y_bottom = y0 - best_h / 2
    return [
        (x0 - best_a, y_top),
        (x0 + best_a, y_top),
        (x0 + best_b, y_bottom),
        (x0 - best_b, y_bottom)
    ], max_area

# 辅助函数：获取水平扫描线与多边形的有效x区间
def get_horizontal_intervals(polygon, y):
    intersections = []
    n = len(polygon)
    for i in range(n):
        p1, p2 = polygon[i], polygon[(i+1)%n]
        y1, y2 = p1[1], p2[1]
        if (y1 - y) * (y2 - y) > 0:
            continue
        if y1 == y2:
            continue
        x = p1[0] + (y - y1) * (p2[0] - p1[0]) / (y2 - y1)
        intersections.append(x)
    intersections.sort()
    return [(intersections[i], intersections[i+1]) for i in range(0, len(intersections)-1, 2)]

# 辅助函数：计算包含x0的区间的最大对称延伸距离
def get_symmetric_extent(intervals, x0):
    for x_left, x_right in intervals:
        if x_left <= x0 <= x_right:
            return min(x0 - x_left, x_right - x0)
    return 0

# 辅助函数：判断线段是否完全在多边形内
def is_segment_inside(p1, p2, polygon):
    if not is_point_inside(p1, polygon) or not is_point_inside(p2, polygon):
        return False
    n = len(polygon)
    for i in range(n):
        edge_p1, edge_p2 = polygon[i], polygon[(i+1)%n]
        if segments_intersect(p1, p2, edge_p1, edge_p2, exclude_endpoints=True):
            return False
    return True

# 射线法判断点是否在多边形内
def is_point_inside(p, polygon):
    x, y = p
    inside = False
    n = len(polygon)
    for i in range(n):
        p1, p2 = polygon[i], polygon[(i+1)%n]
        x1, y1 = p1
        x2, y2 = p2
        if ((y1 > y) != (y2 > y)):
            x_intersect = (y - y1) * (x2 - x1) / (y2 - y1) + x1
            if x <= x_intersect:
                inside = not inside
    return inside

# 判断两条线段是否相交（可排除端点）
def segments_intersect(a1, a2, b1, b2, exclude_endpoints=False):
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    d1 = cross(b1, b2, a1)
    d2 = cross(b1, b2, a2)
    d3 = cross(a1, a2, b1)
    d4 = cross(a1, a2, b2)

    if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
        return True

    if exclude_endpoints:
        return False

    def on_segment(p, a, b):
        return min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= p[1] <= max(a[1], b[1])
    if d1 == 0 and on_segment(a1, b1, b2):
        return True
    if d2 == 0 and on_segment(a2, b1, b2):
        return True
    if d3 == 0 and on_segment(b1, a1, a2):
        return True
    if d4 == 0 and on_segment(b2, a1, a2):
        return True
    return False

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