1 #pragma once 2 #ifndef CATA_SRC_FLOOD_FILL_H 3 #define CATA_SRC_FLOOD_FILL_H 4 5 #include <queue> 6 #include <vector> 7 #include <unordered_set> 8 9 #include "enums.h" 10 #include "point.h" 11 12 namespace ff 13 { 14 /** 15 * Given a starting point, flood fill out to the 4-connected points, applying the provided predicate 16 * to determine if a given point should be added to the collection of flood-filled points, and then 17 * return that collection. 18 * @param starting_point starting point of the flood fill. No assumptions made about if it will satisfy 19 * the predicate. 20 * @param visited externally provided set of points that have already been designated as visited which 21 * will be updated by this call. 22 * @param predicate UnaryPredicate that will be provided with a point for evaluation as to whether or 23 * not the point should be filled. 24 */ 25 template<typename Point, typename UnaryPredicate> point_flood_fill_4_connected(const Point & starting_point,std::unordered_set<Point> & visited,UnaryPredicate predicate)26std::vector<Point> point_flood_fill_4_connected( const Point &starting_point, 27 std::unordered_set<Point> &visited, UnaryPredicate predicate ) 28 { 29 std::vector<Point> filled_points; 30 std::queue<Point> to_check; 31 to_check.push( starting_point ); 32 while( !to_check.empty() ) { 33 const Point current_point = to_check.front(); 34 to_check.pop(); 35 36 if( visited.find( current_point ) != visited.end() ) { 37 continue; 38 } 39 40 visited.emplace( current_point ); 41 42 if( predicate( current_point ) ) { 43 filled_points.emplace_back( current_point ); 44 to_check.push( current_point + point_south ); 45 to_check.push( current_point + point_north ); 46 to_check.push( current_point + point_east ); 47 to_check.push( current_point + point_west ); 48 } 49 } 50 51 return filled_points; 52 } 53 } // namespace ff 54 55 #endif // CATA_SRC_FLOOD_FILL_H 56