從連續的固定尺寸矩形制作更寬的矩形？

Question

我正在爲我的遊戲添加瓷磚碰撞。

我所做的是，我穿過每個物體，並獲得周圍的邊緣瓷磚。

我返回一個Vec2矢量，它對應於每個周圍邊緣圖塊的左上角位置。

那些得到了一套Vec2，所以只有獨特的留下來。

從那裏，可以構建固定大小的矩形。

不過，我需要的是連續的矩形在這個例子中被合併成1

所以，我們能將這些8米固定的矩形進3

最右邊的人會留下來原樣。

在x軸上的6將成爲1並在x軸和它下面的一個最左邊的將成爲1.

鑑於我有一組表示VEC2每一瓦片正方形的左上角位置和我知道正方形的寬度，我怎麼能用合併的固定正方形計算一個新的矩形（x，y，w，h）向量？

void TilePhysicsManager::update() 
     { 
      m_locationSet.clear(); //clear the unique locations 

      for (b2Body* b = m_b2world->GetBodyList(); b; b = b->GetNext()) 
      { 
       if(b->GetType() == b2_dynamicBody) 
       { 
        PhysicsObject* obj = (PhysicsObject*)b->GetUserData(); 
        const std::vector<Vec2>& edgeTiles = m_tileWorld->getSideTiles(*obj,1.5f); 

        //add in locations (duplicates will be rejected) 
        for(int i = 0; i < edgeTiles.size(); ++i) 
        { 
         m_locationSet.insert(edgeTiles[i]); 
        } 

       } 
      } 

      int objIndex = 0; //index of which dummy object we need 

      for(std::set<Vec2>::iterator it = m_locationSet.begin(); it != m_locationSet.end(); ++it) 
      { 
       //if our memory pool is not big enough, grow it 
       if(objIndex >= count()) 
       { 
        allocNewObject(); 
       } 

       m_objects[objIndex]->setLocation(*it); 
       objIndex++; 
      } 
} 

感謝

Answer 1

我相信最簡單也是最快捷的方法是通過「垂直連續帶」擴展或反之亦然進行「水平連續帶」擴展。

例如：

• 計算結合的矩形。垂直條的數量是高度除以固定矩形的高度。
• 創建一個數組的條元素。這存儲了每個條的最小和最大X座標。使用最小和最大座標來構建更寬的矩形。

• 然後，應用的水平條擴張。 （在我們的例子中，我們將在垂直帶擴展之後有4個矩形）。

• 創建帶元件的數目的陣列。這存儲了每個條的最小和最大Y座標。使用最小和最大座標來構建更寬的矩形。
• 檢查更寬的垂直條是否可以進一步擴大，如果是的話，擴大。

結論：

• 此算法假定有在每個條帶不連續性。

實施

• 以下是C＃中的優化的實施

  private List<Rectangle> Merge(Rectangle[] r) { 
      // Computing the bound 
      Rectangle bound = new Rectangle(r[0].X, r[0].Y, r[0].Width, r[0].Height); 
      for (int i = 1; i < r.Length; ++i) { 
       bound.X = Math.Min(bound.X, r[i].X); 
       bound.Y = Math.Min(bound.Y, r[i].Y); 
       bound.Width = Math.Max(bound.Right, r[i].Right) - bound.X; 
       bound.Height = Math.Max(bound.Bottom, r[i].Bottom) - bound.Y; 
      } 
  
      // Create number of rectangle will be created by vertical strip expansion 
      Rectangle[] m = new Rectangle[bound.Height/RECT_HEIGHT]; 
      for (int i = 0; i < m.Length; ++i) { 
       m[i] = new Rectangle(Int32.MaxValue, bound.Y + i * RECT_HEIGHT, 0, RECT_HEIGHT); 
      } 
  
      for (int i = 0; i < r.Length; ++i) { 
       int index = (r[i].Y - bound.Y)/RECT_HEIGHT; 
  
       if (m[index].Width <= 0) { 
        m[index].Width = r[i].Width; 
        m[index].X = r[i].X; 
       } else { 
        int right = m[index].Right; 
        m[index].X = Math.Min(m[index].X, r[i].X); 
        m[index].Width = Math.Max(right, r[i].Right) - m[index].X; 
       } 
      } 
  
      // Merge horozontally 
      for (int i = m.Length - 1; i > 0; --i) { 
       // can only merge when two rect has the same X and Width 
       if ((m[i].X == m[i - 1].X) && (m[i].Width == m[i - 1].Width)) { 
        m[i - 1].Height += m[i].Height; // expanse the rectangle 
        m[i].Width = 0;    // remove one rectangle 
       } 
      } 
  
      // Remove all the empty rectangle 
      List<Rectangle> result = new List<Rectangle>(); 
      for (int i = m.Length - 1; i >= 0; --i) { 
       if (m[i].Width > 0) 
        result.Add(m[i]); 
      } 
  
      return result; 
  } 
  

以下是通過以下實現的結果產生。左邊是最初的矩形，右邊是結果。

• 如果可以合併兩個垂直框，請創建一個更大的矩形。

• 優先於水平框

• 有一個在一個垂直條2個箱之間中止空間的垂直框。結果並不是我們所期望的。

Answer 2

我認爲這個問題語句有一點不含糊來解決。在給出的示例中，有多種可能的方式將給定的拼貼組分成最大的，不重疊的較大矩形。具體來說，可以按照您的建議將左上角的貼磚與行的其餘部分合並，也可以將其與其下面的合併。

就算法而言，我首先想到的是從集合中逐個獲取切片並通過它們的鄰居來擴展它們。當展開一個多個圖塊的矩形時，只需檢查該邊上的所有圖塊中是否有一個鄰居（剩餘的）即可。一旦你發現這個矩形不能在任何方向上展開，你就完成了，並且可以移動到下一個圖塊。

這種方法對我來說似乎是O（n^2），可能可以改進，但在實踐中可能很容易成爲一個非問題，具體取決於規模以及您需要多久評估一次（使用靜態水平幾何，不經常我希望）。

需要注意的一個方法就是不要在迭代時從容器中移除元素。糟糕的迭代器juju。只需複製一份。