The relationship between points and triangles

Question

I want to make a link between two classes, and I'm not sure if this is the best aproach for this. I have a set of points at which I use delaunay triangulation to find triangles between them (note that a point can belong to several triangles). Then the positions of these points are tracked and updated over several frames of the video. Therefore, the position of the triangles also needs to be updated in some way. In addition, I would also like to delete the deleted point and automatically delete the triangles associated with it. Could you guys give me advice on how to combine these classes?

class Point { float x,y; } class Triangle { Point p1, pt2, pt3; } 

Answer 1

Such interaction of collections in computer graphics is usually implemented using indexes.

 class Point { float x,y; } class Triangle { unsigned int indices[3]; // indices in std::vector<Points> } std::vector<Points> points; std::vector<Triangle> triangles; 

The main advantage compared to the solution of pointers is that you can use this index binding in shader programs.

change Example code to remove a vertex at a known index (not verified). Note that now we save the vertices in std :: map, so as not to break the index when erasing indexes.

 class Mesh { public: struct Vertex { float x, y; }; struct Triangle { bool Contains(unsigned int index) const { return ((indices[0] == index) || (indices[1] == index) || (indices[2] == index)); } unsigned int indices[3]; }; // Removes vertex and corresponding triangles void RemoveByIndex(unsigned int index) { for (auto it = triangles.begin(); it != triangles.end(); ++it) { if (it->Contains(index)) triangles.erase(it); } vertices.erase(index); } private: std::map<unsigned int, Vertex> vertices; std::vector<Triangle> triangles; }; 

Of course, there are many opportunities for optimization: at first these are container types, but it depends on the size of the collection and how often you insert / delete data.

Answer 2

@slava refers to what you said that a point can belong to several triangles. With that in mind, your classes should look something like this:

 class Point { float x,y; } class Triangle { Point * p1; Point * pt2; Point * pt3; } 

As you defined your Triangle class, you would carry copies of the copies. If the points were changed, your Triangle class would have to be updated separately.

Bearing in mind that these are not literal class definitions (all private), and that you probably want to use a pointer with reference counting, for example unique_ptr

Answer 3

Perhaps you can use the following data structures:

 struct Point { double x, y; }; struct Triangle { unsigned int ids[3]; bool isValid; }; // Store points for each frame std::vector<std::vector<Point>> points; // Store triangles std::vector<Triangle> triangles; 

You can also save the ALL triangle for each frame as follows:

 // Store triangles for each frame std::vector<std::vector<Triangle>> triangles; 

And here is a "working example". 4 points, 2 triangles for 3 frames. It outputs only triangles whose vertices are ALL positive. From one frame to another, the point cloud translates to -1 along the Y axis. This is obviously a fake test, but it will hopefully help you get started.

 #include <vector> #include <iostream> struct Point { double x, y; }; struct Triangle { unsigned int ids[3]; bool isValid; }; void TrackFirstFrame(std::vector<Point> &firstFrame) { Point p1, p2, p3, p4; p1.x = 1; p1.y = 0; p2.x = 2; p2.y = 1; p3.x = 1; p3.y = 2; p4.x = 0; p4.y = 1; firstFrame[0] = p1; firstFrame[1] = p2; firstFrame[2] = p3; firstFrame[3] = p4; } void Delaunay(const std::vector<Point> &points, std::vector<Triangle> &triangles) { Triangle t1; t1.ids[0] = 0; t1.ids[1] = 1; t1.ids[2] = 3; triangles.push_back(t1); Triangle t2; t2.ids[0] = 1; t2.ids[1] = 2; t2.ids[2] = 3; triangles.push_back(t2); } // Assumption: all previous frame points give a new tracked point for current frame void TrackFrame(const std::vector<Point> &previousFramePoints, unsigned int currentFrame, std::vector<Point> &trackedPoints) { for (unsigned int i = 0; i < previousFramePoints.size(); ++i) { Point previousPoint = previousFramePoints[i]; Point trackedPoint; trackedPoint.x = previousPoint.x; trackedPoint.y = previousPoint.y - 1; trackedPoints[i] = trackedPoint; } } // Assumption: all vertices are positive. If not, triangle is invalid void UpdateTriangles(const std::vector<Point> &points, std::vector<Triangle> &triangles) { std::vector<Triangle>::iterator trianglesIT = triangles.begin(); for (; trianglesIT != triangles.end(); ++trianglesIT) { (*trianglesIT).isValid = true; // By default for (unsigned int i = 0; i < 3; ++i) { Point vertex = points[(*trianglesIT).ids[i]]; if (vertex.x < 0 || vertex.y < 0) { (*trianglesIT).isValid = false; break; } } } } void PrintPoints(const std::vector<Point> &points) { std::cout<<"Points"<<std::endl; std::vector<Point>::const_iterator pointsIT = points.begin(); for (; pointsIT != points.end(); ++pointsIT) { std::cout<<"("<<pointsIT->x<<", "<<pointsIT->y<<")"<<std::endl; } } void PrintTriangles(const std::vector<Triangle> &triangles) { std::cout<<"Triangles"<<std::endl; std::vector<Triangle>::const_iterator trianglesIT = triangles.begin(); for (; trianglesIT != triangles.end(); ++trianglesIT) { if (trianglesIT->isValid) { std::cout<<"["<<trianglesIT->ids[0]<<", "<<trianglesIT->ids[1]<<", "<<trianglesIT->ids[2]<<"])"<<std::endl; } } } int main() { unsigned int nbFrames = 3; unsigned int nbPoints = 4; // Init 2D points std::vector<std::vector<Point>> points; points.resize(nbFrames); std::vector< std::vector<Point> >::iterator framesIT = points.begin(); for (; framesIT != points.end(); ++framesIT) { framesIT->resize(nbPoints); } TrackFirstFrame(points[0]); std::cout<<"Frame 0"<<std::endl; PrintPoints(points[0]); // Init triangles with Delaunay. 4 points => 2 triangles; std::vector<Triangle> triangles; Delaunay(points[0], triangles); PrintTriangles(triangles); for (unsigned int i = 1; i < nbFrames; ++i) { std::cout<<"Track frame #"<<i<<std::endl; TrackFrame(points[i-1], i, points[i]); PrintPoints(points[i]); UpdateTriangles(points[i], triangles); PrintTriangles(triangles); } char c; std::cin >> c; } 

Answer 4

A triangle should not contain points, but pointers to points, because points exist outside the triangles. It may also be convenient to keep a list of connected triangles (a list of pointers, of course) at each point, but it really depends on usage.

Answer 5

I think you need something to remove the triangles (or add them to). I would be a bit like code

 std::vector<Triangle> update_triangles(const std::vector<Point> & points) { //... } 

This code will again find the triangles of the triangles of the new point collections. This might turn out to be slow, and there might be some kind of clever algos that you could use to speed it up later.