Link between points and triangles

Question

I want to make a link between 2 classes and im not sure what is the best aproach for it. What i have is a set of points where i use delaunay triangulation to find triangles between them (note that a point can belong to several triangles). Next, the positions of these points are tracked and updated throughout several frames of a video. Therefore, the position of the triangles also need to be updated somehow. Next to that, i would also like to be able to remove a point which gets lost and automatically remove the triangles associated with it. Could you guys give me some advice how to combine these classes?

class Point  
{ 
  float x,y;
}

class Triangle
{
  Point p1, pt2, pt3;
}

Answer 1

Such collections interaction in computer graphics typically be implemented using indices.

class Point
{ 
  float x,y;
}

class Triangle
{
  unsigned int indices[3]; // indices in std::vector<Points>
}

std::vector<Points> points;
std::vector<Triangle> triangles;

Main advantage, comparing with pointers solution is that you can use such index referencing in shader programs.

edit: Code example to remove vertex by known index (not tested). Note that now we store vertices in std::map, to not break indexing when erasing indices.

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 much space for optimizations: first is a types of containers, but it depends on size of collection, and how often you inserting/erasing data.

Answer 2

You could probably 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 could also keep ALL triangle for each frame like so:

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

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

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

I think you need something to remove the triangles from (or add them to). I'd have code a bit like

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

This code would re-find the delaunay triangles of the new collections of points. This may prove to be slow, and there may be some clever algos you could use to speed it up later.

Answer 4

@slava is referring to the fact that you said a point can belong to several triangles. With that in mind your classes should look something like:

class Point  
{ 
  float x,y;
}

class Triangle
{
  Point * p1;
  Point * pt2;
  Point * pt3;
}

The way you've defined your Triangle class, you would have been carrying around copies of the points. If the points had been modified, your Triangle class would have had to be updated separately.

Keeping in mind that these aren't literal class definitions (everything's private) and that you'll probably want to use a reference counted pointer like unique_ptr

Answer 5

Triangle should contain not points but pointers to points, cause points exist outside of triangles. Also it might be convenient to keep the list of associated triangles (list of pointers of course) in each point, but that really depend on usage.