1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // This file was modified by Oracle on 2014.
6 // Modifications copyright (c) 2014 Oracle and/or its affiliates.
7 
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9 
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
13 
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
16 
17 
18 #include <boost/range/metafunctions.hpp>
19 
20 #include <boost/geometry/core/is_areal.hpp>
21 #include <boost/geometry/core/point_order.hpp>
22 #include <boost/geometry/core/reverse_dispatch.hpp>
23 #include <boost/geometry/geometries/concepts/check.hpp>
24 #include <boost/geometry/algorithms/not_implemented.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
26 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
27 
28 #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
30 
31 
32 namespace boost { namespace geometry
33 {
34 
35 #ifndef DOXYGEN_NO_DISPATCH
36 namespace dispatch
37 {
38 
39 template
40 <
41     typename Geometry1, typename Geometry2, typename GeometryOut,
42     typename TagIn1 = typename tag<Geometry1>::type,
43     typename TagIn2 = typename tag<Geometry2>::type,
44     typename TagOut = typename tag<GeometryOut>::type,
45     bool Areal1 = geometry::is_areal<Geometry1>::value,
46     bool Areal2 = geometry::is_areal<Geometry2>::value,
47     bool ArealOut = geometry::is_areal<GeometryOut>::value,
48     bool Reverse1 = detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
49     bool Reverse2 = detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
50     bool ReverseOut = detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
51     bool Reverse = geometry::reverse_dispatch<Geometry1, Geometry2>::type::value
52 >
53 struct union_insert: not_implemented<TagIn1, TagIn2, TagOut>
54 {};
55 
56 
57 // If reversal is needed, perform it first
58 
59 template
60 <
61     typename Geometry1, typename Geometry2, typename GeometryOut,
62     typename TagIn1, typename TagIn2, typename TagOut,
63     bool Areal1, bool Areal2, bool ArealOut,
64     bool Reverse1, bool Reverse2, bool ReverseOut
65 >
66 struct union_insert
67     <
68         Geometry1, Geometry2, GeometryOut,
69         TagIn1, TagIn2, TagOut,
70         Areal1, Areal2, ArealOut,
71         Reverse1, Reverse2, ReverseOut,
72         true
73     >: union_insert<Geometry2, Geometry1, GeometryOut>
74 {
75     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::dispatch::union_insert76     static inline OutputIterator apply(Geometry1 const& g1,
77             Geometry2 const& g2,
78             RobustPolicy const& robust_policy,
79             OutputIterator out,
80             Strategy const& strategy)
81     {
82         return union_insert
83             <
84                 Geometry2, Geometry1, GeometryOut
85             >::apply(g2, g1, robust_policy, out, strategy);
86     }
87 };
88 
89 
90 template
91 <
92     typename Geometry1, typename Geometry2, typename GeometryOut,
93     typename TagIn1, typename TagIn2, typename TagOut,
94     bool Reverse1, bool Reverse2, bool ReverseOut
95 >
96 struct union_insert
97     <
98         Geometry1, Geometry2, GeometryOut,
99         TagIn1, TagIn2, TagOut,
100         true, true, true,
101         Reverse1, Reverse2, ReverseOut,
102         false
103     > : detail::overlay::overlay
104         <Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, GeometryOut, overlay_union>
105 {};
106 
107 
108 // dispatch for union of non-areal geometries
109 template
110 <
111     typename Geometry1, typename Geometry2, typename GeometryOut,
112     typename TagIn1, typename TagIn2, typename TagOut,
113     bool Reverse1, bool Reverse2, bool ReverseOut
114 >
115 struct union_insert
116     <
117         Geometry1, Geometry2, GeometryOut,
118         TagIn1, TagIn2, TagOut,
119         false, false, false,
120         Reverse1, Reverse2, ReverseOut,
121         false
122     > : union_insert
123         <
124             Geometry1, Geometry2, GeometryOut,
125             typename tag_cast<TagIn1, pointlike_tag, linear_tag>::type,
126             typename tag_cast<TagIn2, pointlike_tag, linear_tag>::type,
127             TagOut,
128             false, false, false,
129             Reverse1, Reverse2, ReverseOut,
130             false
131         >
132 {};
133 
134 
135 // dispatch for union of linear geometries
136 template
137 <
138     typename Linear1, typename Linear2, typename LineStringOut,
139     bool Reverse1, bool Reverse2, bool ReverseOut
140 >
141 struct union_insert
142     <
143         Linear1, Linear2, LineStringOut,
144         linear_tag, linear_tag, linestring_tag,
145         false, false, false,
146         Reverse1, Reverse2, ReverseOut,
147         false
148     > : detail::overlay::linear_linear_linestring
149         <
150             Linear1, Linear2, LineStringOut, overlay_union
151         >
152 {};
153 
154 
155 // dispatch for point-like geometries
156 template
157 <
158     typename PointLike1, typename PointLike2, typename PointOut,
159     bool Reverse1, bool Reverse2, bool ReverseOut
160 >
161 struct union_insert
162     <
163         PointLike1, PointLike2, PointOut,
164         pointlike_tag, pointlike_tag, point_tag,
165         false, false, false,
166         Reverse1, Reverse2, ReverseOut,
167         false
168     > : detail::overlay::union_pointlike_pointlike_point
169         <
170             PointLike1, PointLike2, PointOut
171         >
172 {};
173 
174 
175 } // namespace dispatch
176 #endif // DOXYGEN_NO_DISPATCH
177 
178 #ifndef DOXYGEN_NO_DETAIL
179 namespace detail { namespace union_
180 {
181 
182 /*!
183 \brief_calc2{union}
184 \ingroup union
185 \details \details_calc2{union_insert, spatial set theoretic union}.
186     \details_insert{union}
187 \tparam GeometryOut output geometry type, must be specified
188 \tparam Geometry1 \tparam_geometry
189 \tparam Geometry2 \tparam_geometry
190 \tparam OutputIterator output iterator
191 \param geometry1 \param_geometry
192 \param geometry2 \param_geometry
193 \param out \param_out{union}
194 \return \return_out
195 */
196 template
197 <
198     typename GeometryOut,
199     typename Geometry1,
200     typename Geometry2,
201     typename OutputIterator
202 >
union_insert(Geometry1 const & geometry1,Geometry2 const & geometry2,OutputIterator out)203 inline OutputIterator union_insert(Geometry1 const& geometry1,
204             Geometry2 const& geometry2,
205             OutputIterator out)
206 {
207     concept::check<Geometry1 const>();
208     concept::check<Geometry2 const>();
209     concept::check<GeometryOut>();
210 
211     typedef typename geometry::rescale_overlay_policy_type
212         <
213             Geometry1,
214             Geometry2
215         >::type rescale_policy_type;
216 
217     typedef strategy_intersection
218         <
219             typename cs_tag<GeometryOut>::type,
220             Geometry1,
221             Geometry2,
222             typename geometry::point_type<GeometryOut>::type,
223             rescale_policy_type
224         > strategy;
225 
226     rescale_policy_type robust_policy
227             = geometry::get_rescale_policy<rescale_policy_type>(geometry1, geometry2);
228 
229     return dispatch::union_insert
230            <
231                Geometry1, Geometry2, GeometryOut
232            >::apply(geometry1, geometry2, robust_policy, out, strategy());
233 }
234 
235 
236 }} // namespace detail::union_
237 #endif // DOXYGEN_NO_DETAIL
238 
239 
240 
241 
242 /*!
243 \brief Combines two geometries which each other
244 \ingroup union
245 \details \details_calc2{union, spatial set theoretic union}.
246 \tparam Geometry1 \tparam_geometry
247 \tparam Geometry2 \tparam_geometry
248 \tparam Collection output collection, either a multi-geometry,
249     or a std::vector<Geometry> / std::deque<Geometry> etc
250 \param geometry1 \param_geometry
251 \param geometry2 \param_geometry
252 \param output_collection the output collection
253 \note Called union_ because union is a reserved word.
254 
255 \qbk{[include reference/algorithms/union.qbk]}
256 */
257 template
258 <
259     typename Geometry1,
260     typename Geometry2,
261     typename Collection
262 >
union_(Geometry1 const & geometry1,Geometry2 const & geometry2,Collection & output_collection)263 inline void union_(Geometry1 const& geometry1,
264             Geometry2 const& geometry2,
265             Collection& output_collection)
266 {
267     concept::check<Geometry1 const>();
268     concept::check<Geometry2 const>();
269 
270     typedef typename boost::range_value<Collection>::type geometry_out;
271     concept::check<geometry_out>();
272 
273     detail::union_::union_insert<geometry_out>(geometry1, geometry2,
274                 std::back_inserter(output_collection));
275 }
276 
277 
278 }} // namespace boost::geometry
279 
280 
281 #endif // BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
282