How to get outer edges of a mesh (edges which are part of only one triangle)

Question

Consider a std::vector<int> navigationMeshTriangles filled with coordinates (not indices of vertexes) of triangles, in following order - x1, y1, x2, y2, x3, y3 (every triangle spans six entries in this std::vector). Every triangle shares between one and two edges with others:

What I want to achieve is a std::vector<int> outerEdges, which contains outer edges (edges which are part of only one triangle), in following order - x1, y1, x2, y2.

I've already tried such approach, but it doesn't work (outerEdges.size() is always 0)

bool f, s, t;
for(unsigned int i = 0; i < navigationMeshTriangles.size(); i += 6)
{
    f = false;
    s = false;
    t = false;
    for(unsigned int z = 0; z < navigationMeshTriangles.size(); z += 6)
    {
        if(i == z)
            continue;
        if((navigationMeshTriangles[i] == navigationMeshTriangles[z] || navigationMeshTriangles[i] == navigationMeshTriangles[z+2] ||
           navigationMeshTriangles[i] == navigationMeshTriangles[z+4]) && (navigationMeshTriangles[i+1] == navigationMeshTriangles[z+1] ||
           navigationMeshTriangles[i+1] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+1] == navigationMeshTriangles[z+5]))
        {
            f = true;
        }
        if((navigationMeshTriangles[i+2] == navigationMeshTriangles[z] || navigationMeshTriangles[i+2] == navigationMeshTriangles[z+2] ||
           navigationMeshTriangles[i+2] == navigationMeshTriangles[z+4]) && (navigationMeshTriangles[i+3] == navigationMeshTriangles[z+1] ||
           navigationMeshTriangles[i+3] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+3] == navigationMeshTriangles[z+5]))
        {
            s = true;
        }
        if((navigationMeshTriangles[i+4] == navigationMeshTriangles[z] || navigationMeshTriangles[i+4] == navigationMeshTriangles[z+2] ||
           navigationMeshTriangles[i+4] == navigationMeshTriangles[z+4]) && (navigationMeshTriangles[i+5] == navigationMeshTriangles[z+1] ||
           navigationMeshTriangles[i+5] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+5] == navigationMeshTriangles[z+5]))
        {
            t = true;
        }

    }
    if(!f && !s)
    {
        outerEdges.push_back(navigationMeshTriangles[i]);
        outerEdges.push_back(navigationMeshTriangles[i+1]);
        outerEdges.push_back(navigationMeshTriangles[i+2]);
        outerEdges.push_back(navigationMeshTriangles[i+3]);
    }
    if(!s && !t)
    {
        outerEdges.push_back(navigationMeshTriangles[i+2]);
        outerEdges.push_back(navigationMeshTriangles[i+3]);
        outerEdges.push_back(navigationMeshTriangles[i+4]);
        outerEdges.push_back(navigationMeshTriangles[i+5]);
    }
    if(!f && !t)
    {
        outerEdges.push_back(navigationMeshTriangles[i]);
        outerEdges.push_back(navigationMeshTriangles[i+1]);
        outerEdges.push_back(navigationMeshTriangles[i+4]);
        outerEdges.push_back(navigationMeshTriangles[i+5]);
    }

}
std::cout << "outer edges: " << std::to_string(outerEdges.size()/4) << std::endl;

I am aware that those if statements are complex, and propably they are the cuprits, but i cant see anything wrong with them (that might have something to do with the fact that it is 3 AM and i am drunk).

Answer 1

After sobering up and trying SandieDeDia's suggestion, i came up with this solution:

bool f, s, t;
    for(unsigned int i = 0; i < navigationMeshTriangles.size(); i += 6)
    {
        f = false;
        s = false;
        t = false;
        for(unsigned int z = 0; z < navigationMeshTriangles.size(); z += 6)
        {
            if(i == z)
                continue;
            if((navigationMeshTriangles[i] == navigationMeshTriangles[z] || navigationMeshTriangles[i] == navigationMeshTriangles[z+2] || navigationMeshTriangles[i] == navigationMeshTriangles[z+4])
               && (navigationMeshTriangles[i+1] == navigationMeshTriangles[z+1] || navigationMeshTriangles[i+1] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+1] == navigationMeshTriangles[z+5])
               && (navigationMeshTriangles[i+2] == navigationMeshTriangles[z] || navigationMeshTriangles[i+2] == navigationMeshTriangles[z+2] || navigationMeshTriangles[i+2] == navigationMeshTriangles[z+4])
               && (navigationMeshTriangles[i+3] == navigationMeshTriangles[z+1] || navigationMeshTriangles[i+3] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+3] == navigationMeshTriangles[z+5]))
            {
                f = true;
            }
            if((navigationMeshTriangles[i+2] == navigationMeshTriangles[z] || navigationMeshTriangles[i+2] == navigationMeshTriangles[z+2] || navigationMeshTriangles[i+2] == navigationMeshTriangles[z+4])
               && (navigationMeshTriangles[i+3] == navigationMeshTriangles[z+1] || navigationMeshTriangles[i+3] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+3] == navigationMeshTriangles[z+5])
               && (navigationMeshTriangles[i+4] == navigationMeshTriangles[z] || navigationMeshTriangles[i+4] == navigationMeshTriangles[z+2] || navigationMeshTriangles[i+4] == navigationMeshTriangles[z+4])
               && (navigationMeshTriangles[i+5] == navigationMeshTriangles[z+1] || navigationMeshTriangles[i+5] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+5] == navigationMeshTriangles[z+5]))
            {
                s = true;
            }
            if((navigationMeshTriangles[i] == navigationMeshTriangles[z] || navigationMeshTriangles[i] == navigationMeshTriangles[z+2] || navigationMeshTriangles[i] == navigationMeshTriangles[z+4])
               && (navigationMeshTriangles[i+1] == navigationMeshTriangles[z+1] || navigationMeshTriangles[i+1] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+1] == navigationMeshTriangles[z+5])
               && (navigationMeshTriangles[i+4] == navigationMeshTriangles[z] || navigationMeshTriangles[i+4] == navigationMeshTriangles[z+2] || navigationMeshTriangles[i+4] == navigationMeshTriangles[z+4])
               && (navigationMeshTriangles[i+5] == navigationMeshTriangles[z+1] || navigationMeshTriangles[i+5] == navigationMeshTriangles[z+3] || navigationMeshTriangles[i+5] == navigationMeshTriangles[z+5]))
            {
                t = true;
            }

        }
        if(!f)
        {
            outerEdges.push_back(navigationMeshTriangles[i]);
            outerEdges.push_back(navigationMeshTriangles[i+1]);
            outerEdges.push_back(navigationMeshTriangles[i+2]);
            outerEdges.push_back(navigationMeshTriangles[i+3]);
        }
        if(!s)
        {
            outerEdges.push_back(navigationMeshTriangles[i+2]);
            outerEdges.push_back(navigationMeshTriangles[i+3]);
            outerEdges.push_back(navigationMeshTriangles[i+4]);
            outerEdges.push_back(navigationMeshTriangles[i+5]);
        }
        if(!t)
        {
            outerEdges.push_back(navigationMeshTriangles[i]);
            outerEdges.push_back(navigationMeshTriangles[i+1]);
            outerEdges.push_back(navigationMeshTriangles[i+4]);
            outerEdges.push_back(navigationMeshTriangles[i+5]);
        }

    }
    std::cout << "outer edges: " << std::to_string(outerEdges.size()/4) << std::endl;

Looks even worse than before, but at least it works (i tested the generated coordinates with a GIMP script, they are correct).

One weird thing is that some edges are not detected as outer. I used a Blender script to generate the mesh data, and said edges are original (unmodified) parts of the Plane mesh which modified to make the NavMesh. But, that must be something wrong with my Blender script, not the solution i just posted. I plan switching to other mesh generation methods once my project matures anyway.

Answer 2

if I understand correctly, you want the algorithm to assign f = false if the first point (x1,y1)of the triangle is not shared with any other triangle. But all triangles on the outer boundary do share at least two points with other triangles(!?), so you will never find a triangle that fulfills your final if conditions and size will be 0.

I think it would be better to check for lines instead.

Also notice that in your algorithm you are not looking for polygons sharing a point (x1,y1), but polygons such that any of its 3 vertices have a variable x equal to x1 and variable y equal to y1 (no need to be the same vertex)