boost/geometry/algorithms/union.hpp

   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, 2017.
   6 // Modifications copyright (c) 2014-2017 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   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_UNION_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
  17
  18
  19 #include <boost/range/metafunctions.hpp>
  20
  21 #include <boost/geometry/core/is_areal.hpp>
  22 #include <boost/geometry/core/point_order.hpp>
  23 #include <boost/geometry/core/reverse_dispatch.hpp>
  24 #include <boost/geometry/geometries/concepts/check.hpp>
  25 #include <boost/geometry/algorithms/not_implemented.hpp>
  26 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
  27 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
  28 #include <boost/geometry/strategies/default_strategy.hpp>
  29 #include <boost/geometry/util/range.hpp>
  30
  31 #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
  32 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
  33
  34
  35 namespace boost { namespace geometry
  36 {
  37
  38 #ifndef DOXYGEN_NO_DISPATCH
  39 namespace dispatch
  40 {
  41
  42 template
  43 <
  44     typename Geometry1, typename Geometry2, typename GeometryOut,
  45     typename TagIn1 = typename tag<Geometry1>::type,
  46     typename TagIn2 = typename tag<Geometry2>::type,
  47     typename TagOut = typename tag<GeometryOut>::type,
  48     bool Areal1 = geometry::is_areal<Geometry1>::value,
  49     bool Areal2 = geometry::is_areal<Geometry2>::value,
  50     bool ArealOut = geometry::is_areal<GeometryOut>::value,
  51     bool Reverse1 = detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
  52     bool Reverse2 = detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
  53     bool ReverseOut = detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
  54     bool Reverse = geometry::reverse_dispatch<Geometry1, Geometry2>::type::value
  55 >
  56 struct union_insert: not_implemented<TagIn1, TagIn2, TagOut>
  57 {};
  58
  59
  60 // If reversal is needed, perform it first
  61
  62 template
  63 <
  64     typename Geometry1, typename Geometry2, typename GeometryOut,
  65     typename TagIn1, typename TagIn2, typename TagOut,
  66     bool Areal1, bool Areal2, bool ArealOut,
  67     bool Reverse1, bool Reverse2, bool ReverseOut
  68 >
  69 struct union_insert
  70     <
  71         Geometry1, Geometry2, GeometryOut,
  72         TagIn1, TagIn2, TagOut,
  73         Areal1, Areal2, ArealOut,
  74         Reverse1, Reverse2, ReverseOut,
  75         true
  76     >: union_insert<Geometry2, Geometry1, GeometryOut>
  77 {
  78     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  79     static inline OutputIterator apply(Geometry1 const& g1,
  80             Geometry2 const& g2,
  81             RobustPolicy const& robust_policy,
  82             OutputIterator out,
  83             Strategy const& strategy)
  84     {
  85         return union_insert
  86             <
  87                 Geometry2, Geometry1, GeometryOut
  88             >::apply(g2, g1, robust_policy, out, strategy);
  89     }
  90 };
  91
  92
  93 template
  94 <
  95     typename Geometry1, typename Geometry2, typename GeometryOut,
  96     typename TagIn1, typename TagIn2, typename TagOut,
  97     bool Reverse1, bool Reverse2, bool ReverseOut
  98 >
  99 struct union_insert
 100     <
 101         Geometry1, Geometry2, GeometryOut,
 102         TagIn1, TagIn2, TagOut,
 103         true, true, true,
 104         Reverse1, Reverse2, ReverseOut,
 105         false
 106     > : detail::overlay::overlay
 107         <Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, GeometryOut, overlay_union>
 108 {};
 109
 110
 111 // dispatch for union of non-areal geometries
 112 template
 113 <
 114     typename Geometry1, typename Geometry2, typename GeometryOut,
 115     typename TagIn1, typename TagIn2, typename TagOut,
 116     bool Reverse1, bool Reverse2, bool ReverseOut
 117 >
 118 struct union_insert
 119     <
 120         Geometry1, Geometry2, GeometryOut,
 121         TagIn1, TagIn2, TagOut,
 122         false, false, false,
 123         Reverse1, Reverse2, ReverseOut,
 124         false
 125     > : union_insert
 126         <
 127             Geometry1, Geometry2, GeometryOut,
 128             typename tag_cast<TagIn1, pointlike_tag, linear_tag>::type,
 129             typename tag_cast<TagIn2, pointlike_tag, linear_tag>::type,
 130             TagOut,
 131             false, false, false,
 132             Reverse1, Reverse2, ReverseOut,
 133             false
 134         >
 135 {};
 136
 137
 138 // dispatch for union of linear geometries
 139 template
 140 <
 141     typename Linear1, typename Linear2, typename LineStringOut,
 142     bool Reverse1, bool Reverse2, bool ReverseOut
 143 >
 144 struct union_insert
 145     <
 146         Linear1, Linear2, LineStringOut,
 147         linear_tag, linear_tag, linestring_tag,
 148         false, false, false,
 149         Reverse1, Reverse2, ReverseOut,
 150         false
 151     > : detail::overlay::linear_linear_linestring
 152         <
 153             Linear1, Linear2, LineStringOut, overlay_union
 154         >
 155 {};
 156
 157
 158 // dispatch for point-like geometries
 159 template
 160 <
 161     typename PointLike1, typename PointLike2, typename PointOut,
 162     bool Reverse1, bool Reverse2, bool ReverseOut
 163 >
 164 struct union_insert
 165     <
 166         PointLike1, PointLike2, PointOut,
 167         pointlike_tag, pointlike_tag, point_tag,
 168         false, false, false,
 169         Reverse1, Reverse2, ReverseOut,
 170         false
 171     > : detail::overlay::union_pointlike_pointlike_point
 172         <
 173             PointLike1, PointLike2, PointOut
 174         >
 175 {};
 176
 177
 178 } // namespace dispatch
 179 #endif // DOXYGEN_NO_DISPATCH
 180
 181 #ifndef DOXYGEN_NO_DETAIL
 182 namespace detail { namespace union_
 183 {
 184
 185 /*!
 186 \brief_calc2{union}
 187 \ingroup union
 188 \details \details_calc2{union_insert, spatial set theoretic union}.
 189     \details_insert{union}
 190 \tparam GeometryOut output geometry type, must be specified
 191 \tparam Geometry1 \tparam_geometry
 192 \tparam Geometry2 \tparam_geometry
 193 \tparam OutputIterator output iterator
 194 \param geometry1 \param_geometry
 195 \param geometry2 \param_geometry
 196 \param out \param_out{union}
 197 \return \return_out
 198 */
 199 template
 200 <
 201     typename GeometryOut,
 202     typename Geometry1,
 203     typename Geometry2,
 204     typename OutputIterator
 205 >
 206 inline OutputIterator union_insert(Geometry1 const& geometry1,
 207             Geometry2 const& geometry2,
 208             OutputIterator out)
 209 {
 210     concepts::check<Geometry1 const>();
 211     concepts::check<Geometry2 const>();
 212     concepts::check<GeometryOut>();
 213
 214     typedef typename geometry::rescale_overlay_policy_type
 215         <
 216             Geometry1,
 217             Geometry2
 218         >::type rescale_policy_type;
 219
 220     typename strategy::intersection::services::default_strategy
 221         <
 222             typename cs_tag<GeometryOut>::type
 223         >::type strategy;
 224
 225     rescale_policy_type robust_policy
 226             = geometry::get_rescale_policy<rescale_policy_type>(geometry1, geometry2);
 227
 228     return dispatch::union_insert
 229            <
 230                Geometry1, Geometry2, GeometryOut
 231            >::apply(geometry1, geometry2, robust_policy, out, strategy);
 232 }
 233
 234
 235 }} // namespace detail::union_
 236 #endif // DOXYGEN_NO_DETAIL
 237
 238
 239 namespace resolve_strategy {
 240
 241 struct union_
 242 {
 243     template
 244     <
 245         typename Geometry1,
 246         typename Geometry2,
 247         typename RobustPolicy,
 248         typename Collection,
 249         typename Strategy
 250     >
 251     static inline void apply(Geometry1 const& geometry1,
 252                              Geometry2 const& geometry2,
 253                              RobustPolicy const& robust_policy,
 254                              Collection & output_collection,
 255                              Strategy const& strategy)
 256     {
 257         typedef typename boost::range_value<Collection>::type geometry_out;
 258
 259         dispatch::union_insert
 260            <
 261                Geometry1, Geometry2, geometry_out
 262            >::apply(geometry1, geometry2, robust_policy,
 263                     range::back_inserter(output_collection),
 264                     strategy);
 265     }
 266
 267     template
 268     <
 269         typename Geometry1,
 270         typename Geometry2,
 271         typename RobustPolicy,
 272         typename Collection
 273     >
 274     static inline void apply(Geometry1 const& geometry1,
 275                              Geometry2 const& geometry2,
 276                              RobustPolicy const& robust_policy,
 277                              Collection & output_collection,
 278                              default_strategy)
 279     {
 280         typedef typename boost::range_value<Collection>::type geometry_out;
 281
 282         typedef typename strategy::intersection::services::default_strategy
 283             <
 284                 typename cs_tag<geometry_out>::type
 285             >::type strategy_type;
 286
 287         dispatch::union_insert
 288            <
 289                Geometry1, Geometry2, geometry_out
 290            >::apply(geometry1, geometry2, robust_policy,
 291                     range::back_inserter(output_collection),
 292                     strategy_type());
 293     }
 294 };
 295
 296 } // resolve_strategy
 297
 298
 299 namespace resolve_variant
 300 {
 301
 302 template <typename Geometry1, typename Geometry2>
 303 struct union_
 304 {
 305     template <typename Collection, typename Strategy>
 306     static inline void apply(Geometry1 const& geometry1,
 307                              Geometry2 const& geometry2,
 308                              Collection& output_collection,
 309                              Strategy const& strategy)
 310     {
 311         concepts::check<Geometry1 const>();
 312         concepts::check<Geometry2 const>();
 313         concepts::check<typename boost::range_value<Collection>::type>();
 314
 315         typedef typename geometry::rescale_overlay_policy_type
 316             <
 317                 Geometry1,
 318                 Geometry2
 319             >::type rescale_policy_type;
 320
 321         rescale_policy_type robust_policy
 322                 = geometry::get_rescale_policy<rescale_policy_type>(geometry1,
 323                                                                     geometry2);
 324
 325         resolve_strategy::union_::apply(geometry1, geometry2,
 326                                         robust_policy,
 327                                         output_collection,
 328                                         strategy);
 329     }
 330 };
 331
 332
 333 template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2>
 334 struct union_<variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2>
 335 {
 336     template <typename Collection, typename Strategy>
 337     struct visitor: static_visitor<>
 338     {
 339         Geometry2 const& m_geometry2;
 340         Collection& m_output_collection;
 341         Strategy const& m_strategy;
 342
 343         visitor(Geometry2 const& geometry2,
 344                 Collection& output_collection,
 345                 Strategy const& strategy)
 346             : m_geometry2(geometry2)
 347             , m_output_collection(output_collection)
 348             , m_strategy(strategy)
 349         {}
 350
 351         template <typename Geometry1>
 352         void operator()(Geometry1 const& geometry1) const
 353         {
 354             union_
 355                 <
 356                     Geometry1,
 357                     Geometry2
 358                 >::apply(geometry1, m_geometry2, m_output_collection, m_strategy);
 359         }
 360     };
 361
 362     template <typename Collection, typename Strategy>
 363     static inline void
 364     apply(variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1,
 365           Geometry2 const& geometry2,
 366           Collection& output_collection,
 367           Strategy const& strategy)
 368     {
 369         boost::apply_visitor(visitor<Collection, Strategy>(geometry2,
 370                                                            output_collection,
 371                                                            strategy),
 372                              geometry1);
 373     }
 374 };
 375
 376
 377 template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)>
 378 struct union_<Geometry1, variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 379 {
 380     template <typename Collection, typename Strategy>
 381     struct visitor: static_visitor<>
 382     {
 383         Geometry1 const& m_geometry1;
 384         Collection& m_output_collection;
 385         Strategy const& m_strategy;
 386
 387         visitor(Geometry1 const& geometry1,
 388                 Collection& output_collection,
 389                 Strategy const& strategy)
 390             : m_geometry1(geometry1)
 391             , m_output_collection(output_collection)
 392             , m_strategy(strategy)
 393         {}
 394
 395         template <typename Geometry2>
 396         void operator()(Geometry2 const& geometry2) const
 397         {
 398             union_
 399                 <
 400                     Geometry1,
 401                     Geometry2
 402                 >::apply(m_geometry1, geometry2, m_output_collection, m_strategy);
 403         }
 404     };
 405
 406     template <typename Collection, typename Strategy>
 407     static inline void
 408     apply(Geometry1 const& geometry1,
 409           variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2,
 410           Collection& output_collection,
 411           Strategy const& strategy)
 412     {
 413         boost::apply_visitor(visitor<Collection, Strategy>(geometry1,
 414                                                            output_collection,
 415                                                            strategy),
 416                              geometry2);
 417     }
 418 };
 419
 420
 421 template <BOOST_VARIANT_ENUM_PARAMS(typename T1), BOOST_VARIANT_ENUM_PARAMS(typename T2)>
 422 struct union_<variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, variant<BOOST_VARIANT_ENUM_PARAMS(T2)> >
 423 {
 424     template <typename Collection, typename Strategy>
 425     struct visitor: static_visitor<>
 426     {
 427         Collection& m_output_collection;
 428         Strategy const& m_strategy;
 429
 430         visitor(Collection& output_collection, Strategy const& strategy)
 431             : m_output_collection(output_collection)
 432             , m_strategy(strategy)
 433         {}
 434
 435         template <typename Geometry1, typename Geometry2>
 436         void operator()(Geometry1 const& geometry1,
 437                         Geometry2 const& geometry2) const
 438         {
 439             union_
 440                 <
 441                     Geometry1,
 442                     Geometry2
 443                 >::apply(geometry1, geometry2, m_output_collection, m_strategy);
 444         }
 445     };
 446
 447     template <typename Collection, typename Strategy>
 448     static inline void
 449     apply(variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1,
 450           variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2,
 451           Collection& output_collection,
 452           Strategy const& strategy)
 453     {
 454         boost::apply_visitor(visitor<Collection, Strategy>(output_collection,
 455                                                            strategy),
 456                              geometry1, geometry2);
 457     }
 458 };
 459
 460 } // namespace resolve_variant
 461
 462
 463 /*!
 464 \brief Combines two geometries which each other
 465 \ingroup union
 466 \details \details_calc2{union, spatial set theoretic union}.
 467 \tparam Geometry1 \tparam_geometry
 468 \tparam Geometry2 \tparam_geometry
 469 \tparam Collection output collection, either a multi-geometry,
 470     or a std::vector<Geometry> / std::deque<Geometry> etc
 471 \tparam Strategy \tparam_strategy{Union_}
 472 \param geometry1 \param_geometry
 473 \param geometry2 \param_geometry
 474 \param output_collection the output collection
 475 \param strategy \param_strategy{union_}
 476 \note Called union_ because union is a reserved word.
 477
 478 \qbk{distinguish,with strategy}
 479 \qbk{[include reference/algorithms/union.qbk]}
 480 */
 481 template
 482 <
 483     typename Geometry1,
 484     typename Geometry2,
 485     typename Collection,
 486     typename Strategy
 487 >
 488 inline void union_(Geometry1 const& geometry1,
 489                    Geometry2 const& geometry2,
 490                    Collection& output_collection,
 491                    Strategy const& strategy)
 492 {
 493     resolve_variant::union_
 494         <
 495             Geometry1,
 496             Geometry2
 497         >::apply(geometry1, geometry2, output_collection, strategy);
 498 }
 499
 500
 501 /*!
 502 \brief Combines two geometries which each other
 503 \ingroup union
 504 \details \details_calc2{union, spatial set theoretic union}.
 505 \tparam Geometry1 \tparam_geometry
 506 \tparam Geometry2 \tparam_geometry
 507 \tparam Collection output collection, either a multi-geometry,
 508     or a std::vector<Geometry> / std::deque<Geometry> etc
 509 \param geometry1 \param_geometry
 510 \param geometry2 \param_geometry
 511 \param output_collection the output collection
 512 \note Called union_ because union is a reserved word.
 513
 514 \qbk{[include reference/algorithms/union.qbk]}
 515 */
 516 template
 517 <
 518     typename Geometry1,
 519     typename Geometry2,
 520     typename Collection
 521 >
 522 inline void union_(Geometry1 const& geometry1,
 523                    Geometry2 const& geometry2,
 524                    Collection& output_collection)
 525 {
 526     resolve_variant::union_
 527         <
 528             Geometry1,
 529             Geometry2
 530         >::apply(geometry1, geometry2, output_collection, default_strategy());
 531 }
 532
 533
 534 }} // namespace boost::geometry
 535
 536
 537 #endif // BOOST_GEOMETRY_ALGORITHMS_UNION_HPP