Efficiently project 2D plane onto 1D line

Question

I have a array of [width, height, x, y] vectors, like so: [[width_1, height_1, x_1, y_1],...,[width_n, height_n, x_n, y_n]] representing a 2D plane of blocks. This vector is potentially long (n > 10k).

An example:

must be projected like:

The problem is however that the blocks are not neatly stacked, but can be in any shape and position

The criterion for which block should be project doesn't really matter. In the example I took the first (on the x-axis) largest; which seems reasonable.

What is important is that a list (vector) is maintained of which other blocks were occluded by the projected block. The blocks bear metadata which is important, so I should be able to answer the question "to what line segment was this block projected?"

So concretely how can a 2D plane be efficiently projected onto a line, in a sense "cast a shadow", in a way that maintains a method of seeing what blocks partake in a line segment (shadow)?

Edit: while the problem is rather generic, the concrete problem is that I have a document that has multiple columns and floating images for which I would like to generate a "minimap" which indicates where to find certain annotations (colors)

Answer 1

Assuming that the rectangles are always aligned with the axes, as in your example, I would use a sweep line approach:

1. Sort the rectangle tops/bottoms according to their y value. For every element, keep a reference to the full rectangle data.

2. Scan the list in increasing y order, maintaining a set S of rectangles representing the rectangles that contain the current y value. For every top of a rectangle r, add r to S. Similarly, for every bottom of r, remove r from S. Every time you do it, a segment is being closed and a new one is started. If you inspect S at this point, you have all the rectangles that participate in the segment, so this is the place to apply a policy for choosing the segment color.

If you need to know later what segments a rectangle belongs to, you can build a mapping between rectangles and segments lists, and update it during the scan.