diff --git a/src/percolation/flood_fill.cpp b/src/percolation/flood_fill.cpp index 69781ee..c4507b4 100644 --- a/src/percolation/flood_fill.cpp +++ b/src/percolation/flood_fill.cpp @@ -1,271 +1,270 @@ /* * SPDX-License-Indentifier: AGPL-3.0-or-later * * Copyright (©) 2016-2022 EPFL (École Polytechnique Fédérale de Lausanne), * Laboratory (LSMS - Laboratoire de Simulation en Mécanique des Solides) * Copyright (©) 2020-2022 Lucas Frérot * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU Affero General Public License as published * by the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * This program 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 Affero General Public License for more details. * * You should have received a copy of the GNU Affero General Public License * along with this program. If not, see . * */ /* -------------------------------------------------------------------------- */ #include "flood_fill.hh" #include "partitioner.hh" #include #include -#include +#include /* -------------------------------------------------------------------------- */ namespace tamaas { -Int wrap_pbc(Int i, Int n) { - if (i < 0) - return i + n; - if (i >= n) - return i - n; - return i; -} +// Both i and n should be signed, otherwise weird things happen +Int wrap_pbc(Int i, Int n) { return ((i % n) + n) % n; } template std::array wrap_pbc(const std::array& t, const std::array& n) { std::array index; for (UInt i = 0; i < dim; ++i) index[i] = static_cast(wrap_pbc(t[i], n[i])); return index; } template std::array cast_int(const std::array& a) { std::array r; for (UInt i = 0; i < dim; ++i) r[i] = static_cast(a[i]); return r; } template Cluster::Cluster(const Cluster& other) : points(other.points), perimeter(other.perimeter) {} template <> auto Cluster<1>::getNextNeighbors(const std::array& p) { std::vector neighbors(2); Int i = p[0]; neighbors[0] = {i - 1}; neighbors[1] = {i + 1}; return neighbors; } template <> auto Cluster<1>::getDiagonalNeighbors(const std::array& /*p*/) { return std::vector(); } template <> auto Cluster<2>::getNextNeighbors(const std::array& p) { std::vector neighbors(4); Int i = p[0], j = p[1]; neighbors[0] = {i + 1, j}; neighbors[1] = {i - 1, j}; neighbors[2] = {i, j - 1}; neighbors[3] = {i, j + 1}; return neighbors; } template <> auto Cluster<2>::getDiagonalNeighbors(const std::array& p) { std::vector neighbors(4); Int i = p[0], j = p[1]; neighbors[0] = {i + 1, j + 1}; neighbors[1] = {i - 1, j - 1}; neighbors[2] = {i - 1, j + 1}; neighbors[3] = {i + 1, j - 1}; return neighbors; } template <> auto Cluster<3>::getNextNeighbors(const std::array& p) { std::vector neighbors(6); Int i = p[0], j = p[1], k = p[2]; neighbors[0] = {i + 1, j, k}; neighbors[1] = {i - 1, j, k}; neighbors[2] = {i, j - 1, k}; neighbors[3] = {i, j + 1, k}; neighbors[4] = {i, j, k - 1}; neighbors[5] = {i, j, k + 1}; return neighbors; } template <> auto Cluster<3>::getDiagonalNeighbors(const std::array& p) { std::vector neighbors(20); Int i = p[0], j = p[1], k = p[2]; // 8 corners neighbors[0] = {i + 1, j + 1, k + 1}; neighbors[1] = {i + 1, j + 1, k - 1}; neighbors[2] = {i + 1, j - 1, k + 1}; neighbors[3] = {i + 1, j - 1, k - 1}; neighbors[4] = {i - 1, j + 1, k + 1}; neighbors[5] = {i - 1, j + 1, k - 1}; neighbors[6] = {i - 1, j - 1, k + 1}; neighbors[7] = {i - 1, j - 1, k - 1}; // 4 diagonals in i = 0 neighbors[8] = {i, j + 1, k + 1}; neighbors[9] = {i, j + 1, k - 1}; neighbors[10] = {i, j - 1, k + 1}; neighbors[11] = {i, j - 1, k - 1}; // 4 diagonals in j = 0 neighbors[12] = {i + 1, j, k + 1}; neighbors[13] = {i + 1, j, k - 1}; neighbors[14] = {i - 1, j, k + 1}; neighbors[15] = {i - 1, j, k - 1}; // 4 diagonals in k = 0 neighbors[16] = {i + 1, j + 1, k}; neighbors[17] = {i + 1, j - 1, k}; neighbors[18] = {i - 1, j + 1, k}; neighbors[19] = {i - 1, j - 1, k}; return neighbors; } template typename Cluster::BBox Cluster::boundingBox() const { std::array mins, maxs; mins.fill(std::numeric_limits::max()); maxs.fill(std::numeric_limits::min()); for (const auto& p : points) for (UInt i = 0; i < dim; ++i) { mins[i] = std::min(mins[i], p[i]); maxs[i] = std::max(maxs[i], p[i]); } return std::make_pair(mins, maxs); } template std::array Cluster::extent() const { const auto bb = boundingBox(); std::array extent; std::transform(bb.first.begin(), bb.first.end(), bb.second.begin(), extent.begin(), [](auto min, auto max) { return max - min + 1; }); return extent; } template Cluster::Cluster(Point start, const Grid& map, Grid& visited, bool diagonal) { - // Visiting stack - std::stack> visiting; + // Visiting queue: a queue here prioritizes visiting local neighbors + // instead of growing a stack with each new visited point it gets rid of older + // neighbors first this prevents the points positions to be shifted + // indefinitely across periodic boundaries + std::queue visiting; visiting.push(start); + // Contact sizes const auto& n = cast_int(map.sizes()); while (not visiting.empty()) { - auto p = visiting.top(); + auto p = visiting.front(); auto p_wrapped = wrap_pbc(p, n); if (visited(p_wrapped)) { visiting.pop(); continue; } visited(p_wrapped) = true; - points.push_back(visiting.top()); + points.push_back(visiting.front()); visiting.pop(); auto process = [&](const std::vector& neighbors, const bool do_perimeter) { for (const auto& p : neighbors) { const auto index = wrap_pbc(p, n); if (not visited(index) and map(index)) { visiting.push(p); } perimeter += do_perimeter and (not map(index)); } }; process(getNextNeighbors(p), true); if (diagonal) { process(getDiagonalNeighbors(p), false); } } } typename FloodFill::List<1> FloodFill::getSegments(const Grid& map) { auto n = map.sizes(); Grid visited(n, 1); visited = false; List<1> clusters; for (UInt i = 0; i < n[0]; ++i) { if (map(i) && !visited(i)) { clusters.emplace_back(std::array{(Int)i}, map, visited, false); } } return clusters; } typename FloodFill::List<2> FloodFill::getClusters(const Grid& map, bool diagonal) { auto global_contact = Partitioner<2>::gather(map); auto n = global_contact.sizes(); Grid visited(n, 1); visited = false; List<2> clusters; if (mpi::rank() == 0) for (UInt i = 0; i < n[0]; ++i) { for (UInt j = 0; j < n[1]; ++j) { if (global_contact(i, j) && !visited(i, j)) { clusters.emplace_back(std::array{(Int)i, (Int)j}, global_contact, visited, diagonal); } } } return clusters; } typename FloodFill::List<3> FloodFill::getVolumes(const Grid& map, bool diagonal) { auto n = map.sizes(); Grid visited(n, 1); visited = false; List<3> clusters; for (UInt i = 0; i < n[0]; ++i) { for (UInt j = 0; j < n[1]; ++j) { for (UInt k = 0; k < n[2]; ++k) { if (map(i, j, k) && !visited(i, j, k)) { clusters.emplace_back(std::array{(Int)i, (Int)j, (Int)k}, map, visited, diagonal); } } } } return clusters; } template class Cluster<1>; template class Cluster<2>; template class Cluster<3>; } // namespace tamaas diff --git a/tests/test_flood_fill.py b/tests/test_flood_fill.py index 2fe8547..7173033 100644 --- a/tests/test_flood_fill.py +++ b/tests/test_flood_fill.py @@ -1,101 +1,104 @@ # -*- coding: utf-8 -*- # # Copyright (©) 2016-2022 EPFL (École Polytechnique Fédérale de Lausanne), # Laboratory (LSMS - Laboratoire de Simulation en Mécanique des Solides) # Copyright (©) 2020-2022 Lucas Frérot # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU Affero General Public License as published # by the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # # This program 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 Affero General Public License for more details. # # You should have received a copy of the GNU Affero General Public License # along with this program. If not, see . from __future__ import print_function, division import tamaas as tm import numpy as np def test_flood_fill2d(): field = np.zeros((18, 18), np.bool) # Cluster of permeter 18 area 13 field[2:4, 3:6] = True field[4, 4:6] = True # noqa field[5, 5] = True # noqa field[3:5, 6:8] = True # noqa # Cluster of perimeter 8 area 4 field[14:16, 3:5] = True # Cluster of perimeter 20 area 11 field[9:11, 8:11] = True # noqa field[7:9, 9] = True # noqa field[10, 11:14] = True # noqa # Cluster of perimeter 18 area 9 field[3:5, 14:16] = True field[5:10, 15] = True # Cluster spanning periodic boundary field[0:3, 12:14] = True field[-2:, 12:14] = True # Percolating cluster field[12, :] = True if False: # Show contact map import matplotlib.pyplot as plt plt.imshow(field, interpolation='none', cmap='gray_r', origin='lower') plt.xlim(0, 17) plt.ylim(0, 17) plt.show() clusters = tm.FloodFill.getClusters(field, False) # Dummy class for clusters class dummy: def __init__(self, area, perimeter, extent=None): self.area = area self.perimeter = perimeter self.extent = extent # Solution ref = [ dummy(10, 14, [5, 2]), # cluster spanning pbc dummy(13, 18), dummy(9, 18), dummy(11, 20), dummy(18, 36, [1, 18]), # percolating cluster dummy(4, 8) ] assert len(ref) == len(clusters) for x, y in zip(clusters, ref): assert x.area == y.area assert x.perimeter == y.perimeter if y.extent is not None: assert x.extent == y.extent - print(clusters[0].extent, clusters[4].extent) + field[:] = True + field[2:4, 2:4] = False + clusters = tm.FloodFill.getClusters(field, False) + assert clusters[0].extent == [18, 18] def test_flood_fill3d(): field = np.zeros((5, 5, 5), np.bool) field[2:4, 3, 1:3] = True clusters = tm.FloodFill.getVolumes(field, False) assert len(clusters) == 1 assert clusters[0].area == 4