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?

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?

• algorithm
• geometry
• 2d

• This is exactly what R-Trees (and their variants) are for! You insert items with their bounding boxes and querying returns items whose bounds intersect the given box. – micycle Commented Jan 22 at 11:14
• @micycle Post an answer describing how to use R-Trees – ravenspoint Commented Jan 22 at 17:38
• @ravenspoint R-Tree libraries are readily accessible in most languages. Once you have one they're trivial to interact with, so it's just a matter of letting OP know about them as a solution for a spatial index for bounding boxes. – micycle Commented Jan 22 at 17:51
• Then it will be easy for you to post a good answer. – ravenspoint Commented Jan 22 at 18:32

3 Answers 3

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/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./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/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.)