diff --git a/python/wrap/percolation.cpp b/python/wrap/percolation.cpp
index fd1aa79..cfff21c 100644
--- a/python/wrap/percolation.cpp
+++ b/python/wrap/percolation.cpp
@@ -1,93 +1,95 @@
/*
* 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 "wrap.hh"
/* -------------------------------------------------------------------------- */
#include
/* -------------------------------------------------------------------------- */
namespace tamaas {
namespace wrap {
/* -------------------------------------------------------------------------- */
using namespace py::literals;
/* -------------------------------------------------------------------------- */
template
void wrapCluster(py::module& mod) {
auto name = makeDimensionName("Cluster", dim);
py::class_>(mod, name.c_str())
.def(py::init<>())
.def_property_readonly("area", &Cluster::getArea, "Area of cluster")
.def_property_readonly("points", &Cluster::getPoints,
"Get list of points of cluster")
.def_property_readonly("perimeter", &Cluster::getPerimeter,
"Get perimeter of cluster")
.def_property_readonly("bounding_box", &Cluster::boundingBox,
"Compute the bounding box of a cluster")
+ .def_property_readonly("extent", &Cluster::extent,
+ "Compute the extents of a cluster")
.def(TAMAAS_DEPRECATE_ACCESSOR(getArea, Cluster, "area"))
.def(TAMAAS_DEPRECATE_ACCESSOR(getPoints, Cluster, "points"))
.def(TAMAAS_DEPRECATE_ACCESSOR(getPerimeter, Cluster, "perimeter"))
.def("__str__", [](const Cluster& cluster) {
std::stringstream sstr;
sstr << '{';
auto&& points = cluster.getPoints();
auto print_point = [&sstr](const auto& point) {
sstr << '(';
for (UInt i = 0; i < point.size() - 1; ++i)
sstr << point[i] << ", ";
sstr << point.back() << ')';
};
auto point_it = points.begin();
for (UInt p = 0; p < points.size() - 1; ++p) {
print_point(*(point_it++));
sstr << ", ";
}
print_point(points.back());
sstr << "}";
return sstr.str();
});
}
void wrapPercolation(py::module& mod) {
wrapCluster<1>(mod);
wrapCluster<2>(mod);
wrapCluster<3>(mod);
py::class_(mod, "FloodFill")
.def_static("getSegments", &FloodFill::getSegments,
"Return a list of segments from boolean map", "contact"_a)
.def_static("getClusters", &FloodFill::getClusters,
"Return a list of clusters from boolean map", "contact"_a,
"diagonal"_a)
.def_static("getVolumes", &FloodFill::getVolumes,
"Return a list of volume clusters", "map"_a, "diagonal"_a);
}
} // namespace wrap
} // namespace tamaas
diff --git a/src/percolation/flood_fill.cpp b/src/percolation/flood_fill.cpp
index 0228f05..69781ee 100644
--- a/src/percolation/flood_fill.cpp
+++ b/src/percolation/flood_fill.cpp
@@ -1,258 +1,271 @@
/*
* 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
/* -------------------------------------------------------------------------- */
namespace tamaas {
-Int unsigned_modulo(Int i, UInt n) { return (i % n + n) % n; }
+Int wrap_pbc(Int i, Int n) {
+ if (i < 0)
+ return i + n;
+ if (i >= n)
+ return i - n;
+ return i;
+}
template
-std::array unsigned_modulo(const std::array& t,
- const std::array& n) {
+std::array wrap_pbc(const std::array& t,
+ const std::array& n) {
std::array index;
for (UInt i = 0; i < dim; ++i)
- index[i] = unsigned_modulo(t[i], n[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] = (Int)a[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) {
+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*/) {
+auto Cluster<1>::getDiagonalNeighbors(const std::array& /*p*/) {
return std::vector();
}
template <>
-auto Cluster<2>::getNextNeighbors(const std::array& p) {
+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) {
+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) {
+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) {
+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
-std::pair, std::array>
-Cluster::boundingBox() const {
- // TODO make sure periodic boundaries are correctly unwrapped
+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.push(start);
// Contact sizes
- const auto& n = map.sizes();
+ const auto& n = cast_int(map.sizes());
while (not visiting.empty()) {
- auto p = unsigned_modulo(visiting.top(), n);
+ auto p = visiting.top();
+ auto p_wrapped = wrap_pbc(p, n);
- if (visited(p)) {
+ if (visited(p_wrapped)) {
visiting.pop();
continue;
}
- visited(p) = true;
+ visited(p_wrapped) = true;
points.push_back(visiting.top());
visiting.pop();
auto process = [&](const std::vector& neighbors,
const bool do_perimeter) {
- for (auto& p : neighbors) {
- auto index = unsigned_modulo(p, n);
+ for (const auto& p : neighbors) {
+ const auto index = wrap_pbc(p, n);
if (not visited(index) and map(index)) {
- visiting.push(cast_int(index));
+ visiting.push(p);
}
- if (do_perimeter and (not map(index)))
- ++perimeter;
+ perimeter += do_perimeter and (not map(index));
}
};
process(getNextNeighbors(p), true);
if (diagonal) {
process(getDiagonalNeighbors(p), false);
}
}
}
-std::list> FloodFill::getSegments(const Grid& map) {
+typename FloodFill::List<1> FloodFill::getSegments(const Grid& map) {
auto n = map.sizes();
Grid visited(n, 1);
visited = false;
- std::list> clusters;
+ 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);
+ clusters.emplace_back(std::array{(Int)i}, map, visited, false);
}
}
return clusters;
}
-std::list> FloodFill::getClusters(const Grid& map,
- bool diagonal) {
+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;
- std::list> clusters;
+ 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;
}
-std::list> FloodFill::getVolumes(const Grid& map,
- bool diagonal) {
+typename FloodFill::List<3> FloodFill::getVolumes(const Grid& map,
+ bool diagonal) {
auto n = map.sizes();
Grid visited(n, 1);
visited = false;
- std::list> clusters;
+ 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);
+ 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/src/percolation/flood_fill.hh b/src/percolation/flood_fill.hh
index c760b9d..a7a58c1 100644
--- a/src/percolation/flood_fill.hh
+++ b/src/percolation/flood_fill.hh
@@ -1,77 +1,85 @@
/*
* 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 .
*
*/
/* -------------------------------------------------------------------------- */
#ifndef FLOOD_FILL_H
#define FLOOD_FILL_H
/* -------------------------------------------------------------------------- */
#include "grid.hh"
#include
/* -------------------------------------------------------------------------- */
namespace tamaas {
/* -------------------------------------------------------------------------- */
template
class Cluster {
using Point = std::array;
+ using BBox = std::pair, std::array>;
public:
/// Constructor
Cluster(Point start, const Grid& map, Grid& visited,
bool diagonal);
/// Copy constructor
Cluster(const Cluster& other);
/// Default constructor
Cluster() = default;
/// Get area of cluster
UInt getArea() const { return getPoints().size(); }
/// Get perimeter of cluster
UInt getPerimeter() const { return perimeter; }
/// Get contact points
- const std::list& getPoints() const { return points; }
+ const auto& getPoints() const { return points; }
/// Get bounding box
- std::pair, std::array> boundingBox() const;
+ BBox boundingBox() const;
+ /// Get bounding box extent
+ std::array extent() const;
/// Assign next neighbors
- auto getNextNeighbors(const std::array& p);
+ auto getNextNeighbors(const std::array& p);
/// Assign diagonal neighbors
- auto getDiagonalNeighbors(const std::array& p);
+ auto getDiagonalNeighbors(const std::array& p);
private:
- std::list points;
+ /// List of points in the cluster
+ std::vector points;
+ /// Perimeter size (number of segments)
UInt perimeter = 0;
};
/* -------------------------------------------------------------------------- */
class FloodFill {
+ template
+ using List = std::vector>;
+
public:
- static std::list> getSegments(const Grid& map);
- /// Returns a list of clusters from a boolean contact map
- static std::list> getClusters(const Grid& map,
- bool diagonal);
- static std::list> getVolumes(const Grid& map,
- bool diagonal);
+ /// Return a list of connected segments
+ static List<1> getSegments(const Grid& map);
+ /// Return a list of connected areas
+ static List<2> getClusters(const Grid& map, bool diagonal);
+ /// Return a list of connected volumes
+ static List<3> getVolumes(const Grid& map, bool diagonal);
};
/* -------------------------------------------------------------------------- */
} // namespace tamaas
/* -------------------------------------------------------------------------- */
#endif // FLOOD_FILL_H
diff --git a/tests/test_flood_fill.py b/tests/test_flood_fill.py
index 37b2b60..2fe8547 100644
--- a/tests/test_flood_fill.py
+++ b/tests/test_flood_fill.py
@@ -1,70 +1,101 @@
# -*- 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[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
+ 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):
+
+ def __init__(self, area, perimeter, extent=None):
self.area = area
self.perimeter = perimeter
+ self.extent = extent
# Solution
- ref = [dummy(13, 18), dummy(9, 18), dummy(11, 20), dummy(4, 8)]
+ 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)
+
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