Sorting/clustering mechanism for determining bounding box intersection

Question

I want to be more efficient in determining intersections between a group of 2D shapes (primitives like lines, arcs). I thought to do this by first checking overlap between their bounding boxes. Is there a means to sort the bounding boxes of all shapes such that I can conlude following:

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 ?

Maybe some clustering is needed? Any ideas?

Answer 1

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