Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@101: // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
Chris@101: 
Chris@101: // This file was modified by Oracle on 2014.
Chris@101: // Modifications copyright (c) 2014 Oracle and/or its affiliates.
Chris@101: 
Chris@101: // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <boost/range/metafunctions.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/core/is_areal.hpp>
Chris@16: #include <boost/geometry/core/point_order.hpp>
Chris@16: #include <boost/geometry/core/reverse_dispatch.hpp>
Chris@16: #include <boost/geometry/geometries/concepts/check.hpp>
Chris@16: #include <boost/geometry/algorithms/not_implemented.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
Chris@101: #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
Chris@101: 
Chris@101: #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
Chris@101: #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DISPATCH
Chris@16: namespace dispatch
Chris@16: {
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Geometry1, typename Geometry2, typename GeometryOut,
Chris@16:     typename TagIn1 = typename tag<Geometry1>::type,
Chris@16:     typename TagIn2 = typename tag<Geometry2>::type,
Chris@16:     typename TagOut = typename tag<GeometryOut>::type,
Chris@16:     bool Areal1 = geometry::is_areal<Geometry1>::value,
Chris@16:     bool Areal2 = geometry::is_areal<Geometry2>::value,
Chris@16:     bool ArealOut = geometry::is_areal<GeometryOut>::value,
Chris@16:     bool Reverse1 = detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
Chris@16:     bool Reverse2 = detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
Chris@16:     bool ReverseOut = detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
Chris@16:     bool Reverse = geometry::reverse_dispatch<Geometry1, Geometry2>::type::value
Chris@16: >
Chris@16: struct union_insert: not_implemented<TagIn1, TagIn2, TagOut>
Chris@16: {};
Chris@16: 
Chris@16: 
Chris@16: // If reversal is needed, perform it first
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Geometry1, typename Geometry2, typename GeometryOut,
Chris@16:     typename TagIn1, typename TagIn2, typename TagOut,
Chris@101:     bool Areal1, bool Areal2, bool ArealOut,
Chris@16:     bool Reverse1, bool Reverse2, bool ReverseOut
Chris@16: >
Chris@16: struct union_insert
Chris@16:     <
Chris@16:         Geometry1, Geometry2, GeometryOut,
Chris@16:         TagIn1, TagIn2, TagOut,
Chris@101:         Areal1, Areal2, ArealOut,
Chris@16:         Reverse1, Reverse2, ReverseOut,
Chris@16:         true
Chris@16:     >: union_insert<Geometry2, Geometry1, GeometryOut>
Chris@16: {
Chris@101:     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
Chris@16:     static inline OutputIterator apply(Geometry1 const& g1,
Chris@101:             Geometry2 const& g2,
Chris@101:             RobustPolicy const& robust_policy,
Chris@101:             OutputIterator out,
Chris@16:             Strategy const& strategy)
Chris@16:     {
Chris@16:         return union_insert
Chris@16:             <
Chris@16:                 Geometry2, Geometry1, GeometryOut
Chris@101:             >::apply(g2, g1, robust_policy, out, strategy);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Geometry1, typename Geometry2, typename GeometryOut,
Chris@16:     typename TagIn1, typename TagIn2, typename TagOut,
Chris@16:     bool Reverse1, bool Reverse2, bool ReverseOut
Chris@16: >
Chris@16: struct union_insert
Chris@16:     <
Chris@16:         Geometry1, Geometry2, GeometryOut,
Chris@16:         TagIn1, TagIn2, TagOut,
Chris@16:         true, true, true,
Chris@16:         Reverse1, Reverse2, ReverseOut,
Chris@16:         false
Chris@16:     > : detail::overlay::overlay
Chris@16:         <Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, GeometryOut, overlay_union>
Chris@16: {};
Chris@16: 
Chris@16: 
Chris@101: // dispatch for union of non-areal geometries
Chris@101: template
Chris@101: <
Chris@101:     typename Geometry1, typename Geometry2, typename GeometryOut,
Chris@101:     typename TagIn1, typename TagIn2, typename TagOut,
Chris@101:     bool Reverse1, bool Reverse2, bool ReverseOut
Chris@101: >
Chris@101: struct union_insert
Chris@101:     <
Chris@101:         Geometry1, Geometry2, GeometryOut,
Chris@101:         TagIn1, TagIn2, TagOut,
Chris@101:         false, false, false,
Chris@101:         Reverse1, Reverse2, ReverseOut,
Chris@101:         false
Chris@101:     > : union_insert
Chris@101:         <
Chris@101:             Geometry1, Geometry2, GeometryOut,
Chris@101:             typename tag_cast<TagIn1, pointlike_tag, linear_tag>::type,
Chris@101:             typename tag_cast<TagIn2, pointlike_tag, linear_tag>::type,
Chris@101:             TagOut,
Chris@101:             false, false, false,
Chris@101:             Reverse1, Reverse2, ReverseOut,
Chris@101:             false
Chris@101:         >
Chris@101: {};
Chris@101: 
Chris@101: 
Chris@101: // dispatch for union of linear geometries
Chris@101: template
Chris@101: <
Chris@101:     typename Linear1, typename Linear2, typename LineStringOut,
Chris@101:     bool Reverse1, bool Reverse2, bool ReverseOut
Chris@101: >
Chris@101: struct union_insert
Chris@101:     <
Chris@101:         Linear1, Linear2, LineStringOut,
Chris@101:         linear_tag, linear_tag, linestring_tag,
Chris@101:         false, false, false,
Chris@101:         Reverse1, Reverse2, ReverseOut,
Chris@101:         false
Chris@101:     > : detail::overlay::linear_linear_linestring
Chris@101:         <
Chris@101:             Linear1, Linear2, LineStringOut, overlay_union
Chris@101:         >
Chris@101: {};
Chris@101: 
Chris@101: 
Chris@101: // dispatch for point-like geometries
Chris@101: template
Chris@101: <
Chris@101:     typename PointLike1, typename PointLike2, typename PointOut,
Chris@101:     bool Reverse1, bool Reverse2, bool ReverseOut
Chris@101: >
Chris@101: struct union_insert
Chris@101:     <
Chris@101:         PointLike1, PointLike2, PointOut,
Chris@101:         pointlike_tag, pointlike_tag, point_tag,
Chris@101:         false, false, false,
Chris@101:         Reverse1, Reverse2, ReverseOut,
Chris@101:         false
Chris@101:     > : detail::overlay::union_pointlike_pointlike_point
Chris@101:         <
Chris@101:             PointLike1, PointLike2, PointOut
Chris@101:         >
Chris@101: {};
Chris@101: 
Chris@101: 
Chris@16: } // namespace dispatch
Chris@16: #endif // DOXYGEN_NO_DISPATCH
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail { namespace union_
Chris@16: {
Chris@16: 
Chris@16: /*!
Chris@16: \brief_calc2{union}
Chris@16: \ingroup union
Chris@16: \details \details_calc2{union_insert, spatial set theoretic union}.
Chris@16:     \details_insert{union}
Chris@16: \tparam GeometryOut output geometry type, must be specified
Chris@16: \tparam Geometry1 \tparam_geometry
Chris@16: \tparam Geometry2 \tparam_geometry
Chris@16: \tparam OutputIterator output iterator
Chris@16: \param geometry1 \param_geometry
Chris@16: \param geometry2 \param_geometry
Chris@16: \param out \param_out{union}
Chris@16: \return \return_out
Chris@16: */
Chris@16: template
Chris@16: <
Chris@16:     typename GeometryOut,
Chris@16:     typename Geometry1,
Chris@16:     typename Geometry2,
Chris@16:     typename OutputIterator
Chris@16: >
Chris@16: inline OutputIterator union_insert(Geometry1 const& geometry1,
Chris@16:             Geometry2 const& geometry2,
Chris@16:             OutputIterator out)
Chris@16: {
Chris@16:     concept::check<Geometry1 const>();
Chris@16:     concept::check<Geometry2 const>();
Chris@16:     concept::check<GeometryOut>();
Chris@16: 
Chris@101:     typedef typename geometry::rescale_overlay_policy_type
Chris@101:         <
Chris@101:             Geometry1,
Chris@101:             Geometry2
Chris@101:         >::type rescale_policy_type;
Chris@101: 
Chris@16:     typedef strategy_intersection
Chris@16:         <
Chris@16:             typename cs_tag<GeometryOut>::type,
Chris@16:             Geometry1,
Chris@16:             Geometry2,
Chris@101:             typename geometry::point_type<GeometryOut>::type,
Chris@101:             rescale_policy_type
Chris@16:         > strategy;
Chris@16: 
Chris@101:     rescale_policy_type robust_policy
Chris@101:             = geometry::get_rescale_policy<rescale_policy_type>(geometry1, geometry2);
Chris@101: 
Chris@101:     return dispatch::union_insert
Chris@101:            <
Chris@101:                Geometry1, Geometry2, GeometryOut
Chris@101:            >::apply(geometry1, geometry2, robust_policy, out, strategy());
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: }} // namespace detail::union_
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16: \brief Combines two geometries which each other
Chris@16: \ingroup union
Chris@16: \details \details_calc2{union, spatial set theoretic union}.
Chris@16: \tparam Geometry1 \tparam_geometry
Chris@16: \tparam Geometry2 \tparam_geometry
Chris@16: \tparam Collection output collection, either a multi-geometry,
Chris@16:     or a std::vector<Geometry> / std::deque<Geometry> etc
Chris@16: \param geometry1 \param_geometry
Chris@16: \param geometry2 \param_geometry
Chris@16: \param output_collection the output collection
Chris@16: \note Called union_ because union is a reserved word.
Chris@16: 
Chris@16: \qbk{[include reference/algorithms/union.qbk]}
Chris@16: */
Chris@16: template
Chris@16: <
Chris@16:     typename Geometry1,
Chris@16:     typename Geometry2,
Chris@16:     typename Collection
Chris@16: >
Chris@16: inline void union_(Geometry1 const& geometry1,
Chris@16:             Geometry2 const& geometry2,
Chris@16:             Collection& output_collection)
Chris@16: {
Chris@16:     concept::check<Geometry1 const>();
Chris@16:     concept::check<Geometry2 const>();
Chris@16: 
Chris@16:     typedef typename boost::range_value<Collection>::type geometry_out;
Chris@16:     concept::check<geometry_out>();
Chris@16: 
Chris@16:     detail::union_::union_insert<geometry_out>(geometry1, geometry2,
Chris@16:                 std::back_inserter(output_collection));
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_UNION_HPP