如何在正方形区域内无重叠均匀分布几何对象？

现有一个10×10的正方形区域，包含3个方形对象（obj_1st）和3个三角形对象（obj_2nd），需求是让这些对象在正方形内均匀分布且无重叠。原代码仅解决了重叠问题，但存在对象分布不均、视觉效果差的问题，同时边界处理逻辑存在漏洞。

输入数据 #

import numpy as np

square = np.array([[0, 0, 0, 0, 10, 0, 10, 10, 0, 10, 0, 0, 0, 0, 0]])

obj_1st = np.array([
    [1.0, 8.0, 0, 3.0, 8.0, 0, 3.0, 6.0, 0, 1.0, 6.0, 0, 1.0, 8.0, 0], 
    [6.0, 7.0, 0, 8.0, 7.0, 0, 8.0, 5.0, 0, 6.0, 5.0, 0, 6.0, 7.0, 0], 
    [3.0, 4.0, 0, 5.0, 4.0, 0, 5.0, 2.0, 0, 3.0, 2.0, 0, 3.0, 4.0, 0]
])

obj_2nd = np.array([
    [2.0, 3.0, 0, 3.0, 4.0, 0, 4.0, 3.0, 0, 2.0, 3.0, 0], 
    [2.0, 6.0, 0, 3.0, 7.0, 0, 4.0, 6.0, 0, 2.0, 6.0, 0], 
    [7.0, 3.0, 0, 8.0, 4.0, 0, 9.0, 3.0, 0, 7.0, 3.0, 0]
])

优化后的代码 #

import numpy as np
import matplotlib.pyplot as plt

# 计算对象的包围盒（min_x, max_x, min_y, max_y, center_x, center_y, width, height）
def get_bounding_box(obj):
    x_coords = obj[:, 0::3].flatten()
    y_coords = obj[:, 1::3].flatten()
    min_x = np.min(x_coords)
    max_x = np.max(x_coords)
    min_y = np.min(y_coords)
    max_y = np.max(y_coords)
    center_x = (min_x + max_x) / 2
    center_y = (min_y + max_y) / 2
    width = max_x - min_x
    height = max_y - min_y
    return (min_x, max_x, min_y, max_y, center_x, center_y, width, height)

# 检查两个对象是否重叠（含最小间距）
def are_objects_overlapping(obj1, obj2, min_gap=0.5):
    b1 = get_bounding_box(obj1)
    b2 = get_bounding_box(obj2)
    # 分离轴定理判断，加入最小间距
    return not (b1[1] + min_gap < b2[0] or b1[0] > b2[1] + min_gap or 
                b1[3] + min_gap < b2[2] or b1[2] > b2[3] + min_gap)

# 移动对象
def move_object(obj, vector):
    obj[:, 0::3] += vector[0]
    obj[:, 1::3] += vector[1]
    return obj

# 将对象限制在正方形内
def clamp_to_square(obj, square_size=10):
    bbox = get_bounding_box(obj)
    min_x, max_x, min_y, max_y = bbox[0], bbox[1], bbox[2], bbox[3]
    dx, dy = 0, 0
    
    # X轴边界修正
    if min_x < 0:
        dx = -min_x
    elif max_x > square_size:
        dx = square_size - max_x
    
    # Y轴边界修正
    if min_y < 0:
        dy = -min_y
    elif max_y > square_size:
        dy = square_size - max_y
    
    if dx != 0 or dy != 0:
        move_object(obj, (dx, dy))
    return obj

# 初始化均匀分布位置
def initialize_uniform_distribution(objects, square_size=10):
    total_objects = sum(len(obj_grp) for obj_grp in objects)
    # 按2x3网格分配6个对象
    grid_cols = 3
    grid_rows = 2
    cell_width = square_size / grid_cols
    cell_height = square_size / grid_rows
    
    idx = 0
    for obj_grp in objects:
        for obj in obj_grp:
            # 计算目标网格中心
            col = idx % grid_cols
            row = idx // grid_cols
            target_center_x = (col + 0.5) * cell_width
            target_center_y = (row + 0.5) * cell_height
            
            # 移动对象到目标中心
            bbox = get_bounding_box(obj)
            current_center_x, current_center_y = bbox[4], bbox[5]
            move_vec = (target_center_x - current_center_x, target_center_y - current_center_y)
            move_object(obj, move_vec)
            
            # 修正边界
            clamp_to_square(obj, square_size)
            idx += 1

# 主分布算法
def distribute_objects(objects, square_size=10, max_iterations=100, min_gap=0.5):
    # 先初始化均匀分布
    initialize_uniform_distribution(objects, square_size)
    
    iteration = 0
    while iteration < max_iterations:
        has_overlap = False
        # 整理所有对象到列表
        all_objects = []
        for grp in objects:
            all_objects.extend(grp)
        
        for i in range(len(all_objects)):
            for j in range(i+1, len(all_objects)):
                obj1 = all_objects[i]
                obj2 = all_objects[j]
                if are_objects_overlapping(obj1, obj2, min_gap):
                    has_overlap = True
                    # 获取两个对象的中心
                    b1 = get_bounding_box(obj1)
                    b2 = get_bounding_box(obj2)
                    center1 = np.array([b1[4], b1[5]])
                    center2 = np.array([b2[4], b2[5]])
                    
                    # 计算排斥方向和距离
                    direction = center1 - center2
                    distance = np.linalg.norm(direction)
                    if distance == 0:
                        direction = np.array([np.random.uniform(-1,1), np.random.uniform(-1,1)])
                        distance = np.linalg.norm(direction)
                    
                    # 计算需要移动的距离（确保分开到最小间距）
                    required_distance = (b1[6]/2 + b2[6]/2 + min_gap) + (b1[7]/2 + b2[7]/2 + min_gap)
                    move_distance = required_distance - distance
                    if move_distance < 0:
                        move_distance = 0
                    
                    # 归一化方向，加入衰减因子避免过度移动
                    move_vec = (direction / distance) * move_distance * 0.5
                    
                    # 移动两个对象
                    move_object(obj1, move_vec)
                    move_object(obj2, -move_vec)
                    
                    # 修正边界
                    clamp_to_square(obj1, square_size)
                    clamp_to_square(obj2, square_size)
        
        if not has_overlap:
            break
        iteration += 1

# 绘图函数
def plot_scene(square, objects):
    plt.figure(figsize=(8, 8))
    # 绘制正方形
    sq_x = square[0][0::3]
    sq_y = square[0][1::3]
    plt.plot(sq_x, sq_y, color='black', linewidth=2, label='Square')
    
    # 绘制方形对象
    for obj in obj_1st:
        x = obj[0::3]
        y = obj[1::3]
        plt.plot(x, y, color='blue', linewidth=1.5, label='Square Object' if obj is obj_1st[0] else "")
    
    # 绘制三角形对象
    for obj in obj_2nd:
        x = obj[0::3]
        y = obj[1::3]
        plt.plot(x, y, color='red', linewidth=1.5, label='Triangle Object' if obj is obj_2nd[0] else "")
    
    plt.title('Uniformly Distributed Objects without Overlapping')
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.grid(True)
    plt.axis('equal')
    plt.legend()
    plt.show()

# 执行分布并绘图
if __name__ == "__main__":
    square = np.array([[0, 0, 0, 0, 10, 0, 10, 10, 0, 10, 0, 0, 0, 0, 0]])
    obj_1st = np.array([
        [1.0, 8.0, 0, 3.0, 8.0, 0, 3.0, 6.0, 0, 1.0, 6.0, 0, 1.0, 8.0, 0], 
        [6.0, 7.0, 0, 8.0, 7.0, 0, 8.0, 5.0, 0, 6.0, 5.0, 0, 6.0, 7.0, 0], 
        [3.0, 4.0, 0, 5.0, 4.0, 0, 5.0, 2.0, 0, 3.0, 2.0, 0, 3.0, 4.0, 0]
    ])
    obj_2nd = np.array([
        [2.0, 3.0, 0, 3.0, 4.0, 0, 4.0, 3.0, 0, 2.0, 3.0, 0], 
        [2.0, 6.0, 0, 3.0, 7.0, 0, 4.0, 6.0, 0, 2.0, 6.0, 0], 
        [7.0, 3.0, 0, 8.0, 4.0, 0, 9.0, 3.0, 0, 7.0, 3.0, 0]
    ])
    
    objects = [obj_1st, obj_2nd]
    distribute_objects(objects)
    plot_scene(square, objects)

优化说明 #

• 均匀初始化：将6个对象分配到2×3的网格中，每个对象初始位于网格中心，从根源避免堆积
• 精确重叠判断：使用包围盒+最小间距的分离轴定理，确保对象间有合理空隙
• 智能排斥移动：基于对象中心距离计算移动向量，加入衰减因子避免过度移动，同时保证对象分开到安全距离
• 修复边界处理：直接修改原对象的坐标，确保边界修正生效
• 收敛控制：设置最大迭代次数，避免无限循环

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