Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@101: // Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland
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_DETAIL_OVERLAY_OVERLAY_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <deque>
Chris@16: #include <map>
Chris@16: 
Chris@16: #include <boost/range.hpp>
Chris@16: #include <boost/mpl/assert.hpp>
Chris@16: 
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/algorithms/detail/recalculate.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/num_points.hpp>
Chris@16: #include <boost/geometry/algorithms/reverse.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
Chris@101: #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
Chris@101: 
Chris@101: #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
Chris@16: 
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
Chris@16: #  include <boost/geometry/io/dsv/write.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail { namespace overlay
Chris@16: {
Chris@16: 
Chris@16: 
Chris@101: template <typename TurnPoints, typename TurnInfoMap>
Chris@101: inline void get_ring_turn_info(TurnInfoMap& turn_info_map,
Chris@101:         TurnPoints const& turn_points)
Chris@16: {
Chris@16:     typedef typename boost::range_value<TurnPoints>::type turn_point_type;
Chris@16:     typedef typename turn_point_type::container_type container_type;
Chris@16: 
Chris@16:     for (typename boost::range_iterator<TurnPoints const>::type
Chris@16:             it = boost::begin(turn_points);
Chris@16:          it != boost::end(turn_points);
Chris@101:          ++it)
Chris@16:     {
Chris@101:         typename boost::range_value<TurnPoints>::type const& turn_info = *it;
Chris@101:         bool both_uu = turn_info.both(operation_union);
Chris@101:         bool skip = (turn_info.discarded || both_uu)
Chris@101:             && ! turn_info.any_blocked()
Chris@101:             && ! turn_info.both(operation_intersection)
Chris@101:             ;
Chris@101: 
Chris@101:         for (typename boost::range_iterator<container_type const>::type
Chris@101:                 op_it = boost::begin(turn_info.operations);
Chris@101:             op_it != boost::end(turn_info.operations);
Chris@101:             ++op_it)
Chris@16:         {
Chris@101:             ring_identifier ring_id
Chris@101:                 (
Chris@101:                     op_it->seg_id.source_index,
Chris@101:                     op_it->seg_id.multi_index,
Chris@101:                     op_it->seg_id.ring_index
Chris@101:                 );
Chris@101: 
Chris@101:             if (! skip)
Chris@16:             {
Chris@101:                 turn_info_map[ring_id].has_normal_turn = true;
Chris@101:             }
Chris@101:             else if (both_uu)
Chris@101:             {
Chris@101:                 turn_info_map[ring_id].has_uu_turn = true;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename GeometryOut, overlay_type Direction, bool ReverseOut,
Chris@16:     typename Geometry1, typename Geometry2,
Chris@16:     typename OutputIterator
Chris@16: >
Chris@16: inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
Chris@16:             Geometry2 const& geometry2,
Chris@16:             OutputIterator out)
Chris@16: {
Chris@16:     typedef std::deque
Chris@16:         <
Chris@16:             typename geometry::ring_type<GeometryOut>::type
Chris@16:         > ring_container_type;
Chris@16: 
Chris@16:     typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties;
Chris@16: 
Chris@16: // Silence warning C4127: conditional expression is constant
Chris@16: #if defined(_MSC_VER)
Chris@101: #pragma warning(push)
Chris@101: #pragma warning(disable : 4127)
Chris@16: #endif
Chris@16: 
Chris@16:     // Union: return either of them
Chris@16:     // Intersection: return nothing
Chris@16:     // Difference: return first of them
Chris@16:     if (Direction == overlay_intersection
Chris@16:         || (Direction == overlay_difference
Chris@16:             && geometry::num_points(geometry1) == 0))
Chris@16:     {
Chris@16:         return out;
Chris@16:     }
Chris@16: 
Chris@16: #if defined(_MSC_VER)
Chris@101: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@101:     std::map<ring_identifier, ring_turn_info> empty;
Chris@16:     std::map<ring_identifier, properties> all_of_one_of_them;
Chris@16: 
Chris@101:     select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them);
Chris@16:     ring_container_type rings;
Chris@16:     assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
Chris@16:     return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Geometry1, typename Geometry2,
Chris@16:     bool Reverse1, bool Reverse2, bool ReverseOut,
Chris@16:     typename GeometryOut,
Chris@16:     overlay_type Direction
Chris@16: >
Chris@16: struct overlay
Chris@16: {
Chris@101:     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
Chris@16:     static inline OutputIterator apply(
Chris@16:                 Geometry1 const& geometry1, Geometry2 const& geometry2,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@16:                 OutputIterator out,
Chris@16:                 Strategy const& )
Chris@16:     {
Chris@101:         if ( geometry::num_points(geometry1) == 0
Chris@101:           && geometry::num_points(geometry2) == 0 )
Chris@16:         {
Chris@16:             return out;
Chris@16:         }
Chris@16: 
Chris@101:         if ( geometry::num_points(geometry1) == 0
Chris@101:           || geometry::num_points(geometry2) == 0 )
Chris@16:         {
Chris@16:             return return_if_one_input_is_empty
Chris@16:                 <
Chris@16:                     GeometryOut, Direction, ReverseOut
Chris@16:                 >(geometry1, geometry2, out);
Chris@16:         }
Chris@16: 
Chris@16:         typedef typename geometry::point_type<GeometryOut>::type point_type;
Chris@101:         typedef detail::overlay::traversal_turn_info
Chris@101:         <
Chris@101:             point_type,
Chris@101:             typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
Chris@101:         > turn_info;
Chris@16:         typedef std::deque<turn_info> container_type;
Chris@16: 
Chris@16:         typedef std::deque
Chris@16:             <
Chris@16:                 typename geometry::ring_type<GeometryOut>::type
Chris@16:             > ring_container_type;
Chris@16: 
Chris@16:         container_type turn_points;
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
Chris@16: std::cout << "get turns" << std::endl;
Chris@16: #endif
Chris@16:         detail::get_turns::no_interrupt_policy policy;
Chris@16:         geometry::get_turns
Chris@16:             <
Chris@16:                 Reverse1, Reverse2,
Chris@101:                 detail::overlay::assign_null_policy
Chris@101:             >(geometry1, geometry2, robust_policy, turn_points, policy);
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
Chris@16: std::cout << "enrich" << std::endl;
Chris@16: #endif
Chris@16:         typename Strategy::side_strategy_type side_strategy;
Chris@16:         geometry::enrich_intersection_points<Reverse1, Reverse2>(turn_points,
Chris@16:                 Direction == overlay_union
Chris@16:                     ? geometry::detail::overlay::operation_union
Chris@16:                     : geometry::detail::overlay::operation_intersection,
Chris@16:                     geometry1, geometry2,
Chris@101:                     robust_policy,
Chris@16:                     side_strategy);
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
Chris@16: std::cout << "traverse" << std::endl;
Chris@16: #endif
Chris@16:         // Traverse through intersection/turn points and create rings of them.
Chris@16:         // Note that these rings are always in clockwise order, even in CCW polygons,
Chris@16:         // and are marked as "to be reversed" below
Chris@16:         ring_container_type rings;
Chris@16:         traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply
Chris@16:                 (
Chris@16:                     geometry1, geometry2,
Chris@16:                     Direction == overlay_union
Chris@16:                         ? geometry::detail::overlay::operation_union
Chris@16:                         : geometry::detail::overlay::operation_intersection,
Chris@101:                     robust_policy,
Chris@16:                     turn_points, rings
Chris@16:                 );
Chris@16: 
Chris@101:         std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
Chris@101:         get_ring_turn_info(turn_info_per_ring, turn_points);
Chris@16: 
Chris@101:         typedef ring_properties
Chris@101:         <
Chris@101:             typename geometry::point_type<GeometryOut>::type
Chris@101:         > properties;
Chris@16: 
Chris@101:         // Select all rings which are NOT touched by any intersection point
Chris@101:         std::map<ring_identifier, properties> selected_ring_properties;
Chris@101:         select_rings<Direction>(geometry1, geometry2, turn_info_per_ring,
Chris@101:                 selected_ring_properties);
Chris@16: 
Chris@16:         // Add rings created during traversal
Chris@16:         {
Chris@16:             ring_identifier id(2, 0, -1);
Chris@16:             for (typename boost::range_iterator<ring_container_type>::type
Chris@16:                     it = boost::begin(rings);
Chris@101:                  it != boost::end(rings);
Chris@101:                  ++it)
Chris@16:             {
Chris@101:                 selected_ring_properties[id] = properties(*it);
Chris@101:                 selected_ring_properties[id].reversed = ReverseOut;
Chris@16:                 id.multi_index++;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@101:         assign_parents(geometry1, geometry2, rings, selected_ring_properties);
Chris@16: 
Chris@101:         return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: }} // namespace detail::overlay
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP