Sorting/clustering mechanism for determining bounding box intersection

Whenever box[i] is not intersecting with box[i+1], then this implies box[i] is also not intersecting with box[j] for j > i + 1 ?

That is impossible.

Your best bet would be to take a look at quad trees. https://github.com/JamesBremner/quadtree

Here is an example of how using a quadtree can be applied to a problem, in this case selecting the points that are inside a viewport:

Code to generate the quadtree.

void cViewport::gen()
{
    // viewport located at 250,150 dimensions 100 by 100
    viewport = new quad::cCell( cxy(250,150), 100 );

    // quadtree incuding entire display
    quadtree = new quad::cCell(cxy(300, 300), 600);

    //add randomly placed objects
    const int count = 2000;
    for (int k = 0; k < count; k++) {
        cxy obj(rand() % 500, rand() % 500);
        vObjects.push_back(obj);
        quadtree->insert(obj);
    }
}

Code to detect all the points that are visible in the viewport ( i.e. collide with the viewport ) using the quadtree

void cViewport::draw(wex::shapes &S)
{
    // Draw all the point in white
    S.color(0xFFFFFF);
    for (auto &r : vObjects)
    {
        S.rectangle(r, cxy(1,1));
    }

    // redraw points inside view port in black
    S.color(0x000000);
    for (auto &r : quadtree->find( *viewport ))
    {
        S.rectangle(*r, cxy(1,1));
    }

    // draw viewport in red
    S.color(0x0000FF);
    int dim = viewport->getDim();
    cxy tl( 
        viewport->getCenter().x - dim / 2,
        viewport->getCenter().y - dim / 2);
    S.rectangle(
        tl,
        cxy(dim,dim));
}

Code to generate the sweeplines

void cViewport::genSweep()
{
    vSweep = vObjects;
    std::sort(
        vSweep.begin(), vSweep.end(),
        [](const cxy &a, const cxy &b)
        {
            return a.y < b.y;
        });
}

Code to detect all the points that are visible in the viewport ( i.e. collide with the viewport ) using the sweep lines

std::vector<cxy *> cViewport::sweepFind()
{
    std::vector<cxy *> ret;

    cxy cent = viewport->getCenter();
    double dim = viewport->getDim() / 2;
    double xmin = cent.x - dim;
    double xmax = cent.x + dim;
    double ymin = cent.y - dim;
    double ymax = cent.y + dim;

    for( cxy& o : vSweep )
    {
        if( o.y < ymin )
            continue;
        if( o.y > ymax )
            break;
        if( o.x < xmin)
            continue;
        if( o.x > xmax )
            continue;
        ret.push_back(&o);
    }
    return ret;
}

Output

Complete code for the viewport application at https://codeberg.org/JamesBremner/viewport You can toggle between using the quadtree or the sweepline algorithm using the menu options.

For your particular problem, replace the 1 by 1 points with the bounding rectangles of your 2D shapes, loop over the rectangles, using quadtree->find( boundingRectangle ) to detect possible overlaps.

Performance

Because of the initial expense of building the quadtree, it only becomes worthwhile to use a quadtree if you have more than 100 objects. More than 1000 and the quadtree performance benefit becomes really significant. Performace details at https://github.com/JamesBremner/quadtree#performance-test

It's not exactly a sorting/clustering solution, but you can determine all the intersections in O((n log n) + output_size) time using a sweep-line algorithm.

First, separate each box into its top edge and bottom edge. Each edge will include its y coordinate and the interval in x that it spans.

Then, sort the edges by their y coordinates.

Now, iterate through the edges in y order, from top to bottom. If you have top and bottom edges with the same y coordinate, visit the bottom edges first. Now:

• When you see a top edge, insert its x-interval into an interval tree. At the same time you should check how many other intervals in the tree it overlaps with. There is a collision between the box that has the new top edge, and the boxes for all the overlapping intervals.
• When you see a bottom edge, remove the corresponding top edge from the interval tree.

When you're done, you will have found all the overlaps.

You can imagine the horizontal "sweep line" moving from top to bottom, and the interval tree always represents all the boxes it intersects. The overlaps that the line intersects can only change at top or bottom edges.

As suggested by 'micycle' the R-Tree is matching my needs. With one call I create the index:

index = Index(generator(shapes))

where generator yields the bboxes of supplied shapes. And then I can do the intersection queries like:

intersections = index.intersection(bbox)

Thats it. Its fast for my needs (maybe because of compiled implementation). Factor 4 compared to brute force. (I don't have too many shapes.)