1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // Use, modification and distribution is subject to the Boost Software License,
6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP
11 
12 #include <boost/range.hpp>
13 
14 #include <boost/geometry/core/closure.hpp>
15 #include <boost/geometry/algorithms/area.hpp>
16 #include <boost/geometry/algorithms/detail/overlay/convert_ring.hpp>
17 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
18 
19 
20 namespace boost { namespace geometry
21 {
22 
23 
24 #ifndef DOXYGEN_NO_DETAIL
25 namespace detail { namespace overlay
26 {
27 
28 template
29 <
30     typename GeometryOut,
31     typename Geometry1,
32     typename Geometry2,
33     typename RingCollection
34 >
convert_and_add(GeometryOut & result,Geometry1 const & geometry1,Geometry2 const & geometry2,RingCollection const & collection,ring_identifier id,bool reversed,bool append)35 inline void convert_and_add(GeometryOut& result,
36             Geometry1 const& geometry1, Geometry2 const& geometry2,
37             RingCollection const& collection,
38             ring_identifier id,
39             bool reversed, bool append)
40 {
41     typedef typename geometry::tag<Geometry1>::type tag1;
42     typedef typename geometry::tag<Geometry2>::type tag2;
43     typedef typename geometry::tag<GeometryOut>::type tag_out;
44 
45     if (id.source_index == 0)
46     {
47         convert_ring<tag_out>::apply(result,
48                     get_ring<tag1>::apply(id, geometry1),
49                     append, reversed);
50     }
51     else if (id.source_index == 1)
52     {
53         convert_ring<tag_out>::apply(result,
54                     get_ring<tag2>::apply(id, geometry2),
55                     append, reversed);
56     }
57     else if (id.source_index == 2)
58     {
59         convert_ring<tag_out>::apply(result,
60                     get_ring<void>::apply(id, collection),
61                     append, reversed);
62     }
63 }
64 
65 template
66 <
67     typename GeometryOut,
68     typename SelectionMap,
69     typename Geometry1,
70     typename Geometry2,
71     typename RingCollection,
72     typename OutputIterator
73 >
add_rings(SelectionMap const & map,Geometry1 const & geometry1,Geometry2 const & geometry2,RingCollection const & collection,OutputIterator out)74 inline OutputIterator add_rings(SelectionMap const& map,
75             Geometry1 const& geometry1, Geometry2 const& geometry2,
76             RingCollection const& collection,
77             OutputIterator out)
78 {
79     typedef typename SelectionMap::const_iterator iterator;
80     typedef typename SelectionMap::mapped_type property_type;
81     typedef typename property_type::area_type area_type;
82 
83     area_type const zero = 0;
84     std::size_t const min_num_points = core_detail::closure::minimum_ring_size
85         <
86             geometry::closure
87                 <
88                     typename boost::range_value
89                         <
90                             RingCollection const
91                         >::type
92                 >::value
93         >::value;
94 
95 
96     for (iterator it = boost::begin(map);
97         it != boost::end(map);
98         ++it)
99     {
100         if (! it->second.discarded
101             && it->second.parent.source_index == -1)
102         {
103             GeometryOut result;
104             convert_and_add(result, geometry1, geometry2, collection,
105                     it->first, it->second.reversed, false);
106 
107             // Add children
108             for (typename std::vector<ring_identifier>::const_iterator child_it
109                         = it->second.children.begin();
110                 child_it != it->second.children.end();
111                 ++child_it)
112             {
113                 iterator mit = map.find(*child_it);
114                 if (mit != map.end()
115                     && ! mit->second.discarded)
116                 {
117                     convert_and_add(result, geometry1, geometry2, collection,
118                             *child_it, mit->second.reversed, true);
119                 }
120             }
121 
122             // Only add rings if they satisfy minimal requirements.
123             // This cannot be done earlier (during traversal), not
124             // everything is figured out yet (sum of positive/negative rings)
125             if (geometry::num_points(result) >= min_num_points
126                 && math::larger(geometry::area(result), zero))
127             {
128                 *out++ = result;
129             }
130         }
131     }
132     return out;
133 }
134 
135 
136 template
137 <
138     typename GeometryOut,
139     typename SelectionMap,
140     typename Geometry,
141     typename RingCollection,
142     typename OutputIterator
143 >
add_rings(SelectionMap const & map,Geometry const & geometry,RingCollection const & collection,OutputIterator out)144 inline OutputIterator add_rings(SelectionMap const& map,
145             Geometry const& geometry,
146             RingCollection const& collection,
147             OutputIterator out)
148 {
149     Geometry empty;
150     return add_rings<GeometryOut>(map, geometry, empty, collection, out);
151 }
152 
153 
154 }} // namespace detail::overlay
155 #endif // DOXYGEN_NO_DETAIL
156 
157 
158 }} // namespace geometry
159 
160 
161 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP
162