Issue with overlapping horizontal rectangles

Question

So I'm trying to solve a graphics problem. Basically there's a container, let's say its 600px wide. If there is only one rectangle in that container(with no overlapping rectangles) it takes up the width of it. However, the issue is when these rectangles overlap, the width has to shrink accordingly. We are given the top left and bottom left y-coordinates of this rectangle. (such as it starts 60px down and ends 120 px down the big container)

So I wrote an overlap algorithm that checks if an overlap exists and counts the number of rectangles that the rectangle overlaps with (including itself). Then I divide the container width by the maximum number of elements overlapped to get the width of the smaller rectangles.

    for (i = 0; i < events.length; i++) {
        var event = events[i];
        var numCollisions = 0;  
        for (j = 0; j < events.length; j++) {
            var eventCmp = events[j];
            if (event.start <= eventCmp.start && event.end > eventCmp.start ||
                event.start < eventCmp.end && event.end >= eventCmp.end) {
            numCollisions++;   
        }
    }

However, I've noticed a huge problem with this. If you look at this picture below the rightmost rectangle has two overlapping rectangles. By my algorithm you would get the container width/3 (including the rectangle itself) which is incorrect. The actual answer is the container width/2.

So the issue is (after this long winded explanation) that I need to find if two rectangles are horizontally aligned. I've been busting my head on this for hours. Any hints on how I can do this?

Answer 1

Well, the easiest answer is divide by 2 IF you have a collision (not caring how many collisions you actually have). If you need something more sophisticated, can you show a more sophisticated case?

Answer 2

a less than optimal, but easy to implement algo would be:

foreach y coord in the main container
    rects = find all rects which contain this y coord
    foreach rects as rect
       rect.maxHorizNeighbors = max(rects.length, rect.maxHorizNeighbors)

theres still some other issues you'll need to address, but this should get you started on your homework assignment. in particular, theres a case where you could possibly end up with horizontal gaps. ill let you find that on your own.