Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
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/calculate_distance_policy.hpp>
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@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@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: #ifdef BOOST_GEOMETRY_TIME_OVERLAY
Chris@16: # include <boost/timer.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: // Skip for assemble process
Chris@16: template <typename TurnInfo>
Chris@16: inline bool skip(TurnInfo const& turn_info)
Chris@16: {
Chris@16:     return (turn_info.discarded || turn_info.both(operation_union))
Chris@16:         && ! turn_info.any_blocked()
Chris@16:         && ! turn_info.both(operation_intersection)
Chris@16:         ;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <typename TurnPoints, typename Map>
Chris@16: inline void map_turns(Map& map, 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:     int index = 0;
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@16:          ++it, ++index)
Chris@16:     {
Chris@16:         if (! skip(*it))
Chris@16:         {
Chris@16:             int op_index = 0;
Chris@16:             for (typename boost::range_iterator<container_type const>::type
Chris@16:                     op_it = boost::begin(it->operations);
Chris@16:                 op_it != boost::end(it->operations);
Chris@16:                 ++op_it, ++op_index)
Chris@16:             {
Chris@16:                 ring_identifier ring_id
Chris@16:                     (
Chris@16:                         op_it->seg_id.source_index,
Chris@16:                         op_it->seg_id.multi_index,
Chris@16:                         op_it->seg_id.ring_index
Chris@16:                     );
Chris@16:                 map[ring_id]++;
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@16: #pragma warning(push)  
Chris@16: #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@16: #pragma warning(pop)  
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16:     std::map<ring_identifier, int> empty;
Chris@16:     std::map<ring_identifier, properties> all_of_one_of_them;
Chris@16: 
Chris@16:     select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them, false);
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@16:     template <typename OutputIterator, typename Strategy>
Chris@16:     static inline OutputIterator apply(
Chris@16:                 Geometry1 const& geometry1, Geometry2 const& geometry2,
Chris@16:                 OutputIterator out,
Chris@16:                 Strategy const& )
Chris@16:     {
Chris@16:         if (geometry::num_points(geometry1) == 0
Chris@16:             && geometry::num_points(geometry2) == 0)
Chris@16:         {
Chris@16:             return out;
Chris@16:         }
Chris@16: 
Chris@16:         if (geometry::num_points(geometry1) == 0
Chris@16:             || 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@16:         typedef detail::overlay::traversal_turn_info<point_type> 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_TIME_OVERLAY
Chris@16:         boost::timer timer;
Chris@16: #endif
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@16:                 detail::overlay::calculate_distance_policy
Chris@16:             >(geometry1, geometry2, turn_points, policy);
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_TIME_OVERLAY
Chris@16:         std::cout << "get_turns: " << timer.elapsed() << std::endl;
Chris@16: #endif
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@16:                     side_strategy);
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_TIME_OVERLAY
Chris@16:         std::cout << "enrich_intersection_points: " << timer.elapsed() << std::endl;
Chris@16: #endif
Chris@16: 
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@16:                     turn_points, rings
Chris@16:                 );
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_TIME_OVERLAY
Chris@16:         std::cout << "traverse: " << timer.elapsed() << std::endl;
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16:         std::map<ring_identifier, int> map;
Chris@16:         map_turns(map, turn_points);
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_TIME_OVERLAY
Chris@16:         std::cout << "map_turns: " << timer.elapsed() << std::endl;
Chris@16: #endif
Chris@16: 
Chris@16:         typedef ring_properties<typename geometry::point_type<GeometryOut>::type> properties;
Chris@16: 
Chris@16:         std::map<ring_identifier, properties> selected;
Chris@16:         select_rings<Direction>(geometry1, geometry2, map, selected, ! turn_points.empty());
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_TIME_OVERLAY
Chris@16:         std::cout << "select_rings: " << timer.elapsed() << std::endl;
Chris@16: #endif
Chris@16: 
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@16:                     it != boost::end(rings);
Chris@16:                     ++it)
Chris@16:             {
Chris@16:                 selected[id] = properties(*it, true);
Chris@16:                 selected[id].reversed = ReverseOut;
Chris@16:                 id.multi_index++;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_TIME_OVERLAY
Chris@16:         std::cout << "add traversal rings: " << timer.elapsed() << std::endl;
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16:         assign_parents(geometry1, geometry2, rings, selected);
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_TIME_OVERLAY
Chris@16:         std::cout << "assign_parents: " << timer.elapsed() << std::endl;
Chris@16: #endif
Chris@16: 
Chris@16:         return add_rings<GeometryOut>(selected, geometry1, geometry2, rings, out);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: // Metafunction helper for intersection and union
Chris@16: template <order_selector Selector, bool Reverse = false>
Chris@16: struct do_reverse {};
Chris@16: 
Chris@16: template <>
Chris@16: struct do_reverse<clockwise, false> : boost::false_type {};
Chris@16: 
Chris@16: template <>
Chris@16: struct do_reverse<clockwise, true> : boost::true_type {};
Chris@16: 
Chris@16: template <>
Chris@16: struct do_reverse<counterclockwise, false> : boost::true_type {};
Chris@16: 
Chris@16: template <>
Chris@16: struct do_reverse<counterclockwise, true> : boost::false_type {};
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