確定幾何形狀的梯度所需的算法

Question

我一直在努力開發一種算法，根據一個形狀是否完全封閉在另一個形狀的外圍，對封閉幾何圖形的集合進行排序。當完全分析時，我最終應該定義一個定義層次結構的樹結構。

我可以照顧實際的比較，即一個形狀是否完全在另一個形狀的外圍。儘管對無組織輸入進行排序，但我很困難。我懷疑這個解決方案涉及到二叉樹結構和遞歸代碼，這是我從未使用過的。

在生成排序的層次數據之前，幾何數據已經過清理，因此像開放路徑，重疊，部分重疊和自相交等問題不應該成爲問題。

下面是我一直在處理的一組測試數字，這可能有助於說明我的問題。

作爲一個人，我可以看到黃色形狀不是藍色之一內，也不是內黃色是藍色的。他們都在綠色的形狀內，這是在紅色內......等等。 （對不住那些誰是色盲）

得到的樹將如下所示：

我工作在C＃，但不弄清楚它的相關的問題。

謝謝

編輯1

更簡潔的問題可能是「我如何生成此樹正確的順序？」 （給定的數據沒有特定的順序）。這只是你的基本教科書「二叉搜索樹插入」，我可能過度思考？

EDIT 2

試圖Norlesh的僞代碼轉換成C＃，並將其綁到我現有的代碼，我結束了以下內容：

 // Return list of shapes contained within container contour but no other 
    private List<NPContour> DirectlyContained(NPContour container, List<NPContour> contours) 
    { 
     List<NPContour> result = new List<NPContour>(); 

     foreach (NPContour contour in contours) 
     { 
      if (container.Contains(contour)) 
      { 
       foreach (NPContour other in contours) 
       { 
        if (other.Contains(contour)) 
         break; 
        result.Add(contour); 
       } 
      } 
     } 

     return result; 
    } 

    // Recursively build tree structure with each node being a list of its children 
    private void BuildTree(NPContourTreeNode2 parent, List<NPContour> contours) 
    { 
     List<NPContour> children = DirectlyContained(parent.Contour, contours); 

     if (children.Count > 0) 
     { 
      // TODO: There's probably a faster or more elegant way to do this but this is clear and good enough for now 
      foreach (NPContour child in children) 
      { 
       contours.Remove(child); 
       parent.Children.Add(new NPContourTreeNode2(child)); 
      } 

      foreach (NPContourTreeNode2 child in parent.Children) 
      { 
       BuildTree(child, contours); 
      } 
     } 
    } 

...和調用代碼...

  List<NPContour> contours = new List<NPContour>(); 
     List<NPContour> _topLevelContours = new List<NPContour>(); 
     bool contained = false; 

     foreach (NPChain chain in _chains) 
     { 
      if (chain.Closed) 
      { 
       NPContour newContour = new NPContour(chain); 
       contours.Add(newContour); 
      } 
     } 

     //foreach (NPContour contour in contours) 
     for (int i = 0; i < contours.Count(); i++) 
     { 
      contained = false; 
      foreach (NPContour container in contours) 
      { 
       if (container.Contains(contours[i])) 
       { 
        contained = true; 
        continue; 
       } 
      } 
      if (contained == false) 
      { 
       _topLevelContours.Add(contours[i]); 
       contours.Remove(contours[i]); 
      } 
     } 

     foreach (NPContour topLevelContour in _topLevelContours) 
     { 
      NPContourTreeNode2 topLevelNode = new NPContourTreeNode2(topLevelContour); 
      BuildTree(topLevelNode, contours); 
     } 

我在想，我一定是誤解了翻譯中的某些內容，因爲它不工作。我會繼續阻止它，但認爲我會在這裏發佈代碼，希望有人可以幫助指出我的錯誤。

請注意，在僞代碼中buildTree沒有返回任何內容，但在調用代碼中，返回值被附加到...以及我有點困惑，它應該是什麼位置無論如何去那裏。我得到了這個例子的總體思路，但我認爲可能有一些重要的觀點丟在了我的頭上。

到目前爲止，在我的簡短調試中，我似乎從下面的示例（而應該只有一個）和多個不同的子項（比如55？）中獲得多個頂級形狀。我希望以後能夠提供更多的調試信息。

Answer 1

下面是一些僞代碼，應該達到什麼樣的你要做的：

// return true if shape is enclosed completely inside container function contains(container, shape); // return list of shapes contained within container shape but no other. function directlyContained(container, shapes) { result = [] for (shape in shapes) { if (contains(container, shape)) { // check its not further down hierarchy for (other in shapes) { if (contains(other, shape)) { break // not the top level container } result.append(shape) } } } return result; } // recursively build tree structure with each node being a list of its children // - removes members of shapes list as they are claimed. function buildTree(parent, shapes) { children = directlyContained(parent, shapes) if (children.length > 0) { shapes.remove(children); parent.append(children); for (child in children) { // recall on each child buildTree(child, shapes); } } } function findTopLevel(shapes) { result = [] // find the one or more top level shapes that are not contained for shape in shapes { contained = false; for (container in shapes) { if (contains(container, shape)) { contained = true; continue; } } if (contained = false) { scene.append(shape); shapes.remove(shape); } } return result; } shapes = <...>; // list initialized with the unsorted shapes scene = findTopLevel(shapes); shapes.remove(scene); for (top in scene) { buildTree(top, shapes); }