DCEL data structure throwing garbage value for particular vector element?

Question

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

Above is the code I implemented. Im printing the edges list every time I execute addEdge to debug it.

The output I'm getting is really absurd

I'm getting the right value when addEdge executes the first time (i.e. (0,0) ) but then it changes abruptly (in VSCode debugger it shows this change happens when I'm trying to push it inside the 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)

-----

You have a weird mix of by-value and by-pointer passing of your stuff. This is not likely to work well. I recommend making everything a pointer An Edge should not *contain* a Vertex, it should *point to* a Vertex. The DCEL should have containers of *pointers* to Edge Vertex and Face. — n. m. could be an AI, Mar 01 '23 at 18:41
See [Why should I not #include ?](https://stackoverflow.com/q/31816095) and [Why using namespace std is bad practice](https://stackoverflow.com/questions/1452721). — prapin, Mar 01 '23 at 18:46

ravenspoint · Accepted Answer · 2023-03-01T22:30:25.993

The reason this happens is because push_back is not doing what you think it is. In reality, push_back makes and stores a new copy of the edge using the default edge copy constructor - which plays havoc with pointers.

The quick fix is to supply a copy constructor that does the correct thing with pointers.

You also need to take a look at how your storing vertices. Consider

main() {
    DCEL dcel;
    Vertex v1(0.0, 0.0);
    Vertex v2(1.0, 0.0);
    Vertex v3(1.0, 1.0);

    dcel.addVertex(v1);
    dcel.addVertex(v2);
    dcel.addVertex(v3);


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

Where is v1 stored? Well there is the original one that was constructed by the main function and stored there as local variable. Then there is a copy of V1 stored in the DCEL::vertices vector. There are also two copies stored in the Edge::Origin attribute of the two edges. Which of these 4 copies should we update if needed?

Your design is riddled with this sort of problem. It needs a major rethink. My suggestion: your code would be much safer if you used, instead of pointers, indices to the vertices and edges stored in the DCEL vectors.

Something like this:

#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:
    int origin;
    int twin;
    Edge *prev;
    Edge *next;
    Face *right;

    Edge(int o) : origin(o), 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;

    int addVertex(int x, int y)
    {
        vertices.push_back(Vertex(x,y));
        return vertices.size()-1;
    }

    void addEdge(int origin,int destination)
    {
        edges.push_back( Edge(origin));
        int e1 = edges.size()-1;
        edges.push_back( Edge(destination));
        int e2 = edges.size()-1;
        edges[e1].twin = e2;
        edges[e2].twin = e1;
        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 << "(" << vertices[e.origin].x << ", " << vertices[e.origin].y << ")";
            cout << " <-> (" << vertices[edges[e.twin].origin].x << ", " << vertices[edges[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;

    int v1 = dcel.addVertex(0,0);
    int v2 = dcel.addVertex(1,0);
    int v3 = dcel.addVertex(1,1);
    int v4 = dcel.addVertex(0,1);

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

which outputs

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)

DCEL data structure throwing garbage value for particular vector element?

1 Answers1