How to optimize the list of "dirty regions" when they intersect?

Question

I have a list of "dirty regions" (for texture). The rectangles in it may overlap with each other. I want to optimize this list so that there are no overlaps. Accordingly, when I use this list, data will not be copied twice in the intersecting regions.

Is there some kind of algorithm that might work for this? The ideas I have don't seem to be the most optimal.

Answer 1

One method of doing this is based on horizontal scanning, where you draw lines across the image, counting the edges that are passed to determine whether you are inside a rectangle, as demonstrated in this fiddle. which produces the following output, where the filled rectangles are the input and the stroked rectangles are the output:

It first finds all of the places where the result of this scanning could change, the tops and bottoms of the rectangles, then sorts and filters them for unique values.

for (let rect of rects) {
    yCoordinates.push(rect.starty, rect.endy);
}

#Then we assess scan lines that cross between those y coordinates:
for (let i = 0; i < yCoordinates.length - 1; i++) {
    let y = (yCoordinates[i] + yCoordinates[i+1]) / 2;
    
    #Finding all of left of the right sides of the rectangles along that line:
    for (let rect of rects) {
        if (rect.endy < y || rect.starty > y) {
            continue;
        }
        xStarts.push(rect.startx);
        xEnds.push(rect.endx);
    }
}
let allXs = [...xStarts, ...xEnds];

#Then, for each x coordinate, we determine whether we are inside a rectangle by counting whether we have passed more rectangle starts than ends:

for (let k = 0; k < allXs.length; k++) {
    let insideCount = xStarts.filter(x => x <= allXs[k]).length
                    - xEnds.filter(x => x <= allXs[k]).length;
    
    #Creating an output rectangle whenever the count reaches 0:
    
    if (insideCount === 0 && inside) {
        output.push({
            starty: yCoordinates[i],
            endy: yCoordinates[i + 1],
            startx: start,
            endx: allXs[k]
        });
    }
    if (insideCount > 0 && !inside) {
        start = allXs[k];
    }
    inside = insideCount > 0;
}

This could be optimised, but it demonstrates the idea.