Method SkylinePackRects

source/rect_packing.cpp:102–190

// ***********************************************************************

void Packing::SkylinePackRects(Arena* pScratchMem, ResizableArray<Rect>& rects, i32 width, i32 height) {
    for (i64 i = 0; i < rects.count; i++) {
        rects[i].ordering = (int)i;
    }

    // Sort by a heuristic
    Sort(rects.pData, rects.count, SortByHeight());

    i32 maxX = 0;
    i32 maxY = 0;
    i32 totalArea = 0;

    ResizableArray<SkylineNode> nodes(pScratchMem);

    nodes.PushBack({ 0, 0, width });

    for (Rect& rect : rects) {
        i32 bestHeight = height;
        i32 bestWidth = width;
        i32 bestNode = -1;
        i32 bestX, bestY;
        // We're going to search for the best location for this rect along the skyline
        for (i64 i = 0; i < nodes.count; i++) {
            SkylineNode& node = nodes[i];
            i32 highestY = CanRectFit(nodes, (i32)i, rect.w, rect.h, width, height);
            if (highestY != -1) {
                // Settling a tie here on best height by checking lowest width we can use up
                if (highestY + rect.h < bestHeight || (highestY + rect.h == bestHeight && node.width < bestWidth)) {
                    bestNode = (int)i;
                    bestWidth = node.width;
                    bestHeight = highestY + rect.h;
                    bestX = node.x;
                    bestY = highestY;
                }
            }
        }

        if (bestNode == -1)
            continue;  // We failed

        // Add the actual rect, changing the skyline

        // First add the new node
        SkylineNode newNode;
        newNode.width = rect.w;
        newNode.x = bestX;
        newNode.y = bestY + rect.h;
        nodes.Insert(bestNode, newNode);

        // Now we have to find all the nodes underneath that new skyline level and remove them
        for (int i = bestNode + 1; i < (int)nodes.count; i++) {
            SkylineNode& node = nodes[i];
            SkylineNode& prevNode = nodes[i - 1];
            // Check to see if the current node is underneath the previous node
            // Remember that i starts as the first node after we inserted, so the previous node is the one we inserted
            if (node.x < prevNode.x + prevNode.width) {
                // Draw a picture of this
                i32 amountToShrink = (prevNode.x + prevNode.width) - node.x;