刪除重複對的列表<object>

Question

問題

我使用顯示在3D WPF庫簡單線條的幾何形狀。它的一個例子可以看出，在未來的畫面：

在這裏面你可以看到一組三角形和四邊形的。我繪製這個的方式是我提供了一個List<Point3D>，其中我放置了代表每個片段的點對。

的問題是，有很多重複的邊緣，我想避免這種情況，因爲這類型的表示似乎是非常資源需求。產生

點列表遍歷包含N個頂點每個Element。它不知道特定的邊是否被共享。

<p0, p1, p1, p2, p2, p333, p333, p89, p89, p2, p2, p1 ...>

的想法是，除去重複對（注意順序可能是不一樣的）。在上面的例子中，刪除的對應該是最後一個（p2，p1），因爲它表示與第二對點（p1，p2）相同的邊緣。可能有一個，兩個或更多個重複的點對。

我需要儘可能快地做到這一點的操作，表現爲頂部PRIO這裏。

理念

雖然在列表中添加點我可以暫時保存了其中兩個，檢查列表已經包含了他們，但是這意味着我每增加一個點，並且沒有時間尋找到一個列表對我來說似乎是一個好主意（名單將包含數千個點5000-50000）。

我生成點列表的元素有幾個具有唯一ID的節點，所以我認爲可以通過創建Dictionary訂購Tuple<Point3D, Point3D>然後刪除重複項來以某種方式使用它。

我沒有嘗試過的最後一個想法，我不知道如何實現它，我想聽到的話，有可以做一些其他的事情。

Answer 1

使用HashSet<Tuple<Point3D, Point3D>>。每當你得到一個新的邊 - p1，p2時，檢查（p1，p2）在集合中的存在。同時檢查（p2，p1）的存在。如果兩者都不存在，則將（p1，p2）和（p2，p1）添加到該集合並使用該邊。

您可以通過製作自己的散列函數和相等函數來進一步加速這個過程，該函數會將（p1，p2）看作等於（p2，p1）。除非需要，否則不要這樣做，設置操作非常快，我懷疑這種改進會很大。

Answer 2

您可以使用HashSet來存儲所有的邊緣。檢查速度快，邊緣已經設定好了。但是您應該覆蓋GetHashCode和Equals。我舉了一個簡單的例子。

class MyLine 
{ 
    public MyPoint P1 { get; private set; } 
    public MyPoint P2 { get; private set; } 
    public MyLine(MyPoint p1, MyPoint p2) 
    { 
     P1 = p1; 
     P2 = p2; 
    } 
    protected bool Equals(MyLine other) 
    { 
     return (Equals(P1, other.P1) && Equals(P2, other.P2)) || Equals(P1, other.P2) && Equals(P2, other.P1); 
    } 
    public override bool Equals(object obj) 
    { 
     if (ReferenceEquals(null, obj)) return false; 
     if (ReferenceEquals(this, obj)) return true; 
     if (obj.GetType() != this.GetType()) return false; 
     return Equals((MyLine)obj); 
    } 
    public override int GetHashCode() 
    { 
     unchecked 
     { 
      return P1.GetHashCode() + P2.GetHashCode(); 
     } 
    } 
} 
class MyPoint 
{ 
    public string Id { get; private set; } 
    public MyPoint(string id) 
    { 
     Id = id; 
    } 
    protected bool Equals(MyPoint other) 
    { 
     return string.Equals(Id, other.Id); 
    } 
    public override bool Equals(object obj) 
    { 
     if (ReferenceEquals(null, obj)) return false; 
     if (ReferenceEquals(this, obj)) return true; 
     if (obj.GetType() != this.GetType()) return false; 
     return Equals((MyPoint)obj); 
    } 
    public override int GetHashCode() 
    { 
     return (Id != null ? Id.GetHashCode() : 0); 
    } 
} 

，那麼你應該能夠增加每行是這樣的：

與 GetHashCode和 Equals

public static void Main(string[] args) 
{ 
    HashSet<MyLine> lines = new HashSet<MyLine>(); 
    var line = new MyLine(new MyPoint("a"), new MyPoint("b")); 
    lines.Add(line); 
    line = new MyLine(new MyPoint("b"), new MyPoint("a")); 
    lines.Add(line); 
} 

您也可以存儲在List所有行，然後使用Distinct方法。

public static void Main(string[] args) 
{ 
    List<MyLine> lines = new List<MyLine>(); 
    var line = new MyLine(new MyPoint("a"), new MyPoint("b")); 
    lines.Add(line); 
    line = new MyLine(new MyPoint("b"), new MyPoint("a")); 
    lines.Add(line); 
    lines = lines.Distinct().ToList(); 
}