2D平面中基于指定成本函数的三角形集合直线分割最优算法求解

嘿，这个问题我之前也碰到过类似的场景——用直线分割2D三角形集合，还要尽量让左右两边的规模差不多，结合你定义的成本函数，我给你梳理几个实用的算法思路，还有具体的Python实现细节，你可以直接参考：

你的成本函数是 cost=-min(len(set_left), len(set_right))，说白了就是要让左右两侧的三角形数量里，较小的那个尽可能大，这样cost才会更小（更优）。那些被直线切到的碰撞三角形，目前不影响cost，但你也可以根据实际需求调整，比如把它们归到重心所在的一侧，进一步平衡两边的规模。

1. 候选直线启发式搜索法 #

这是最直接的思路：先生成一堆有潜力成为最优分割线的候选直线，挨个计算它们的cost，挑出最优的那个。

候选直线怎么生成？ #

• 过每个三角形的顶点，方向选常用的几个（水平、垂直、45°、135°）——这些直线要么刚好贴着三角形，要么能精准分开多个三角形，大概率能找到不错的解
• 取所有三角形重心的x/y坐标中位数，生成垂直于x/y轴的直线，作为初始候选
• 还可以用三角形的边所在直线，或者边的垂直平分线

具体步骤 #

• 生成所有候选直线（记得去重，避免重复计算）
• 对每条直线，遍历所有三角形，判断它属于左侧、右侧还是相交
• 计算每条直线的cost，保留cost最小的直线

2. 投影中位数分割法 #

这个方法计算量小，适合快速找到不错的初始解，原理是把三角形投影到某个方向上，用中位数来分割：

步骤 #

• 选几个候选方向（比如0°、45°、90°、135°，或者均匀采样10个方向）
• 对每个方向θ：
  • 把每个三角形的重心（或者顶点平均坐标）投影到θ方向的轴上，得到投影值
  • 找到这些投影值的中位数，生成垂直于θ的直线（刚好穿过中位数对应的点）
  • 计算这条直线的cost
• 从所有方向的最优直线里，选全局最优的

3. 迭代优化的局部搜索法 #

如果候选直线的解还不够理想，咱可以在最优候选直线的基础上做局部微调，进一步优化：

步骤 #

• 用上面两种方法得到一个初始最优直线
• 对直线进行微小调整：比如旋转1°以内的角度，或者平移几个单位
• 每次调整后计算cost，如果cost变小（也就是min(left, right)变大），就保留这个新直线
• 重复这个过程，直到无法再优化为止
• 可以加入随机扰动（比如偶尔随机选个方向调整），避免陷入局部最优

我给你写几个核心函数，你可以直接整合到你的代码里：

1. 判断三角形在直线的哪一侧 #

import math

def point_side(a, b, c, x, y):
    # 直线方程：ax + by + c = 0，返回点(x,y)代入后的符号
    return a * x + b * y + c

def triangle_side(a, b, c, triangle):
    # triangle是三个顶点的列表，每个顶点是(x,y)元组
    signs = [point_side(a, b, c, x, y) for x, y in triangle]
    pos_count = sum(s > 0 for s in signs)
    neg_count = sum(s < 0 for s in signs)
    
    if pos_count == 3:
        return "right"
    elif neg_count == 3:
        return "left"
    else:
        return "intersect"

2. 计算直线的成本 #

def calculate_cost(a, b, c, triangles):
    left_num = 0
    right_num = 0
    for tri in triangles:
        side = triangle_side(a, b, c, tri)
        if side == "left":
            left_num += 1
        elif side == "right":
            right_num += 1
    return -min(left_num, right_num)

3. 生成候选直线（示例） #

def generate_candidate_lines(triangles):
    lines = []
    vertices = []
    # 收集所有三角形的顶点
    for tri in triangles:
        vertices.extend(tri)
    
    # 生成水平直线（y = k → 0x + 1y -k = 0）
    for _, y in vertices:
        lines.append((0, 1, -y))
    # 生成垂直直线（x = k → 1x + 0y -k = 0）
    for x, _ in vertices:
        lines.append((1, 0, -x))
    # 生成45°直线（y = x + k → 1x -1y +k =0）
    for x, y in vertices:
        k = y - x
        lines.append((1, -1, k))
    # 生成135°直线（y = -x +k →1x +1y -k=0）
    for x, y in vertices:
        k = x + y
        lines.append((1, 1, -k))
    
    # 去重：归一化直线参数，避免重复计算相同直线
    unique_lines = []
    seen = set()
    for a, b, c in lines:
        # 计算最大公约数，归一化参数
        gcd_val = math.gcd(math.gcd(abs(a), abs(b)), abs(c))
        if gcd_val == 0:
            continue
        a_norm = a // gcd_val
        b_norm = b // gcd_val
        c_norm = c // gcd_val
        
        # 统一符号：让第一个非零参数为正
        if a_norm != 0:
            sign = 1 if a_norm > 0 else -1
        elif b_norm != 0:
            sign = 1 if b_norm > 0 else -1
        else:
            sign = 1 if c_norm > 0 else -1
        key = (a_norm * sign, b_norm * sign, c_norm * sign)
        
        if key not in seen:
            seen.add(key)
            unique_lines.append(key)
    return unique_lines

• 如果三角形数量很大，候选直线太多，可以随机采样一部分顶点生成直线，减少计算量
• 可以把碰撞的三角形按重心位置归到某一侧，进一步平衡两边规模
• 用并行计算（比如multiprocessing库）加速候选直线的cost计算，因为每条直线的计算是独立的

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