Найти группу пересекающихся прямоугольников

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 вершины. Таким образом, я могу использовать алгоритм развертки. Но я не могу найти образец, который можно применить к моей проблеме.

Как получить пересекающиеся группы?

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 является промежуточным решением. Процесс для данного набора прямоугольников (или для любого набора прямоугольников) выглядят следующим образом:

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]. Пустой список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]]

3. Удалить пустые списки из списка. Результатом является группа пересекающихся прямых.

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

Надеется, что это помогает. Я не говорю на C++ свободно. Однако, если это помогает, я могу поделиться с вами директором Lingo, который я написал. Причина, по которой я не опубликовал код Lingo, заключается в том, что редко кто-либо работает в Director больше.