usuwania duplikatów pary z listy <object>

Question

Emisji

ja wyświetlania geometrii za pomocą prostych linii w bibliotece 3D WPF. Przykładem tego może być postrzegane w następnym zdjęciu:

W nim można zobaczyć zbiór trójkątów i quadów. Sposób, w jaki to wykreślam, polega na tym, że zapewniam List<Point3D>, w której umieszczam pary punktów reprezentujących każdy segment.

Problem polega na tym, że istnieje wiele zduplikowanych krawędzi i chciałbym tego uniknąć, ponieważ ten rodzaj reprezentacji wydaje się być bardzo wymagającym zasobem.

Lista punktów jest generowana powtarzanie nad każdym Element, który zawiera N wierzchołków. Nie wiadomo, czy dana krawędź jest udostępniona czy nie.

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

Pomysł byłoby usunąć powtarzające się pary (zauważ, że zamówienie nie może być taka sama). W powyższym przykładzie usunięta para powinna być ostatnią (p2, p1), ponieważ reprezentuje tę samą krawędź co druga para punktów (p1, p2). Może istnieć jedna, dwie lub więcej podwójnych par punktów.

Muszę wykonać tę operację tak szybko, jak to możliwe, wydajność jest tu najwyższą wartością.

Pomysły

Podczas dodawania punktów na liście mogę przechowywać tymczasowo dwie z nich i sprawdzić, czy lista zawiera ich już, ale oznacza to, patrząc na listę za każdym razem dodawać punkt i nie wydaje mi się to dobrym pomysłem (lista będzie zawierała kilka tysięcy punktów 5000-50000).

Elementy, z których generuję listę punktów, mają kilka węzłów z unikalnym identyfikatorem, więc myślę, że można go w jakiś sposób wykorzystać, tworząc Dictionary zamówionego Tuple<Point3D, Point3D>, a następnie usuwając zduplikowane elementy.

Nie próbowałem tego ostatniego pomysłu, ponieważ nie jestem jeszcze pewien, jak go wdrożyć, i chciałbym usłyszeć, czy jest jakaś inna rzecz, którą można zrobić.

Answer 1

Użyj HashSet<Tuple<Point3D, Point3D>>. Ilekroć otrzymasz nową krawędź - p1, p2, sprawdź istnienie (p1, p2) w zestawie. Sprawdź także istnienie (p2, p1). Jeśli nie istnieje, dodaj (p1, p2) i (p2, p1) do zestawu i użyj krawędzi.

Możesz jeszcze bardziej przyspieszyć, tworząc własne funkcje skrótu i ​​równości, które będą widzieć (p1, p2) jako równe (p2, p1). Nie rób tego, chyba że musisz, operacje Set są bardzo szybkie, wątpię, że poprawa będzie znaczna.

Answer 2

Możesz użyć HashSet do przechowywania wszystkich krawędzi. Szybko to sprawdzić, czy krawędź jest już w zestawie. Ale należy zastąpić GetHashCode i Equals. Zrobiłem prosty przykład.

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); 
    } 
} 

to powinieneś być w stanie dodać każdą linię tak:

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); 
} 

także z GetHashCode i Equals można przechowywać wszystkie linie w List a następnie użyć Distinct metody.

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(); 
}