ceph/src/boost/boost/geometry/algorithms/sym_difference.hpp

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