Algorithm suggestion
I have a programming problem: Here's a simplification that isolates the actual problem:
Imagine a grid and a set of rectangles. Each rectangle has a position and width/height. One rectangle may enclose another, but they never overlap. Enclosed rectangles are considered on top of the enclosing ones.
Each rectangle has a unique identifier (a pointer to another object in fact)
The goal: For each horizontal row, I want to compute spans where the rectangle identifier is the same.
A simple solution for this would be to allocate the entire grid, then sort the rectangles by top-left x and y (or vice versa) and then iterate over each rectangle, filling each cell with the identifier. The sorting ensures that enclosed cells are drawn after the enclosing ones.
The issue is that I want to do this row-by-row. I.e. I do not want to allocate the entire grid in one go.
Anyone have a good solution to this?
Algorithm suggestion
You can use a broom: have a data structure that represents what's going on in a single row that can be updated. Whenever you move to a new row, update it to take into account rectangles that appear or disappear in that row (which you can find by having a list of rectangle starts and ends and sorting that instead of just the list of rectangles).
The candidate for such a structure is a sorted dictionary that maps left ends of intervals to their IDs and right ends. You can simply amend it (by adding/removing the appropriate entry) and you can construct the spans by iterating over it while keeping aside a stack of still-open rectangles.
Algorithm suggestion
If you need to accept a stream of rectangles as input (i.e. can't keep all of them in memory), then you can keep a priority queue for the "rectangle end" events, where you'd insert an event when you encounter a beginning of a rectangle.
