#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
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)