CODEWITHSUNDEEP
algorithmgeometryshapesoverlap
Garret Fick
Garret Fick

Reputation: 83

How to group shapes into sets of sets of overlapping shapes

Please note I am interested in the most efficient way to solve the problem, and not looking for a recommendation to use a particular library.

I have a large number (~200,000) of 2D shapes (rectangles, polygons, circles, etc) that I want to sort into overlapping groups. For example, in the picture, the green and orange would be marked as group 1 and the black, red, and blue would be marked as group 2.

Example

Let's say I will be given a list<Shape>. A slow solution would be:

(I haven't run this code - just an example algorithm)

// Everything initialized with groupid = 0
int groupid = 1;

for (int i = 0; i < shapes.size(); ++i)
{
    if (shapes[i].groupid)
    {
        // The shape hasn't been assigned a group yet
        // so assign it now
        shapes[i].groupid = groupid;
        ++groupid;
    }

    // As we compare shapes, we may find that a shape overlaps with something
    // that was already assigned a group. This keeps track of groups that
    // should be merged.
    set<int> mergingGroups = set<int>();

    // Compare to all other shapes
    for (int j = i + 1; j < shapes.size(); ++j)
    {
        // If this is one of the groups that we are merging, then
        // we don't need to check overlap, just merge them
        if (shapes[j].groupid && mergingGroups.contains(shapes[j].groupid))
        {
            shapes[j].groupid = shapes[i].groupid;
        }
        // Otherwise, if they overlap, then mark them as the same group
        else if (shapes[i].overlaps(shapes[j]))
        {
            if (shapes[j].groupid >= 0)
            {
                // Already have a group assigned
                mergingGroups.insert(shapes[j].groupid;
            }
            // Mark them as part of the same group
            shapes[j].groupid = shapes[i].groupid
        }
    }
}

A faster solution would be to put the objects into a spacial tree to reduce the number of j object overlap comparisons (the inner loop), but I would still have to iterate over the rest to merge groups.

Is there anything faster?

Thanks!

Upvotes: 0

Views: 321

Answers (2)

Garret Fick
Garret Fick

Reputation: 83

Hopefully this helps someone - this is what I actually implemented (in pseudocode).

tree = new spatial tree
for each shape in shapes
    set shape not in group 
    add shape to tree 

for each shape in shapes
    if shape in any group 
        skip shape

    cur_group = new group
    set shape in cur_group 

    regions = new stack
    insert bounds(shape) into regions

    while regions has items
        cur_bounds = pop(regions)

        for test_shape in find(tree, cur_bounds)
            if test_shape has group
                skip test_shape

            if overlaps(any in cur_group, test_shape)
                insert bounds(tester) into regions
                set test_shape group = cur_group

Upvotes: 1

MBo
MBo

Reputation: 80197

If you effectively find all pairwise intersections with a spatial tree, you can use union-find algorithm to group objects

Upvotes: 0

Related Questions