def place_boxes()

in mujoco_worldgen/util/placement.py [0:0]

• 79 lines of code
• 26 McCabe index (conditional complexity)

def place_boxes(random_state, boxes, width, height, placement_margin=0.0):
    '''
    Tries to randomly place rectangular boxes between (0,0) and (width, height)
    boxes - list of dictionaries, each with keys 'size' and 'placement_xy'
            'size' must be (x,y)
            'placement_xy' is either None or (x_frac, y_frac) between 0 and 1
                (0, 0) is left lower corner, (.5, .5) is the center, etc
    width, height - dimensions of the outer bound to place boxes in
    placement_margin - minimum distance (orthogonal) between placed boxes
    Returns list of box positions (x,y) from left lower corner, or None if
        no solution found.
    '''
    width = float(width)
    height = float(height)
    assert width > 0 and height > 0, "invalid width, height"
    area = 0
    sizes = [box["size"] for box in boxes]
    for s in sizes:
        if s[0] > width - 2 * placement_margin or s[0] <= 0.0 or \
           s[1] > height - 2 * placement_margin or s[1] <= 0.0:
            return None
        area += (s[0] + placement_margin // 2) * (s[1] + placement_margin // 2)
    if area > 0.6 * (width - placement_margin) * (height - placement_margin) and len(sizes) > 1:
        return None
    if area > width * height:
        return None
    a_edge, b_edge = _get_edge_constraints(sizes, width, height, placement_margin)

    for _ in range(10):
        def get_matrices(xy):
            a_eq = []
            b_eq = []
            for idx, box in enumerate(boxes):
                if box["placement_xy"] is not None:
                    xy[idx] = box["placement_xy"][0] * (width - box["size"][0])
                    xy[idx + len(sizes)] = box["placement_xy"][1] * \
                        (height - box["size"][1])
                    for i in [idx, idx + len(sizes)]:
                        a = np.zeros(2 * len(sizes))
                        a[i] = 1.0
                        a_eq.append(a)
                        b_eq.append(xy[i])
            a_pairwise, b_pairwise, violated = _get_pairwise_constraints(xy, boxes, placement_margin)
            for idx, v in enumerate(violated):
                if not v:
                    for i in [idx, idx + len(sizes)]:
                        a = np.zeros(2 * len(sizes))
                        a[i] = 1.0
                        a_eq.append(a)
                        b_eq.append(xy[i])
            if len(a_eq) > 0:
                a_eq = np.stack(a_eq)
                b_eq = np.stack(b_eq)
            else:
                a_eq = None
                b_eq = None
            return a_eq, b_eq, a_pairwise, b_pairwise, violated

        best_xy = None
        best_violated = [True for _ in range(100)]
        for _ in range(10):
            xy = _get_random_xy(random_state, boxes, width, height, placement_margin)
            a_eq, b_eq, a_pairwise, b_pairwise, violated = get_matrices(xy)
            if sum(violated) < sum(best_violated):
                best_xy = xy
                best_violated = violated

        xy = best_xy
        a_eq, b_eq, a_pairwise, b_pairwise, violated = get_matrices(xy)

        # If it's not violated, than further optimization is not needed.
        if sum(violated) > -1e-4:
            return [(a, b) for a, b in zip(xy[:len(sizes)], xy[len(sizes):])]
        if len(a_pairwise) == 0:
            a = a_edge
            b = b_edge
        else:
            a = np.concatenate([a_edge, np.stack(a_pairwise)], 0)
            b = np.concatenate([b_edge, np.array(b_pairwise)], 0)

        random = random_state.uniform(-1, 1, 2 * len(sizes))
        sol = scipy.optimize.linprog(random, A_ub=-a, b_ub=-b, A_eq=a_eq, b_eq=b_eq)
        if sol.success:
            return _further_randomize(random_state, boxes, a, b, sol.x)
    return None