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