algorithms/detail/gc_group_elements.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2022, Oracle and/or its affiliates.
0004 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0005
0006 // Licensed under the Boost Software License version 1.0.
0007 // http://www.boost.org/users/license.html
0008
0009 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_GC_GROUP_ELEMENTS_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_GC_GROUP_ELEMENTS_HPP
0011
0012
0013 #include <array>
0014 #include <deque>
0015 #include <map>
0016 #include <set>
0017 #include <vector>
0018
0019 #include <boost/range/begin.hpp>
0020 #include <boost/range/size.hpp>
0021
0022 #include <boost/geometry/algorithms/detail/gc_make_rtree.hpp>
0023 #include <boost/geometry/algorithms/detail/visit.hpp>
0024 #include <boost/geometry/algorithms/is_empty.hpp>
0025 #include <boost/geometry/core/topological_dimension.hpp>
0026 #include <boost/geometry/views/detail/random_access_view.hpp>
0027
0028
0029
0030 namespace boost { namespace geometry
0031 {
0032
0033
0034 #ifndef DOXYGEN_NO_DETAIL
0035 namespace detail
0036 {
0037
0038
0039 struct gc_element_id
0040 {
0041     gc_element_id(unsigned int source_id_, std::size_t gc_id_)
0042         : source_id(source_id_), gc_id(gc_id_)
0043     {}
0044
0045     unsigned int source_id;
0046     std::size_t gc_id;
0047
0048     friend bool operator<(gc_element_id const& left, gc_element_id const& right)
0049     {
0050         return left.source_id < right.source_id
0051             || (left.source_id == right.source_id && left.gc_id < right.gc_id);
0052     }
0053 };
0054
0055 template <typename GC1View, typename GC2View, typename Strategy, typename IntersectingFun, typename DisjointFun>
0056 inline void gc_group_elements(GC1View const& gc1_view, GC2View const& gc2_view, Strategy const& strategy,
0057                               IntersectingFun&& intersecting_fun,
0058                               DisjointFun&& disjoint_fun,
0059                               bool const group_self = false)
0060 {
0061     // NOTE: gc_make_rtree_indexes() already checks for random-access,
0062     //   non-recursive geometry collections.
0063
0064     // NOTE: could be replaced with unordered_map and unordered_set
0065     std::map<gc_element_id, std::set<gc_element_id>> adjacent;
0066
0067     // Create adjacency list based on intersecting envelopes of GC elements
0068     auto const rtree2 = gc_make_rtree_indexes(gc2_view, strategy);
0069     if (! group_self) // group only elements from the other GC?
0070     {
0071         for (std::size_t i = 0; i < boost::size(gc1_view); ++i)
0072         {
0073             traits::iter_visit<GC1View>::apply([&](auto const& g1)
0074             {
0075                 using g1_t = util::remove_cref_t<decltype(g1)>;
0076                 using box1_t = gc_make_rtree_box_t<g1_t>;
0077                 box1_t b1 = geometry::return_envelope<box1_t>(g1, strategy);
0078                 detail::expand_by_epsilon(b1);
0079
0080                 gc_element_id id1 = {0, i};
0081                 for (auto qit = rtree2.qbegin(index::intersects(b1)); qit != rtree2.qend(); ++qit)
0082                 {
0083                     gc_element_id id2 = {1, qit->second};
0084                     adjacent[id1].insert(id2);
0085                     adjacent[id2].insert(id1);
0086                 }
0087             }, boost::begin(gc1_view) + i);
0088         }
0089     }
0090     else // group elements from the same GCs and the other GC
0091     {
0092         auto const rtree1 = gc_make_rtree_indexes(gc1_view, strategy);
0093         for (auto it1 = rtree1.begin() ; it1 != rtree1.end() ; ++it1)
0094         {
0095             auto const b1 = it1->first;
0096             gc_element_id id1 = {0, it1->second};
0097             for (auto qit2 = rtree2.qbegin(index::intersects(b1)); qit2 != rtree2.qend(); ++qit2)
0098             {
0099                 gc_element_id id2 = {1, qit2->second};
0100                 adjacent[id1].insert(id2);
0101                 adjacent[id2].insert(id1);
0102             }
0103             for (auto qit1 = rtree1.qbegin(index::intersects(b1)); qit1 != rtree1.qend(); ++qit1)
0104             {
0105                 if (id1.gc_id != qit1->second)
0106                 {
0107                     gc_element_id id11 = {0, qit1->second};
0108                     adjacent[id1].insert(id11);
0109                     adjacent[id11].insert(id1);
0110                 }
0111             }
0112         }
0113         for (auto it2 = rtree2.begin(); it2 != rtree2.end(); ++it2)
0114         {
0115             auto const b2 = it2->first;
0116             gc_element_id id2 = {1, it2->second};
0117             for (auto qit2 = rtree2.qbegin(index::intersects(b2)); qit2 != rtree2.qend(); ++qit2)
0118             {
0119                 if (id2.gc_id != qit2->second)
0120                 {
0121                     gc_element_id id22 = {1, qit2->second};
0122                     adjacent[id2].insert(id22);
0123                     adjacent[id22].insert(id2);
0124                 }
0125             }
0126         }
0127     }
0128
0129     // Traverse the graph and build connected groups i.e. groups of intersecting envelopes
0130     std::deque<gc_element_id> queue;
0131     std::array<std::vector<bool>, 2> visited = {
0132         std::vector<bool>(boost::size(gc1_view), false),
0133         std::vector<bool>(boost::size(gc2_view), false)
0134     };
0135     for (auto const& elem : adjacent)
0136     {
0137         std::vector<gc_element_id> group;
0138         if (! visited[elem.first.source_id][elem.first.gc_id])
0139         {
0140             queue.push_back(elem.first);
0141             visited[elem.first.source_id][elem.first.gc_id] = true;
0142             group.push_back(elem.first);
0143             while (! queue.empty())
0144             {
0145                 gc_element_id e = queue.front();
0146                 queue.pop_front();
0147                 for (auto const& n : adjacent[e])
0148                 {
0149                     if (! visited[n.source_id][n.gc_id])
0150                     {
0151                         queue.push_back(n);
0152                         visited[n.source_id][n.gc_id] = true;
0153                         group.push_back(n);
0154                     }
0155                 }
0156             }
0157         }
0158         if (! group.empty())
0159         {
0160             if (! intersecting_fun(group))
0161             {
0162                 return;
0163             }
0164         }
0165     }
0166
0167     {
0168         std::vector<gc_element_id> group;
0169         for (std::size_t i = 0; i < visited[0].size(); ++i)
0170         {
0171             if (! visited[0][i])
0172             {
0173                 group.emplace_back(0, i);
0174             }
0175         }
0176         for (std::size_t i = 0; i < visited[1].size(); ++i)
0177         {
0178             if (! visited[1][i])
0179             {
0180                 group.emplace_back(1, i);
0181             }
0182         }
0183         if (! group.empty())
0184         {
0185             disjoint_fun(group);
0186         }
0187     }
0188 }
0189
0190
0191 } // namespace detail
0192 #endif // DOXYGEN_NO_DETAIL
0193
0194 }} // namespace boost::geometry
0195
0196 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_GC_GROUP_ELEMENTS_HPP