Find group of intersecting rectangles

Question

I've a list of rectangles (they cannot rotate):

struct Rectangle {
  double centerX;
  double centerY;
  double width;
  double height;

  Rectangle(double x, double y, double w, double h):centerx(x),centery(y),width(w),height(h){}
};

std::vector<Rectangle> rectangles;
rectangles.push_back(Rectangle(0  ,  0  , 1  , 1  );
rectangles.push_back(Rectangle(0.5,  0.5, 1  , 1  );
rectangles.push_back(Rectangle(3  ,  2  , 0.5, 0.6);
rectangles.push_back(Rectangle(0.2,  0.5, 0.5, 0.6);
rectangles.push_back(Rectangle(2  , -0.3, 0.4, 0.4);
rectangles.push_back(Rectangle(0.2, -0.4, 0.3, 0.4);

I want to calculate group of rectangles that have at least one intersection, with transitivity property. i.e. if r1 intersect r2 and r2 intersect r3, r1, r2, r3 are part of the same group.

In this sample, group will be

{{3}, {4, 1, 2}, {5, 6}}

Group order and element order inside group is not important.

How can I calculate these groups? I can change data structure if necessary.

For example, I can change std::vector to std::set and order rectangles by left vertex X coordinate. In this way I can use a sweep line algorithm. But I am not be able to find any sample that can be applied to my problem.

How can I obtain intersecting groups?

Answer 1

I have been working on a problem where the OP's question is an intermediate solution. The process for the given set of rectangles (or for any set of rectangles) is as follows:

1. Make a list of rectangles that intersect with each rectangle. So, for the 6 rectangles in the sample, we will have 6 lists. The result of step 1 is as shown below:

   [[1,2], [2,1,4], [4,2], [3], [5,6], [6,5]]

2. Next, we iterate through this list of lists and merge the lists if either one of the rectangles exist in the next list. For eg. rectangle 1 of list 1 exists in list 2. Therefore, the merged list formed out of list1 and list2 would be [1,2,4]. Empty out list1 so that we can't use it again in the next iteration. The result of each iteration is shown below:

   [[], [2,1,4], [4,2], [3], [5,6], [6,5]] [[], [], [4,2,1], [3], [5,6], [6,5]] [[], [], [4,2,1], [3], [5,6], [6,5]] [[], [], [4,2,1], [3], [5,6], [6,5]] [[], [], [4,2,1], [3], [], [6,5]]

3. Delete the empty lists from the list. The result is a group of intersecting rects.

   [[4,2,1], [3], [6,5]]

Hope this helps. I don't speak C++ fluently. However, if it helps, I can share with you the Director Lingo code that I have written. The reason I have not posted the Lingo code is because rarely anyone works in Director anymore.

Answer 2

I think a vector of sets would do the job.

Like this:

std::vector< std::set< int > > groups;

// loop over rectangles
for( int r1 = 0; r1 < rectangles.size(); r1++ )
{
    // check if rectngle already in group
    auto g_it = groups.end();
    for( auto group = groups.begin();
        group != groups.end(); group++ )
    {
        auto group_r1_it = group->find( r1 );
        if( group_r1_it != group->end() )
        {
            g_it = group;
            break;
        }
    }
    if( g_it == groups.end() )
    {
        // not already in group, so create new group
        set<int> s;
        s.insert( r1 );
        groups.push_back( s );
        g_it = groups.end()-1;
    }

    // loop over remaining rectangles
    for( int r2 = r1+1; r2 < rectangles.size(); r2++ )
    {
        // check for intersection
        if( rectangles[r1].Intersect( rectangles[r2] ))
        {
            //report intersection
            cout << r1+1 <<" " <<r2+1 << endl;

            // add to group
            g_it->insert( r2 );

        }
    }

}
    // Display results
    for ( auto group : groups )
    {
        cout << "{ ";
        for( auto r : group )
        {
            cout << r+1 << " ";
        }
        cout << "} ";
    }
    cout << endl;

In order to write cleaner code, I would suggest upgrading your rectangle so it plays nicely with the STL ...

class Rectangle
{
public:
    double centerX;
    double centerY;
    double width;
    double height;
    int myID;
    static int lastID;

    Rectangle(double x, double y, double w, double h)
        :centerX(x),centerY(y),width(w),height(h),
         myID( ++lastID )
    {        }

    bool Intersect( const Rectangle& other ) const
    {
        ...
    }
    bool operator ==(const Rectangle& other ) const
    {
        return myID == other.myID;
    }
    bool operator <(const Rectangle& other ) const
    {
        return myID < other.myID;
    }
};

int Rectangle::lastID = 0;

... adding a class to handle the vector of sets ...

class RectangleGroups
{
public:
    typedef std::set< Rectangle > group_t;
    typedef std::vector< group_t >::iterator iter;

    iter begin()
    {
        return groups.begin();
    }
    iter end()
    {
        return groups.end();
    }
    /**  Build the groups of intersecting trinagles

    @param[in] rectangles  vector of rectangles
    @param[in] intersections vector of pairs of intersecting rectangles
    */
    void Make(
        std::vector< Rectangle > rectangles,
        std::vector< std::pair< Rectangle&, Rectangle& > >& intesections )
    {
        // loop over intersecting triangles
        for( auto rp : intesections )
        {
            iter g_it = Find( rp.first );
            if( g_it != groups.end() )
            {
                g_it->insert( rp.second );
                continue;
            }
            g_it = Find( rp.second );
            if( g_it != groups.end() )
            {
                g_it->insert( rp.first );
                continue;
            }
            // neither rectangle is already in group, so add new group
            g_it = Add( rp.first );
            g_it->insert( rp.second );

        }
        // Add orphans
        for(  auto& r : rectangles )
        {
            if ( Find( r ) == groups.end() )
            {
                Add( r );
            }
        }
    }
    /// Display rectangle IDs in groups marked off with curly braces
    void Display()
    {
        for ( auto group : groups )
        {
            cout << "{ ";
            for( auto r : group )
            {
                cout << r.myID << " ";
            }
            cout << "} ";
        }
        cout << endl;
    }

private:
        std::vector< group_t > groups;

            ///  Add new group containing a copy of a rectangle, return iterator pointing to new group
    iter Add( const Rectangle& r )
    {
        group_t s;
        s.insert( r );
        groups.push_back( s );
        return groups.end()-1;

    }
    ///  Find group containing rectangle, return iterator pointing to found group or to end
    iter Find( const Rectangle& r )
    {
        for( iter it = groups.begin(); it != groups.end(); it++  )
        {
            auto group_it = it->find( r );
            if( group_it != it->end() )
            {
                return it;
            }
        }
        return groups.end();
    }
};

... so that we can write ...

 // vector of intesections
 // you can build this using various algorithms, even a sweepline
// here I will use a simple pair of nested for loops
   std::vector< std::pair< Rectangle&, Rectangle& > > intersections;
// loop over rectangles
    for( auto& r1 : rectangles )
    {
        // loop over remaining rectangles
        for( auto& r2 : rectangles )
        {
            if( r2 < r1 || r1 == r2 )
                continue;

            // check for intersection
            if( r1.Intersect( r2 ))
            {
                intersections.push_back( std::pair<Rectangle&, Rectangle& >( r1, r2 ) );
            }
        }
    }

    // Construct a vector of rectangle groups
    // The groups will contain interesecting rectangles.
    RectangleGroups groups;

    groups.Make(
            rectangles,
            intersections );

// Display results
groups.Display();