Find a group of intersecting rectangles

Question

I have 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 a group of rectangles having at least one intersection with the transitivity property. those. if r1 intersect r2 and r2 intersect r3, r1, r2, r3 are part of the same group.

In this example, the group will be

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

The group order and the order of the elements within the group are not important.

How can I calculate these groups? If necessary, I can change the data structure.

For example, I can change std::vectorto std::setand arrange the rectangles with the left X coordinate of the vertex. That way I can use the sweep algorithm. But I cannot find a pattern that can be applied to my problem.

How to get overlapping groups?

Answer 1

, .

:

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;

, , 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;

... ...

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();
    }
};

... ...

 // 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();

Answer 2

, OP . ( ) :

• , . , 6 6 . 1 :

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

• , . . 1 1 2. , , list1 list2, [1,2,4]. 1, . :

  [[], [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]]

• . .

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

, . ++ . , , Lingo, . , Lingo, , - Director .