grid-based manhattan boxing

File: file.png (41KB, 957x418px) Image search: [Google]

41KB, 957x418px

maybe one of you anons has a good idea for this.

basically I want to separate a connected area in a 2d grid into the least amount of boxes as fast as possible. Are there any good algorithms lying around?

I came up with this pseudo code to illustrate what I want to do

field = [
    [ 0, 0, 0, 0, 0 ],
    [ 0, 1, 1, 0, 0 ],
    [ 0, 1, 1, 1, 0 ],
    [ 0, 1, 1, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ],
]

func manhattan_boxing(field) {

    // collect boxes
    var boxes = [];

    // array of point(x,y)
    var open_cells = get_occupied_points(field);

    while (!open_cells.empty()) {

        // pick a point at random
        var point = random(open_cells);

        // Expansion count to N, E, S, W
        var expansions = {0,0,0,0};

        int n_expansions = 0;

        // repeatedly try to expand in all 4 directions until nothing can be expanded anymore
        do {
            // try to expand north
            if (can_expand_north(field, expansions, point)) {
                expansions[0]++;
                n_expansions++;
            }

            // try to expand east
            if (can_expand_east(field, expansions, point)) {
                expansions[1]++;
                n_expansions++;
            }

            // try to expand south
            if (can_expand_south(field, expansions, point)) {
                expansions[2]++;
                n_expansions++;
            }

            // try to expand west
            if (can_expand_west(field, expansions, point)) {
                expansions[3]++;
                n_expansions++;
            }

        } until (n_expansions == 0);

        box = get_box(point, expansions); // returns a box, which is defined by a minimum and maximum point of its spanning diagonal vectors

        // add box to box collection
        boxes.add(box);

        // remove all open cells that are within the box
        remove_open_cells(open_cells, box);

    }

    return boxes;
}

Any ideas?