diff --git a/src/percolation/flood_fill.cpp b/src/percolation/flood_fill.cpp index e1e4be2..83925d1 100644 --- a/src/percolation/flood_fill.cpp +++ b/src/percolation/flood_fill.cpp @@ -1,100 +1,103 @@ /** * @file * * @author Lucas Frérot * * @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 . * */ /* -------------------------------------------------------------------------- */ #include "flood_fill.hh" #include /* -------------------------------------------------------------------------- */ __BEGIN_TAMAAS__ Cluster::Cluster(const Cluster& other) : points(other.points), area(other.area) {} Cluster::Cluster(Point start, const Grid& contact, Grid& visited, bool diagonal) : area(0) { // Visiting stack std::stack 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 neighbors; + std::vector neighbors; + neighbors.reserve(8); // space for max 8 neighbors, avoid multiple reserves + + // Pushing 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); } } } } std::list FloodFill::getClusters(const Grid& contact, bool diagonal) { auto n = contact.sizes(); Grid visited(n, 1); visited = false; std::list 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__