Find outlines of a tile collection

Question

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 cell¹ objects:

struct point { int x{}, y{}; };
struct line { point b{}, e{}; };
struct cell
{
    int x{}, y{};
    std::array<line, 4> 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:

1. Transform cells to lines.
2. Save lines into container, if the line is already on that container: delete it (this Will get rid of lines inside shapes).
3. 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 <template <typename> typename container_t>
auto vertex_of(const container_t<cell> &cells)
{
    std::set<line> outlines;

    for (const auto &cell : cells)
        // Transform cells to lines
        for (const auto &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<line> 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 &outline : outlines)
    {
        if (std::find_if(result.begin(), result.end(), [&b = outline](line &a)
        {
            bool result{};
            if ((result = (a.e == b.b) && ((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.

---

¹cell is more complex, but the additional complexity is out of the scope right now, so I'll keep things simple.

Answer 1

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<line>, but ideally this should be documented in the declaration itself. I'd advice changing the signature to either

std::vector<line> vertex_of(const container_t<cell> &cells)

or

auto vertex_of(const container_t<cell> &cells) -> std::vector<line>

depending on the stlye you prefer.

Answer 2

It seems that the order of elements in outlines is not important, so it could also be of type std::unordered_set<line>. Of course, we'd then have to give it a suitable hash function, but that's easy to do.

Another consideration: for the 2nd loop of vertex_of, we are essentially interested in the question "given a line, is there another line whose end matches the beginning of the first?". For this, we could set up a data structure that orders lines based on their beginning. By doing that, we could do away with much less work than your current quadratic solution.

Answer 3

if (std::find_if(result.begin(), result.end(), [&b = outline](line &a)
        {
            bool result{};
            if ((result = (a.e == b.b) && ((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())

You're modifying the contents of the result collection within a find_if predicate. It might work, but it's very unintuitive and should be just as easy to modify the value outside the predicate.

---

You have a point data structure you don't seem to be using.

---

int x{}, y{};

In my opinion, don't zero initialize these, as it's not adding anything of value, even semantically. There's no reason a default initialized point needs to be assumed to be 0, especially when it could be zero initialized itself.

---

bool result{};
if ((result = (a.e == b.b) && ((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;

This needs to be cleaned up. Declaring the result like that is unnecessary. Ideally the code should be understandable with a minimal amount of surrounding context. These are not appropriate names for variables.

---

The lines method is tightly coupling lines to your cell data structure. I recommend removing it, and keeping the cell data structure as plain data with no methods.

---

If you are guaranteed that the grid is always 8x8 (due to your design), then it's fine to store an array of bools. It's the size of 8 doubles. You presently use more memory if your grid is over 12.5% full since each cell is 8 bytes. The advantage of a sparse data structure is if you have a huge grid with significantly fewer entries.

---

If you're bound to using a sparse representation, you can store it more coherently such that the outlines can be extracted more conveniently. It seems very much like a connected components problem. For example, if you had a huge grid, you could represent occupied cells with a std::unordered_map<CellColumnIndexType, std::unordered_set<CellRowIndexType>>

This has nearly no superfluous memory overhead with constant time searching. Note that this will perform significantly slower on small grid sizes (e.g. 8x8).