删除List 的重复对

Issue

I'm displaying a geometry using simple lines in a 3D WPF library. An example of it could be seen in the next picture:

我在3D WPF库中使用简单的线条显示几何体。在下一张图片中可以看到它的一个例子:

In it you can see a set of triangles and quads. The way I'm plotting this is that I provide a List<Point3D> in which I place pairs of points representing each segment.

在其中,您可以看到一组三角形和四边形。我正在绘制这个的方式是我提供了一个List ,其中我放置了代表每个段的点对。

The problem is that there are a lot of duplicate edges and I would like to avoid this as this type of representation seems to be very resource demanding.

问题是有很多重复的边缘,我想避免这种情况,因为这种类型的表示似乎非常需要资源。

The points list is generated iterating over each Element that contains N vertices. It is not aware of if a particular edge is shared or not.

迭代在包含N个顶点的每个元素上生成点列表。它不知道是否共享特定边缘。

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

,p1,p1,p2,p2,p333,p333,p89,p89,p2,p2,p1>

The idea would be to remove the repeated pairs (note that the order could be not the same). In the example above the removed pair should be the last one (p2, p1), as it represents the same edge as the second pair of points (p1, p2). There could be one, two, or more duplicate pairs of points.

想法是删除重复的对(注意顺序可能不一样)。在上面的示例中,移除的对应该是最后一个(p2,p1),因为它表示与第二对点(p1,p2)相同的边。可能有一对,两个或更多重复的点对。

I need to do this operation as fast as possible, performance is top prio here.

我需要尽快完成这项操作,性能是最重要的。

Ideas

While adding points in the list I could store temporarily two of them and check if the list already contains them, but this implies looking into a list each time I add a point and doesn't seems a good idea to me (the list will contain several thousand of points 5000-50000).

在列表中添加点时,我可以临时存储其中的两个并检查列表是否已包含它们,但这意味着每次添加一个点时都会查看列表,这对我来说似乎不是一个好主意(列表将包含几千点5000-50000)。

The elements of which I generate the points list have several nodes with an unique ID so I think it could be used somehow by creating a Dictionary of ordered Tuple<Point3D, Point3D> and then removing the duplicate items.

我生成点列表的元素有几个具有唯一ID的节点,所以我认为它可以通过创建有序元组的字典 以及然后删除重复项来以某种方式使用。 ,point3d>

I haven't tried the last idea as I'm not sure how to implement it yet, and I would like to hear if there is some other thing that can be done.

我还没有尝试过最后一个想法,因为我还不确定如何实现它,我想知道是否还有其他事情可以做。

2 个解决方案

#1

You can use HashSet to store all the edges. It is fast to check, is the edge is already in set. But you should override GetHashCode and Equals. I made a simple example.

您可以使用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);
    }
}

then you should be able to add each line like this:

那么你应该能够像这样添加每一行:

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

Also with GetHashCode and Equals you can store all the lines in List and then use Distinct method.

使用GetHashCode和Equals,您可以将所有行存储在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();
}

#2

Use a HashSet<Tuple<Point3D, Point3D>> . Whenever you get a new edge - p1,p2, check for (p1,p2)'s existence in the set. Also check for (p2,p1)'s existence. If neither exists, add (p1,p2) and (p2,p1) to the set and use the edge.

使用HashSet >。每当你得到一个新的边缘 - p1,p2时,检查集合中是否存在(p1,p2)。还要检查(p2,p1)是否存在。如果两者都不存在,则将(p1,p2)和(p2,p1)添加到集合中并使用边缘。

You can further speed this up by crafting your own hash and equality functions that will see (p1,p2) as equal to (p2,p1). Don't do that unless you need to, Set operations are very quick, I doubt the improvement will be considerable.

您可以通过制作自己的哈希和相等函数来进一步加快速度,这些函数将看到(p1,p2)等于(p2,p1)。除非你需要,不要这样做,Set操作非常快,我怀疑改进会相当可观。