Algorithm for merging overlapping rectangles

Question

The following code is part of an application I maintain that has a VT100/Xterm style graphical user interface that is implemented using text (Think Midnight Commander. Retro, I know.)

Part of the code involves producing collections of rectangles that represent regions of the screen that may require redrawing. These are then chopped up into "slices" of rectangles with a height of 1. After this, any overlapping rectangles are merged together to produce a final set of non-overlapping rectangles. The code then goes on to check to see exactly what parts of those regions have changed since the last time the client was updated and the ultimate goal is to produce the smallest amount of protocol code to the client, which is usually somewhere over the network, in order to redraw its screen.

After profiling detected a bottleneck there, I recently attacked the part of the code that merges the rectangles together, as a full-screen redraw of all components can generate a couple of thousand of the above "slices" (which merges down to 24 quite happily). The old algorithm naively checked every element in the array with every other element, making it quadratic, whereas my new algorithm seems to be roughly linear.

At the centre of the algorithm, however, there are three special cases for how to merge the rectangles. I am almost certain that these can be generalised into one non-branching statement, but it eludes me. I would appreciate any pointers in that direction, or any other critiques of the algorithm in general.

(Aside: compare_slices orders by the Y co-ordinate of a rectangle's origin, then by the X co-ordinate.)

static vector<rectangle> merge_overlapping_slices(vector<rectangle> rectangles)
{
    sort(rectangles.begin(), rectangles.end(), compare_slices);

    BOOST_AUTO(first_slice, rectangles.begin());

    // Iterate through adjacent slices, merging any that overlap.
    for (; first_slice != rectangles.end(); ++first_slice)
    {
        // Skip over any slices that have been merged.
        if (first_slice->size.height == 0)
        {
            continue;
        }

        BOOST_AUTO(second_slice, first_slice + 1);

        // Iterate through all adjacent slices that share a y-coordinate
        // until we either run out of slices, or cannot merge a slice.
        for (; 
             second_slice != rectangles.end()
          && first_slice->origin.y == second_slice->origin.y;
             ++second_slice)
        {
            // If there is an overlap, then merge the slices and continue
            // to the next adjacent slice.
            if (first_slice->origin.x + first_slice->size.width
             >= second_slice->origin.x)
            {
                // Change the first slice so that it is the union of both
                // slices.  Note we only have to consider the x-coordinate
                // since we already know that both slices share the same
                // y-axis.
                s32 required_width;

                // !!NOTE: this is the code I would like to generalise
                if (first_slice->origin.x == second_slice->origin.x)
                {
                    // Both slices share the same origin, so we can simply
                    // take the width of the widest slice.
                    required_width = (std::max)(
                        first_slice->size.width, second_slice->size.width);
                }
                else if (first_slice->origin.x + first_slice->size.width
                      >= second_slice->origin.x + second_slice->size.width)
                {
                    // The first slice completely encompasses the second,
                    // so we can just take the width of the first slice.
                    required_width = first_slice->size.width;
                }
                else
                {
                    // The slices only partially overlap.  Work out the union
                    // of the slices.
                    required_width = second_slice->size.width
                      + (second_slice->origin.x - first_slice->origin.x);
                }

                first_slice->size.width = required_width;

                // Mark the second slice as having been merged.
                second_slice->size.height = 0;
            }
            // Otherwise, break out of this iteration and try to merge a
            // different slice.
            else
            {
                break;
            }
        }
    }

    // Snip out any rectangles that have been merged (have 0 height).
    rectangles.erase(remove_if(
            rectangles.begin()
          , rectangles.end()
          , has_empty_height)
      , rectangles.end());

    return rectangles;
}

Answer 1

So I cleaned up and simplified the inner loop in the code quite a lot:

static vector<rectangle> merge_overlapping_slices(vector<rectangle> rectangles)
{
    sort(rectangles.begin(), rectangles.end(), compare_slices);

    BOOST_AUTO(first_slice, rectangles.begin());

    // Iterate through adjacent slices, merging any that overlap.
    for (; first_slice != rectangles.end(); ++first_slice)
    {
        // Skip over any slices that have been merged.
        if (first_slice->size.height == 0)
        {
            continue;
        }

        BOOST_AUTO(second_slice, first_slice + 1);

        // Iterate through all adjacent slices that share a y-coordinate
        // until we either run out of slices, or cannot merge a slice.
        for (; 
             second_slice != rectangles.end()
          && first_slice->origin.y == second_slice->origin.y
          && first_slice->origin.x + first_slice->size.width >= second_slice->origin.x;
             ++second_slice)
        {
            // Set the width of the first slice to be equivalent to the
            // rightmost point of the two rectangles.
            first_slice->size.width = (std::max)(
                first_slice->origin.x + first_slice->size.width
              , second_slice->origin.x + second_slice->size.width)
              - first_slice->origin.x;

            // Mark the second slice as having been merged.
            second_slice->size.height = 0;
        }
    }

    // Snip out any rectangles that have been merged (have 0 height).
    rectangles.erase(remove_if(
            rectangles.begin()
          , rectangles.end()
          , has_empty_height)
      , rectangles.end());

    return rectangles;
}

Furthermore, it occurs to me that all of the variables used in the body of the loop are already "touched" by the loop control. This would, according to my understanding of the situation, reduce the possible hit from branching.

In other words, I should stop fretting about this and focus efforts elsewhere.

(Academically, though, I'm still interested in something that would flatten the call to std::max to some basic arithmetic.)