#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)
-----
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
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:
which outputs