查找相交矩形组

Question

我有一个矩形列表（它们无法旋转）：

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

我希望能计算至少有一个交集的矩形组，且具有传递性。即如果r1和r2相交，r2和r3相交，则r1、r2、r3是同一组的一部分。

在这个样例中，该组包括：

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

组的顺序和组内元素的顺序并不重要。

我该如何计算这些组？如果需要，我可以更改数据结构。

例如，我可以将std::vector更改为std::set，并按左侧顶点X坐标对矩形进行排序。这样，我就可以使用扫描线算法。但是我找不到任何可应用于我的问题的示例。

我该如何获取相交的组？

- Jepessen

---

你可以轻松地将扫描与并查集结合起来。 - Danstahr

有没有任何参考书目或样例可以适用于我的具体问题？ - Jepessen

@Danstahr 感谢关键词，很好了解 :) 不相交集数据结构。 - legends2k

我不知道是否有任何需要，但应该是不必要的。并查集用于Kruskal算法中的最小生成树。如果您已经有了查找交点的算法（假设我们已经得到了相交矩形ID对），则只需在这些对上调用union()操作即可。该结构会处理其余部分并为您提供结果。 - Danstahr

好的，我会在网上检查这个。谢谢你的时间。 - Jepessen

Answer 1

我认为一个集合的向量可以胜任这个任务。

就像这样：

```c++ vector> vec; ```

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

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

- ravenspoint

---

谢谢，我会检查一下。它并没有使用扫描线算法，但目前我认为这不会是一个问题，因为我每次只需要处理大约20个矩形... - Jepessen

你所说的扫描线是什么？ - ravenspoint

@ravenspoint 这是一种避免对矩形进行嵌套循环的方法，但仅针对20个矩形而言，实现起来是浪费时间的。 - David Eisenstat

好的。我已经将交集计算与分组计算分开，这样你就可以使用你喜欢的方法来检测矩形集合中的交集。 - ravenspoint

Answer 2

我一直在解决一个问题，其中提问者的问题是一个中间解决方案。对于给定的矩形集（或任何矩形集），处理过程如下：

1. 列出与每个矩形相交的矩形列表。因此，对于示例中的6个矩形，我们将有6个列表。步骤1的结果如下所示：

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

2. 接下来，我们遍历这个列表的列表，并在任一矩形存在于下一个列表中时合并列表。例如，列表1的矩形1存在于列表2中。因此，由list1和list2形成的合并列表将是[1,2,4]。清空list1，以便我们不能在下一次迭代中再次使用它。每次迭代的结果如下所示：

   [[], [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. 从列表中删除空列表。结果是一组相交的矩形。

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

希望这可以帮到您。我不太擅长C++，但如果有帮助的话，我可以与您分享我编写的Director Lingo代码。我没有发布Lingo代码的原因是因为现在很少有人使用Director了。

- Manish