FloodFill.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (C) 2018-2025 ISciences, LLC
*
* This is free software; you can redistribute and/or modify it under
* the terms of the GNU Lesser General Public Licence as published
* by the Free Software Foundation.
* See the COPYING file for more information.
*
**********************************************************************/
#pragma once
#include <geos/operation/grid/Grid.h>
#include <geos/operation/grid/Matrix.h>
#include <queue>
namespace geos::geom {
class Geometry;
}
namespace geos::algorithm::locate {
class PointOnGeometryLocator;
}
namespace geos::operation::grid {
template<typename T>
struct fill_values
{
static T EXTERIOR;
};
template<>
struct fill_values<float>
{
static constexpr float EXTERIOR{ 0.0f }; // Cell is known to be entirely outside the polygon
static constexpr float INTERIOR{ 1.0f }; // Cell is known to be entirely within the polygon
static constexpr float FILLABLE{ -1.0f }; // Cell location relative to polygon unknown, but
// can be determined by fill.
static constexpr float UNKNOWN{ -2.0f }; // Cell location relative to polygon unknown
// and cannot be determined from a flood fill
// (must be explicitly tested)
};
class FloodFill
{
public:
FloodFill(const geom::Geometry& g, const Grid<bounded_extent>& extent);
~FloodFill();
template<typename T>
void flood(Matrix<T>& arr) const;
bool cellIsInside(size_t i, size_t j) const;
private:
Grid<bounded_extent> m_extent;
const geom::Geometry& m_g;
std::unique_ptr<algorithm::locate::PointOnGeometryLocator> m_loc;
};
template<typename T>
void
floodFromPixel(Matrix<T>& arr, size_t i, size_t j, T fill_value)
{
std::queue<std::pair<size_t, size_t>> locations;
locations.emplace(i, j);
while (!locations.empty()) {
i = locations.front().first;
j = locations.front().second;
locations.pop();
if (arr(i, j) == fill_value) {
continue;
}
// Left
if (j > 0 && arr(i, j - 1) == fill_values<T>::FILLABLE) {
locations.emplace(i, j - 1);
}
auto j0 = j;
// Fill along this row until we hit something
for (; j < arr.getNumCols() && arr(i, j) == fill_values<T>::FILLABLE; j++) {
arr(i, j) = fill_value;
}
auto j1 = j;
// Initiate scanlines above our current row
if (i > 0) {
for (j = j0; j < j1; j++) {
// Up
if (arr(i - 1, j) == fill_values<T>::FILLABLE) {
locations.emplace(i - 1, j);
}
}
}
// Initiate scanlines below our current row
if (i < arr.getNumRows() - 1) {
for (j = j0; j < j1; j++) {
// Down
if (arr(i + 1, j) == fill_values<T>::FILLABLE) {
locations.emplace(i + 1, j);
}
}
}
}
}
template<typename T>
void
FloodFill::flood(Matrix<T>& arr) const
{
for (size_t i = 0; i < arr.getNumRows(); i++) {
for (size_t j = 0; j < arr.getNumCols(); j++) {
if (arr(i, j) == fill_values<T>::UNKNOWN) {
throw std::runtime_error("Cell with unknown position encountered.");
} else if (arr(i, j) == fill_values<T>::FILLABLE) {
// Cell position relative to polygon is unknown but can
// be determined from adjacent cells.
if (cellIsInside(i, j)) {
floodFromPixel(arr, i, j, fill_values<T>::INTERIOR);
} else {
floodFromPixel(arr, i, j, fill_values<T>::EXTERIOR);
}
}
}
}
}
}
geos::algorithm::locate::PointOnGeometryLocator
An interface for classes which determine the Location of points in Polygon or MultiPolygon geometries...
Definition PointOnGeometryLocator.h:36
geos::geom::Geometry
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition Geometry.h:196
geos::algorithm::locate
Classes which determine the Location of points in geometries.
Definition IndexedPointInAreaLocator.h:40
geos::geom
Definition Angle.h:26
geos::geom::Location::INTERIOR
@ INTERIOR
Definition Location.h:43