1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland
6 // This file was modified by Oracle on 2015.
7 // Modifications copyright (c) 2015, Oracle and/or its affiliates.
9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
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)
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
22 #include <boost/range.hpp>
23 #include <boost/mpl/assert.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
27 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
30 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
33 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
35 #include <boost/geometry/algorithms/detail/recalculate.hpp>
37 #include <boost/geometry/algorithms/is_empty.hpp>
38 #include <boost/geometry/algorithms/reverse.hpp>
40 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
41 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
42 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
43 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
44 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
46 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
49 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
50 # include <boost/geometry/io/dsv/write.hpp>
54 namespace boost { namespace geometry
58 #ifndef DOXYGEN_NO_DETAIL
59 namespace detail { namespace overlay
63 //! Default visitor for overlay, doing nothing
64 struct overlay_null_visitor
66 void print(char const* ) {}
68 template <typename Turns>
69 void print(char const* , Turns const& , int) {}
71 template <typename Turns>
72 void print(char const* , Turns const& , int , int ) {}
74 template <typename Turns>
75 void visit_turns(int , Turns const& ) {}
77 template <typename Clusters, typename Turns>
78 void visit_clusters(Clusters const& , Turns const& ) {}
80 template <typename Turns, typename Turn, typename Operation>
81 void visit_traverse(Turns const& , Turn const& , Operation const& , char const*)
84 template <typename Turns, typename Turn, typename Operation>
85 void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type )
89 template <typename Turns, typename TurnInfoMap>
90 inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns)
92 typedef typename boost::range_value<Turns>::type turn_type;
93 typedef typename turn_type::container_type container_type;
95 for (typename boost::range_iterator<Turns const>::type
96 it = boost::begin(turns);
97 it != boost::end(turns);
100 typename boost::range_value<Turns>::type const& turn_info = *it;
102 if (turn_info.discarded
103 && ! turn_info.any_blocked()
104 && ! turn_info.colocated)
109 for (typename boost::range_iterator<container_type const>::type
110 op_it = boost::begin(turn_info.operations);
111 op_it != boost::end(turn_info.operations);
114 ring_identifier const ring_id
116 op_it->seg_id.source_index,
117 op_it->seg_id.multi_index,
118 op_it->seg_id.ring_index
120 turn_info_map[ring_id].has_normal_turn = true;
128 typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
129 typename Geometry1, typename Geometry2,
130 typename OutputIterator
132 inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
133 Geometry2 const& geometry2,
138 typename geometry::ring_type<GeometryOut>::type
139 > ring_container_type;
141 typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties;
143 // Silence warning C4127: conditional expression is constant
144 #if defined(_MSC_VER)
145 #pragma warning(push)
146 #pragma warning(disable : 4127)
149 // Union: return either of them
150 // Intersection: return nothing
151 // Difference: return first of them
152 if (OverlayType == overlay_intersection
153 || (OverlayType == overlay_difference && geometry::is_empty(geometry1)))
158 #if defined(_MSC_VER)
163 std::map<ring_identifier, ring_turn_info> empty;
164 std::map<ring_identifier, properties> all_of_one_of_them;
166 select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them);
167 ring_container_type rings;
168 assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
169 return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
175 typename Geometry1, typename Geometry2,
176 bool Reverse1, bool Reverse2, bool ReverseOut,
177 typename GeometryOut,
178 overlay_type OverlayType
182 template <typename RobustPolicy, typename OutputIterator, typename Strategy, typename Visitor>
183 static inline OutputIterator apply(
184 Geometry1 const& geometry1, Geometry2 const& geometry2,
185 RobustPolicy const& robust_policy,
190 bool const is_empty1 = geometry::is_empty(geometry1);
191 bool const is_empty2 = geometry::is_empty(geometry2);
193 if (is_empty1 && is_empty2)
198 if (is_empty1 || is_empty2)
200 return return_if_one_input_is_empty
202 GeometryOut, OverlayType, ReverseOut
203 >(geometry1, geometry2, out);
206 typedef typename geometry::point_type<GeometryOut>::type point_type;
207 typedef detail::overlay::traversal_turn_info
210 typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
212 typedef std::deque<turn_info> turn_container_type;
216 typename geometry::ring_type<GeometryOut>::type
217 > ring_container_type;
219 // Define the clusters, mapping cluster_id -> turns
226 turn_container_type turns;
228 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
229 std::cout << "get turns" << std::endl;
231 detail::get_turns::no_interrupt_policy policy;
235 detail::overlay::assign_null_policy
236 >(geometry1, geometry2, robust_policy, turns, policy);
238 visitor.visit_turns(1, turns);
240 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
241 std::cout << "enrich" << std::endl;
243 typename Strategy::side_strategy_type side_strategy;
244 cluster_type clusters;
246 geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
247 clusters, geometry1, geometry2,
251 visitor.visit_turns(2, turns);
253 visitor.visit_clusters(clusters, turns);
255 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
256 std::cout << "traverse" << std::endl;
258 // Traverse through intersection/turn points and create rings of them.
259 // Note that these rings are always in clockwise order, even in CCW polygons,
260 // and are marked as "to be reversed" below
261 ring_container_type rings;
262 traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply
264 geometry1, geometry2,
271 std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
272 get_ring_turn_info(turn_info_per_ring, turns);
274 typedef ring_properties
276 typename geometry::point_type<GeometryOut>::type
279 // Select all rings which are NOT touched by any intersection point
280 std::map<ring_identifier, properties> selected_ring_properties;
281 select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
282 selected_ring_properties);
284 // Add rings created during traversal
286 ring_identifier id(2, 0, -1);
287 for (typename boost::range_iterator<ring_container_type>::type
288 it = boost::begin(rings);
289 it != boost::end(rings);
292 selected_ring_properties[id] = properties(*it);
293 selected_ring_properties[id].reversed = ReverseOut;
298 assign_parents(geometry1, geometry2, rings, selected_ring_properties);
300 return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out);
303 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
304 static inline OutputIterator apply(
305 Geometry1 const& geometry1, Geometry2 const& geometry2,
306 RobustPolicy const& robust_policy,
308 Strategy const& strategy)
310 overlay_null_visitor visitor;
311 return apply(geometry1, geometry2, robust_policy, out, strategy, visitor);
316 }} // namespace detail::overlay
317 #endif // DOXYGEN_NO_DETAIL
320 }} // namespace boost::geometry
323 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP