Page MenuHomec4science
Files F91606776

flood_fill.cpp
No OneTemporary
Actions

File Metadata

Created
Tue, Nov 12, 16:08

flood_fill.cpp
View Options

/**
*
* @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