假设我有一个点向量:
vector<int> points;
三角形存储组成它们的点的索引:
struct Triangle {
int p0, p1, p2;
};
Triangle tri0;
tri0.p0 = 3;
tri0.p1 = 6;
tri0.p2 = 7;
Triangle tri1;
tri1.p0 = 4;
tri1.p1 = 6;
tri1.p2 = 7;
现在我决定擦除point[3]。然而，如果我擦除point[3]，索引3之后的点的索引将移回，所以我需要通知所有三角形它们存储的索引可能会改变。通知三角形的合理方式是什么?
在我看来，最合理的方法是而不是删除顶点。因为如果你真的删除它们，那么你必须将所有的顶点向右移动(平均V/2元素)，然后你必须遍历所有的三角形(T总是检查)。
相反，您可以将顶点标记为dead。简单地把一些坏值点数组(在你的样本-1是ok的)。在每次删除中添加标记只需要O(1)。有时，您可能想要物理地移除死顶点。你可以用两个完整的通道(一个顶点，一个三角形)，并在线性时间O(V + T)压缩你的网格。
为了使事情易于使用，我建议为你的网格创建一个类。在网格对象中，对类用户透明地维护失效条目的数量。当删除后死条目的部分变得相当大(例如超过一半)时，调用死顶点消除。您还可以创建三角形枚举方法，它只会在活动三角形上迭代(只是为了方便)。
此方法确保O(1)每次删除的平摊时间，如果花费在压缩上的时间不大于删除次数乘以常数。给定T <= c V在任意时刻(对于某常数c)，它为真。实际上，不太可能看到三角形数量大于顶点数量的网格，所以你很好。
一个非常不同的解决方案是使用链表而不是数组来存储顶点和三角形(彼此有指针)。在这种情况下，你可以在O(Sv)时间内移除顶点v，其中Sv是它所属的三角形数。但是这种数据结构的底层性能可能很差。
编辑:另一个问题出现在我的脑海里。死顶点消除对用户来说是透明的，但此时用户可能会陷入三角形或顶点枚举的中间。显然，这种情况会造成很大的麻烦。
为了避免危险，在你的网格中添加lock/unlock方法。这样你就可以确保只要一个网格被锁定，它的顶点就会保持在索引方向上。在这种情况下，您可以安全地执行顶点过滤之类的操作，例如