交差による多角形の任意の数のグループ化 - C＃

Question

私は、それぞれが物理的オブジェクトを表すポリゴンの複数のリストを持っています。たとえば、

List<CurveLoop> Aは、穴がある矩形を表すことができます。このリスト内の1つの曲線は長方形の輪郭であり、別の曲線は穴である。

リストのリストを返すメソッドが必要です。各リストには、交差するすべてのオブジェクトが含まれています。

私はすでに2つのオブジェクトが交差するかどうかを返します方法があります：二つのリストタッチ内の任意の二つの曲線があれば

bool _CurveLoopsIntersect(List<CurveLoop> curveLoopsA, List<CurveLoop> curveLoopsB) {...}

はtrueを返しますが。

以下は私がこれまでに持っていたコードですが、それは私に1回のパスを与えます。私はオブジェクトAとBが交差し、BとCが交差すると、set {A、B、C}を形成するように、複数のパスが必要だと思います。しかし、任意の数のパスが必要で、時にはオブジェクトが全く交差しないか、{A、B、C}や{D、E}や{F}などの異なるセットの一部になることがあります。これは、このpsuedu

set = a,b,c, ... 

While(set not empty) { 
Create newSet 
Add set.first to new list 
Remove set.first from set // this line isnt necessary if a curve doesnt intersect with self 


For (i = 0 , i < newset.length , i++) 
{   
     newSet.add(set.FindAll(x => _CurveLoopsIntersect(x, newSet[i])); 
     set.removeRange(newSet); // this line may have error that the first element doesnt exist in set 
} 
Add newSet to set of sets 

}

Answer 1

おかげで、あなたは正しい方向に私を置きます。あなたが正しいと思ったのは、セットが適切なアプローチだったことです。私は再帰関数（あなたのwhileループに似ている）と組み合わせてセットを使用しました。

私が書いたコードは以下の通りです：

static List<Polygon> _RecursiveMergePolygons(List<Polygon> polygons, View view) 
    { 
     HashSet<Polygon> initialSet = new HashSet<Polygon>(polygons); 

     HashSet<Polygon> finalSet = new HashSet<Polygon>(polygons); 

     foreach (var polygon in initialSet) 
     { 
      // Should always return at least 1 instance 
      var polys = polygons.FindAll(x => _PolygonsIntersect(x, polygon)); 

      // if it's greater than 1, then merge them and restart the recursion, otherwise continue 
      if (polys.Count > 1) 
      { 
       foreach (var poly in polys) 
       { 
        finalSet.Remove(poly); 
       } 
       var mergedPolygon = new Polygon(polys, view); 
       finalSet.Add(mergedPolygon); 
       break; 
      } 
     } 
     if (finalSet.Count == initialSet.Count) 
     { 
      return finalSet.ToList(); 
     } 
     return _RecursiveMergePolygons(finalSet.ToList(), view); 
    } 

Answer 2

のようないくつかのコードを使用して実装することができ

public List<CurveLoop> _MergeCurveLoops(List<List<CurveLoop>> elementCurveLoops, View view) 
{ 
    // ... 
    // Preprocessing 

    var listOfLists = new List<List<CurveLoop>>(); 
    foreach (var elementCurveLoop in elementCurveLoops) 
    { 
     var newList = elementCurveLoops.FindAll(x => _CurveLoopsIntersect(x, elementCurveLoop)); 
     listOfLists.Add(newList); 
    } 
} 


private bool _CurveLoopsIntersect(List<CurveLoop> curveLoopsA, List<CurveLoop> curveLoopsB) 
{ 
    foreach (var curveLoopA in curveLoopsA) 
    { 
     foreach (var curveA in curveLoopA) 
     { 
      foreach (var curveLoopB in curveLoopsB) 
      { 
       foreach (var curveB in curveLoopB) 
        { 
        var result = curveA.Intersect(curveB); 

        if (result == SetComparisonResult.Overlap || 
         result == SetComparisonResult.Subset || 
         result == SetComparisonResult.Superset || 
         result == SetComparisonResult.Equal) 
        { 
         return true; 
        } 
       } 
      } 
     } 
    } 
    return false; 
}