Homec4science
Diffusion tamaas (features/netcdf-mpi) Browse

tamaas/src/percolation/flood_fill.cpp
257c769ec25dfeatures/netcdf-mpi

Last Change
Raw File

flood_fill.cpp
View Options

/**
* @file
*
* @author Lucas Frérot <lucas.frerot@epfl.ch>
*
* @section LICENSE
*
* Copyright (©) 2016 EPFL (Ecole Polytechnique Fédérale de
* Lausanne) Laboratory (LSMS - Laboratoire de Simulation en Mécanique des
* Solides)
*
* Tamaas is free software: you can redistribute it and/or modify it under the
* terms of the GNU Lesser General Public License as published by the Free
* Software Foundation, either version 3 of the License, or (at your option) any
* later version.
*
* Tamaas is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
* A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
* details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with Tamaas. If not, see <http://www.gnu.org/licenses/>.
*
*/
/* -------------------------------------------------------------------------- */
#include "flood_fill.hh"
#include <stack>
/* -------------------------------------------------------------------------- */
__BEGIN_TAMAAS__
Int unsigned_modulo(Int i, UInt n) {
return (i % n + n) % n;
}
Cluster::Cluster(const Cluster& other)
: points(other.points), perimeter(other.perimeter) {}
Cluster::Cluster(Point start, const Grid<bool, 2>& contact,
Grid<bool, 2>& visited, bool diagonal) {
// Visiting stack
std::stack<Point, std::vector<Point>> visiting;
visiting.push(start);
// Contact sizes
const auto& n = contact.sizes();
while (!visiting.empty()) {
Int i = visiting.top().first;
Int j = visiting.top().second;
if (visited(i, j)) {
visiting.pop();
continue;
}
visited(i, j) = true;
points.push_back(visiting.top());
visiting.pop();
std::vector<Point> neighbors;
neighbors.reserve(4); // space for max 4 neighbors, avoid multiple reserves
// Pushing neighbors
neighbors.emplace_back(i + 1, j);
neighbors.emplace_back(i - 1, j);
neighbors.emplace_back(i, j - 1);
neighbors.emplace_back(i, j + 1);
auto process = [&](const std::vector<Point>& neighbors, bool do_perimeter) {
for (auto& p : neighbors) {
Int im = unsigned_modulo(p.first, n[0]);
Int jm = unsigned_modulo(p.second, n[1]);
if (!visited(im, jm) and contact(im, jm)) {
visiting.push(Point{im, jm});
}
if (do_perimeter and (not contact(im, jm)))
++perimeter;
}
};
process(neighbors, true);
if (diagonal) {
neighbors[0] = std::make_pair(i + 1, j + 1);
neighbors[1] = std::make_pair(i - 1, j - 1);
neighbors[2] = std::make_pair(i - 1, j + 1);
neighbors[3] = std::make_pair(i + 1, j - 1);
process(neighbors, false);
}
}
}
std::list<Cluster> FloodFill::getClusters(const Grid<bool, 2>& contact,
bool diagonal) {
auto n = contact.sizes();
Grid<bool, 2> visited(n, 1);
visited = false;
std::list<Cluster> clusters;
for (UInt i = 0; i < n[0]; ++i) {
for (UInt j = 0; j < n[1]; ++j) {
if (contact(i, j) && !visited(i, j)) {
clusters.emplace_back(std::make_pair(i, j), contact, visited, diagonal);
}
}
}
return clusters;
}
__END_TAMAAS__
c4science · Help