DCEL数据结构特定向量元素输出垃圾值问题排查

实现代码 #

#include<bits/stdc++.h>
using namespace std;

class Vertex;
class Edge;
class Face;

class Vertex{
    public:
    float x;
    float y;
    Edge* edge; 

    Vertex(float x, float y) : x(x), y(y), edge(NULL) {}
};

class Edge{
    public:
    Vertex origin;
    Edge* twin;
    Edge* prev;
    Edge* next;
    Face* right;

    Edge(Vertex origin): origin(origin), twin(NULL), prev(NULL), next(NULL), right(NULL) {}
};

class Face{
    public:
    Edge* edge;

    Face(Edge* edge): edge(edge){}
};

class DCEL{
    public:
    vector<Vertex> vertices;
    vector<Edge> edges;
    vector<Face> faces;

    void addVertex(Vertex &vertex){
        vertices.push_back(vertex);
    }

    void addEdge(Vertex *origin, Vertex *destination){
        Edge e1 = Edge(*origin);
        Edge e2 = Edge(*destination);
        // origin->edge = &e1;
        // destination->edge = &e2;
        edges.push_back(e1);
        edges.push_back(e2);
        edges[edges.size()-1].twin = &edges[edges.size()-2];
        edges[edges.size()-2].twin = &edges[edges.size()-1];
        printEdges();
    }

    void addFace(Edge *edge){
        Face f1(edge);
        faces.push_back(f1);

    }

    void printVertices (){
        cout << "Vertices: " << endl;
        cout << "Count: "<< vertices.size() << endl;
        for (auto v: vertices){
            cout << "(" << v.x << ", " << v.y << ")" << endl;
        }
        cout << endl;
    }

    void printEdges (){
        cout << "Edges: " << endl;
        cout << "Count: " << edges.size() << endl;
        for (auto e: edges){
            cout << "(" << e.origin.x << ", " << e.origin.y << ")";
            cout << " <-> (" << e.twin->origin.x << ", " << e.twin->origin.y << ")" << endl;
        }
        cout << endl;
    }

    void printFaces (){
        cout << "Faces: " << endl;
        cout << "Count: "<< faces.size() << endl; // TODO: to be changed
        for (auto f: faces){
            cout << "(" << f.edge->origin.x << ", " << f.edge->origin.y << ")" << endl;
        }
        cout << endl;
    }

    void print(){
        cout << "-----" << endl;
        printVertices();
        printEdges();
        printFaces();
        cout << "-----" << endl;
    }

};

int main(){

    DCEL dcel;
    Vertex v1(0.0, 0.0);
    Vertex v2(1.0, 0.0);
    Vertex v3(1.0, 1.0);
    Vertex v4(0.0, 1.0);
    // Vertex v5(0.5, 0.5);

    dcel.addVertex(v1);
    dcel.addVertex(v2);
    dcel.addVertex(v3);
    dcel.addVertex(v4);
    // dcel.addVertex(v5);

    dcel.addEdge(&v1, &v2);
    dcel.addEdge(&v2, &v3);
    dcel.addEdge(&v3, &v4);
    dcel.addEdge(&v4, &v1);

    dcel.addFace(&dcel.edges[0]);

    cout << endl;
    dcel.print();
}

调试操作与异常现象 #

每次调用addEdge时打印边列表，首次执行addEdge输出正常，但后续添加边时，部分边的twin顶点出现垃圾值（如(1.54853e+21, 7.00649e-45)）。通过VSCode调试发现，异常发生在将元素推入vector时。

异常输出 #

Edges: 
Count: 2
(0, 0) <-> (1, 0)
(1, 0) <-> (0, 0)

Edges: 
Count: 4
(0, 0) <-> (1, 0)
(1, 0) <-> (1.54853e+21, 7.00649e-45)
(1, 0) <-> (1, 1)
(1, 1) <-> (1, 0)

Edges: 
Count: 6
(0, 0) <-> (1, 0)
(1, 0) <-> (1.54853e+21, 7.00649e-45)
(1, 0) <-> (1, 1)
(1, 1) <-> (1, 0)
(1, 1) <-> (0, 1)
(0, 1) <-> (1, 1)

Edges: 
Count: 8
(0, 0) <-> (1, 0)
(1, 0) <-> (1.54853e+21, 7.00649e-45)
(1, 0) <-> (1, 1)
(1, 1) <-> (1, 0)
(1, 1) <-> (0, 1)
(0, 1) <-> (1, 1)
(0, 1) <-> (0, 0)
(0, 0) <-> (0, 1)


-----
Vertices: 
Count: 4
(0, 0)
(1, 0)
(1, 1)
(0, 1)

Edges: 
Count: 8
(0, 0) <-> (1, 0)
(1, 0) <-> (1.54853e+21, 7.00649e-45)
(1, 0) <-> (1, 1)
(1, 1) <-> (1, 0)
(1, 1) <-> (0, 1)
(0, 1) <-> (1, 1)
(0, 1) <-> (0, 0)
(0, 0) <-> (0, 1)

Faces: 
Count: 1
(0, 0)

-----

问题原因 #

核心问题是vector的内存重分配机制：当vector容量不足时，会重新分配更大的内存空间，将原有元素拷贝后释放旧内存。而代码中直接用&edges[下标]获取的指针指向旧内存地址，旧内存释放后这些指针变成野指针，访问时就会读取到垃圾数据。

另外，Edge类中存储Vertex对象而非指针，会导致顶点数据重复拷贝，虽然不是本次问题的直接原因，但不符合DCEL的设计逻辑（DCEL通常用顶点指针共享实例）。

修复方案 #

方案1：使用智能指针存储Edge（推荐） #

将vector<Edge>改为vector<unique_ptr<Edge>>，避免vector扩容导致的对象移动，保证指针地址始终有效：

1. 修改DCEL类的edges成员：

vector<unique_ptr<Edge>> edges;

2. 修改addEdge方法：

void addEdge(Vertex *origin, Vertex *destination){
    auto e1 = make_unique<Edge>(*origin);
    auto e2 = make_unique<Edge>(*destination);
    e1->twin = e2.get();
    e2->twin = e1.get();
    edges.push_back(move(e1));
    edges.push_back(move(e2));
    printEdges();
}

3. 修改printEdges方法适配智能指针：

void printEdges (){
    cout << "Edges: " << endl;
    cout << "Count: " << edges.size() << endl;
    for (auto &e: edges){
        cout << "(" << e->origin.x << ", " << e->origin.y << ")";
        cout << " <-> (" << e->twin->origin.x << ", " << e->twin->origin.y << ")" << endl;
    }
    cout << endl;
}

方案2：提前预留vector容量 #

如果坚持存储对象，可以在添加边前提前预留足够容量，避免vector扩容：
在main函数添加边前调用：

dcel.edges.reserve(8); // 4条边对应8个Edge对象

此方法仅临时解决问题，后续添加更多边仍会触发同样异常。

额外优化：Vertex改为指针存储 #

为符合DCEL设计，将Edge中的origin改为Vertex*，避免顶点数据重复拷贝：

1. 修改Edge类：

class Edge{
    public:
    Vertex* origin;
    Edge* twin;
    Edge* prev;
    Edge* next;
    Face* right;

    Edge(Vertex* origin): origin(origin), twin(NULL), prev(NULL), next(NULL), right(NULL) {}
};

2. 修改addEdge方法：

void addEdge(Vertex *origin, Vertex *destination){
    auto e1 = make_unique<Edge>(origin);
    auto e2 = make_unique<Edge>(destination);
    e1->twin = e2.get();
    e2->twin = e1.get();
    edges.push_back(move(e1));
    edges.push_back(move(e2));
    printEdges();
}

修复后的输出 #

所有边的twin顶点均显示正确值：

Edges: 
Count: 2
(0, 0) <-> (1, 0)
(1, 0) <-> (0, 0)

Edges: 
Count: 4
(0, 0) <-> (1, 0)
(1, 0) <-> (0, 0)
(1, 0) <-> (1, 1)
(1, 1) <-> (1, 0)

Edges: 
Count: 6
(0, 0) <-> (1, 0)
(1, 0) <-> (0, 0)
(1, 0) <-> (1, 1)
(1, 1) <-> (1, 0)
(1, 1) <-> (0, 1)
(0, 1) <-> (1, 1)

Edges: 
Count: 8
(0, 0) <-> (1, 0)
(1, 0) <-> (0, 0)
(1, 0) <-> (1, 1)
(1, 1) <-> (1, 0)
(1, 1) <-> (0, 1)
(0, 1) <-> (1, 1)
(0, 1) <-> (0, 0)
(0, 0) <-> (0, 1)


-----
Vertices: 
Count: 4
(0, 0)
(1, 0)
(1, 1)
(0, 1)

Edges: 
Count: 8
(0, 0) <-> (1, 0)
(1, 0) <-> (0, 0)
(1, 0) <-> (1, 1)
(1, 1) <-> (1, 0)
(1, 1) <-> (0, 1)
(0, 1) <-> (1, 1)
(0, 1) <-> (0, 0)
(0, 0) <-> (0, 1)

Faces: 
Count: 1
(0, 0)

-----

内容的提问来源于stack exchange，提问作者Nameet Rajore