圓圈堆碼算法

Question

在一個遊戲中，我需要堆疊一堆不同半徑的圓圈，以避免堆疊重疊。圓圈堆疊，以便重疊的圓形成一個堆疊，最大半徑的圓在頂部。圓圈隨機放置在連續的2D平面上。可以有相同半徑的圓。

我使用C++。圓圈存儲在向量中。乘飛機我只是說圓圈有（雙）x和y座標。堆棧基本上是使用最頂層的位置和半徑的圓圈矢量（它應該是最大的）。通過「沒有堆疊重疊」我的意思是堆疊後的堆疊不應該重疊。

我所做的：

1. 排序半徑
2. 對於第一個圓（最大的一個）的圈子中的所有重疊圓添加到它的堆棧，從圓列表中刪除它們。
3. 重複，直到圓圈列表爲空。
4. 排序所有堆棧以獲得最大的堆棧。

爲什麼它不工作（總是）。有時3個相等的半徑圓圈重疊，以便兩個圓圈共用一個圓圈（但它們本身並不重疊）。其中一個圈子獲得共享圈，然後偶然選擇該圈作爲導致兩個重疊棧的最高圈。

我給了它很多想法，但我能想到的所有方法似乎都需要非常複雜的循環和ifs來手動檢查哪些圈子是共享的以及如何移動它們，或者通過隨機重新排列棧。

是否有一些通用的方法來解決這樣的問題？如果堆棧是「最優」的，那麼所有堆棧將它們的「能量」最小化（如拉入節點的距離最小），這也是很酷的。

在情況1中，選擇了中心圓（假設所有三個大圓都具有相同的半徑），因爲它最小化堆的數量。在情況2中，最大的圓圈正確地位於堆棧頂部。在情況3中，一切都按預期進行。在情況4中，小圓圈錯誤地位於堆棧頂部。另外，如果其他兩個圓圈的大小相同，則應該只有一個堆疊，如情況1所示。在情況5中，錯誤的圓圈位於頂部，導致堆疊重疊。

謝謝！

的工作蠻力版本：

std::vector<std::vector<Symbol>::iterator >symPos; std::vector<int> cons;std::vector<Symbol> selVec; Symbol start; SymbolStack stack; 
    while(symbols.size()){ 
     std::sort(symbols.begin(),symbols.end(),std::greater<Symbol>()); 
     start = symbols.front(); 
     for(int i = 0;i<symbols.size();i++){ 
      if(symbols[i].getRadius() == start.getRadius()){ 
       selVec.push_back(symbols[i]); cons.push_back(0); symPos.push_back(symbols.begin()+i); 
      } 
     } 
     for(int i = 0;i<selVec.size();i++){ 
      for(int j = i+1;j<selVec.size();j++){ 
       if((selVec[i].getPos()-selVec[j].getPos()).len() < 2*(selVec[i].getRadius()+selVec[j].getRadius())){ 
        cons[i]++;cons[j]++; 
       } 
      } 
     } 
     int maxCons = 0; int selected; 
     for(int i = 0;i<cons.size();i++){ 
      if(cons[i] >= maxCons){selected = i;maxCons = cons[i];} 
     } 
     start = selVec[selected]; 
     stack.addSymbol(start); symbols.erase(symPos[selected]); 
     for(auto it = symbols.begin();it!=symbols.end();){ 
      if((it->getPos()-start.getPos()).len() < 1.5*(it->getRadius()+start.getRadius())){ 
       stack.addSymbol(*it); 
       it = symbols.erase(it); 
      }else{ 
       it++; 
      } 
     } 
     stacks.push_back(stack); 
     stack.clear(); 
     selVec.clear(); 
     symPos.clear(); 
     cons.clear(); 
    } 

其中symbol是一個圓的對象。堆棧是一個std :: vector。根本沒有效率，但它的工作原理。我會嘗試像Nico建議的那樣優化它。符號對象包含一個vector2位置（getPos（））和一個半徑（getRadius（））。 len（）方法獲取vector2的長度。

Answer 1

我會將算法分爲兩部分 - 代表性檢測和堆棧構建，其中堆棧構建基本上將每個圓與代表相關聯，形成一個堆棧。

最後一部分非常簡單。迭代每個圓並將其與代表能量最少的代表（可能是最接近的一個）相關聯。使用加速度數據結構（如網格或kd樹）來增強此類查詢。

第一部分更難。其實，它看起來很難，雖然我無法證明它。但是讓我們從頭開始。

按大小降序對圓進行排序是一個好主意。如果第一個圓（最大半徑）不與具有相同半徑的圓重疊，那麼顯然它應該是一個代表。在這種情況下，從列表中刪除（或標記）每個重疊的圓。在另一種情況下，您必須決定選擇哪個重疊的圓（等半徑）。

在您的代碼中，您使用簡單的啓發式（重疊圓圈的數量）來決定選擇哪個圓圈。根據您的數據和用例，這可能是一個有效的選項。總體而言，這可能並不總是會產生最佳解決方案（因爲決策可能會顯着改變後續決策）。

另一種選擇是使用反向跟蹤。嘗試一個決定，看看它如何發展（最終評估代表人數）。然後，當回去時，也嘗試其他決定。一旦代表人數超過目前所見的最低人數，您可以立即離開決策部門。不幸的是，這可能會導致最壞情況下的指數運行時間。但是，只有在重疊相同大小的圓圈的情況下才需要做出決定。如果這種情況不經常發生，反向跟蹤可能是一個不錯的選擇，它可以保證您獲得全球最佳的解決方案。

請記住，您的列表已排序。搜索特定半徑的圓時，不必搜索整個列表。在你的代碼中有幾個地方可以通過這個事實來改進。並且，如前所述，使用加速結構來更快地評估重疊查詢。