atlas.d

struct Node {
    Rectangle area;

    string name;
    Image image;

    Node* left;
    Node* right;

    Node* insert(Image image, string name) {
        // http://www.blackpawn.com/texts/lightmaps/
        if(left !is null && right !is null) { // it's not a leaf
            Node* node = left.insert(image, name);
            if(node !is null) {
                return node;
            }

            return right.insert(image, name);
        }

        if(this.image !is null) {
            return null; // no space for an image here!
        }

        if(image.width > area.width || image.height > area.height) {
            return null; // image is too big
        }

        if(image.width == area.width && image.height == area.height) {
            return &this; // fits perfectly!
        }

        int delta_width = area.width - image.width;
        int delta_height = area.height - image.height;

        assert(delta_width >= 0 && delta_height >= 0);

        left = new Node();
        right = new Node();

        if(delta_width > delta_height) {
            left.area = Rectangle(area.x, area.y, image.width, area.height);
            right.area = Rectangle(area.x+image.width, area.y,
                                    area.width-image.width, area.height);
        } else {
            left.area = Rectangle(area.x, area.y, area.width, image.height);
            right.area = Rectangle(area.x, area.y+image.height,
                                    area.width, area.height - image.height);
        }

        return left.insert(image, name);
    }
}