Page MenuHomec4science
Files F61224921

flood_fill.cpp
No OneTemporary
Actions

File Metadata

Created
Sun, May 5, 08:06

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__
Cluster::Cluster(const Cluster& other)
: points(other.points), area(other.area) {}
Cluster::Cluster(Point start, const Grid<bool, 2>& contact,
Grid<bool, 2>& visited, bool diagonal)
: area(0) {
// Visiting stack
std::stack<Point> visiting;
visiting.push(start);
// Contact sizes
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());
area++;
visiting.pop();
std::list<Point> neighbors;
neighbors.push_back(std::make_pair(i + 1, j));
neighbors.push_back(std::make_pair(i - 1, j));
neighbors.push_back(std::make_pair(i, j - 1));
neighbors.push_back(std::make_pair(i, j + 1));
if (diagonal) {
neighbors.push_back(std::make_pair(i + 1, j + 1));
neighbors.push_back(std::make_pair(i - 1, j - 1));
neighbors.push_back(std::make_pair(i - 1, j + 1));
neighbors.push_back(std::make_pair(i + 1, j - 1));
}
for (auto& p : neighbors) {
Int im = p.first % n[0];
Int jm = p.second % n[1];
if (!visited(im, jm) && contact(im, jm)) {
visiting.push(p);
}
}
}
}
Cluster::~Cluster() {}
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.push_back(
Cluster(std::make_pair(i, j), contact, visited, diagonal));
}
}
}
return clusters;
}
__END_TAMAAS__

Event Timeline

c4science · Help