Find outlines of a tile collection On a game I'm working curently I keep on memory a simplified representation of the map which only have solid and non-solid cells. I need to get the outline of the shapes that adjacent cells might create, something like this:



I do not have a 8×8 array of bools on memory but a container of cell1 objects:

struct point { int x{}, y{}; };
struct line { point b{}, e{}; };
struct cell
{
    int x{}, y{};
    std::array&lt;line, 4&gt; lines() const
    {
        return
        {{
            {{x + 0, y + 0}, {x + 0, y + 1}},
            {{x + 0, y + 0}, {x + 1, y + 0}},
            {{x + 0, y + 1}, {x + 1, y + 1}},
            {{x + 1, y + 0}, {x + 1, y + 1}},
        }};
    };
};


Mi goal is to obtain a container with all the otulines, for example the outlines of the square at the top right corner are:

{
    // Vertical line (x6) that starts at position y0 and ends at position y2
    {{6, 0}, {6, 2}},
    // Horizontal line (y0) that starts at position x6 and ends at position x8
    {{6, 0}, {8, 0}},
    // …
    {{6, 2}, {8, 2}},
    // …
    {{8, 0}, {8, 2}}
}


The algorithm I'm using have the following steps:


Transform cells to lines.
Save lines into container, if the line is already on that container: delete it (this Will get rid of lines inside shapes).
Test each line against the others, if two lines are colinear and the end of one is the beggining of the other: merge it.




template &lt;template &lt;typename&gt; typename container_t&gt;
auto vertex_of(const container_t&lt;cell&gt; &amp;cells)
{
    std::set&lt;line&gt; outlines;

    for (const auto &amp;cell : cells)
        // Transform cells to lines
        for (const auto &amp;line : cell.lines())
            // Save lines into temp container
            if (auto [i, b] = outlines.insert(line); !b)
                // If the line is already on the container: delete it
                outlines.erase(i);

    std::vector&lt;line&gt; result;
    // Test each line against the others, if two lines are colinear and the end of one
    // is the beggining of the other: merge it.
    for (const auto &amp;outline : outlines)
    {
        if (std::find_if(result.begin(), result.end(), [&amp;b = outline](line &amp;a)
        {
            bool result{};
            if ((result = (a.e == b.b) &amp;&amp; ((a.b.x * (b.b.y - b.e.y)) + (b.b.x * (b.e.y - a.b.y)) + (b.e.x * (a.b.y - b.b.y)) == 0)))
                a.e = b.e;
            return result;

        }) == result.end())
        {
            result.push_back(outline);
        }
    }

    return result;
}


Code Snippet available here, I have the feeling that it have lots of room for improvement.



1cell is more complex, but the additional complexity is out of the scope right now, so I'll keep things simple.
Your code makes remarkably good usage of modern C++ idioms. Bravo!

The only improvement that jumps out to me is the signature of vertex_of. By reading its definition, you can deduce that it returns a std::vector&lt;line&gt;, but ideally this should be documented in the declaration itself. I'd advice changing the signature to either

std::vector&lt;line&gt; vertex_of(const container_t&lt;cell&gt; &amp;cells)


or

auto vertex_of(const container_t&lt;cell&gt; &amp;cells) -&gt; std::vector&lt;line&gt;


depending on the stlye you prefer.