删除List <object>的重复对

Question

问题

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

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

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

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

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

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

我需要尽快做这个操作,性能在这里是最重要的.

思路

在列表中添加点时,我可以临时存储其中的两个,并检查列表是否已经包含它们,但这意味着每次添加一个点时都会查看列表,这对我来说似乎不是一个好主意(列表将包含几千点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)。除非需要，否则不要这样做，Set 操作非常快，我怀疑改进会很大。