Rimozione coppie duplicate di un elenco <object>

Question

Problema

Sto mostrando una geometria utilizzando linee semplici in una libreria 3D WPF. Un esempio di esso potrebbe essere visto nella figura seguente:

In esso si può vedere una serie di triangoli e quadrati. Il modo in cui sto tramando questo è che fornisco uno List<Point3D> in cui metto coppie di punti che rappresentano ciascun segmento.

Il problema è che ci sono molti bordi duplicati e vorrei evitare questo dato che questo tipo di rappresentazione sembra essere molto impegnativo.

L'elenco di punti viene generato iterando su ogni Element che contiene N vertici. Non è a conoscenza se un determinato bordo è condiviso o meno.

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

L'idea sarebbe quella di rimuovere le coppie ripetute (si noti che l'ordine potrebbe non essere lo stesso). Nell'esempio sopra la coppia rimossa dovrebbe essere l'ultima (p2, p1), poiché rappresenta lo stesso bordo della seconda coppia di punti (p1, p2). Potrebbero esserci una, due o più coppie di punti duplicate.

Ho bisogno di fare questa operazione il più velocemente possibile, le prestazioni sono migliori qui.

Idee

Mentre l'aggiunta di punti nella lista ho potuto memorizzare temporaneamente due di loro e verificare se la lista li contiene già, ma questo implica cercando in un elenco ogni volta aggiungo un punto e non lo fa mi sembra una buona idea (la lista conterrà diverse migliaia di punti 5000-50000).

Gli elementi di cui generi l'elenco di punti hanno diversi nodi con un ID univoco, quindi penso che potrebbe essere utilizzato in qualche modo creando uno Tuple<Point3D, Point3D> ordinato e quindi rimuovendo gli elementi duplicati.

Non ho provato l'ultima idea perché non sono sicuro di come implementarlo ancora, e mi piacerebbe sentire se c'è qualche altra cosa che può essere fatta.

Answer 1

Utilizzare un HashSet<Tuple<Point3D, Point3D>>. Ogni volta che ottieni un nuovo vantaggio - p1, p2, controlla l'esistenza di (p1, p2) nel set. Controlla anche l'esistenza di (p2, p1). Se nessuno dei due esiste, aggiungi (p1, p2) e (p2, p1) all'insieme e usa il bordo.

È possibile accelerare ulteriormente creando le proprie funzioni di hash e uguaglianza che vedranno (p1, p2) come uguali a (p2, p1). Non farlo a meno che non sia necessario, le operazioni di Set sono molto veloci, dubito che il miglioramento sarà considerevole.

Answer 2

È possibile utilizzare HashSet per memorizzare tutti i bordi. È veloce da controllare, il bordo è già nel set. Ma è necessario eseguire l'override di GetHashCode e Equals. Ho fatto un semplice esempio.

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

allora si dovrebbe essere in grado di aggiungere ogni riga come questa:

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

Anche con GetHashCode e Equals è possibile memorizzare tutte le linee in List e quindi utilizzare Distinct metodo.

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