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 2017.
6 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
7 
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9 
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
13 
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
16 
17 #include <cstddef>
18 #include <algorithm>
19 #include <map>
20 #include <set>
21 #include <vector>
22 
23 #include <boost/range.hpp>
24 
25 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
27 #include <boost/geometry/strategies/side.hpp>
28 
29 namespace boost { namespace geometry
30 {
31 
32 #ifndef DOXYGEN_NO_DETAIL
33 namespace detail { namespace overlay
34 {
35 
36 // Wraps "turn_operation" from turn_info.hpp,
37 // giving it extra information, necessary for sorting
38 template <typename TurnOperation>
39 struct indexed_turn_operation
40 {
41     typedef TurnOperation type;
42 
43     std::size_t turn_index;
44     std::size_t operation_index;
45     bool skip;
46     // use pointers to avoid copies, const& is not possible because of usage in vector
47     segment_identifier const* other_seg_id; // segment id of other segment of intersection of two segments
48     TurnOperation const* subject;
49 
indexed_turn_operationboost::geometry::detail::overlay::indexed_turn_operation50     inline indexed_turn_operation(std::size_t ti, std::size_t oi,
51                 TurnOperation const& sub,
52                 segment_identifier const& oid)
53         : turn_index(ti)
54         , operation_index(oi)
55         , skip(false)
56         , other_seg_id(&oid)
57         , subject(boost::addressof(sub))
58     {}
59 
60 };
61 
62 template
63 <
64     typename Turns,
65     typename Indexed,
66     typename Geometry1, typename Geometry2,
67     typename RobustPolicy,
68     typename SideStrategy,
69     bool Reverse1, bool Reverse2
70 >
71 struct less_by_segment_ratio
72 {
less_by_segment_ratioboost::geometry::detail::overlay::less_by_segment_ratio73     inline less_by_segment_ratio(Turns const& turns
74             , Geometry1 const& geometry1
75             , Geometry2 const& geometry2
76             , RobustPolicy const& robust_policy
77             , SideStrategy const& strategy)
78         : m_turns(turns)
79         , m_geometry1(geometry1)
80         , m_geometry2(geometry2)
81         , m_robust_policy(robust_policy)
82         , m_strategy(strategy)
83     {
84     }
85 
86 private :
87 
88     Turns const& m_turns;
89     Geometry1 const& m_geometry1;
90     Geometry2 const& m_geometry2;
91     RobustPolicy const& m_robust_policy;
92     SideStrategy const& m_strategy;
93 
94     typedef typename geometry::point_type<Geometry1>::type point_type;
95 
default_orderboost::geometry::detail::overlay::less_by_segment_ratio96     inline bool default_order(Indexed const& left, Indexed const& right) const
97     {
98         // We've nothing to sort on. Take the indexes
99         return left.turn_index < right.turn_index;
100     }
101 
consider_relative_orderboost::geometry::detail::overlay::less_by_segment_ratio102     inline bool consider_relative_order(Indexed const& left,
103                     Indexed const& right) const
104     {
105         point_type pi, pj, ri, rj, si, sj;
106 
107         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
108             left.subject->seg_id,
109             pi, pj);
110         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
111             *left.other_seg_id,
112             ri, rj);
113         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
114             *right.other_seg_id,
115             si, sj);
116 
117         int const side_rj_p = m_strategy.apply(pi, pj, rj);
118         int const side_sj_p = m_strategy.apply(pi, pj, sj);
119 
120         // Put the one turning left (1; right == -1) as last
121         if (side_rj_p != side_sj_p)
122         {
123             return side_rj_p < side_sj_p;
124         }
125 
126         int const side_sj_r = m_strategy.apply(ri, rj, sj);
127         int const side_rj_s = m_strategy.apply(si, sj, rj);
128 
129         // If they both turn left: the most left as last
130         // If they both turn right: this is not relevant, but take also here most left
131         if (side_rj_s != side_sj_r)
132         {
133             return side_rj_s < side_sj_r;
134         }
135 
136         return default_order(left, right);
137     }
138 
139 
140 public :
141 
142     // Note that left/right do NOT correspond to m_geometry1/m_geometry2
143     // but to the "indexed_turn_operation"
operator ()boost::geometry::detail::overlay::less_by_segment_ratio144     inline bool operator()(Indexed const& left, Indexed const& right) const
145     {
146         if (! (left.subject->seg_id == right.subject->seg_id))
147         {
148             return left.subject->seg_id < right.subject->seg_id;
149         }
150 
151         // Both left and right are located on the SAME segment.
152 
153         if (! (left.subject->fraction == right.subject->fraction))
154         {
155             return left.subject->fraction < right.subject->fraction;
156         }
157 
158 
159         typedef typename boost::range_value<Turns>::type turn_type;
160         turn_type const& left_turn = m_turns[left.turn_index];
161         turn_type const& right_turn = m_turns[right.turn_index];
162 
163         // First check "real" intersection (crosses)
164         // -> distance zero due to precision, solve it by sorting
165         if (left_turn.method == method_crosses
166             && right_turn.method == method_crosses)
167         {
168             return consider_relative_order(left, right);
169         }
170 
171         bool const left_both_xx = left_turn.both(operation_blocked);
172         bool const right_both_xx = right_turn.both(operation_blocked);
173         if (left_both_xx && ! right_both_xx)
174         {
175             return true;
176         }
177         if (! left_both_xx && right_both_xx)
178         {
179             return false;
180         }
181 
182         bool const left_both_uu = left_turn.both(operation_union);
183         bool const right_both_uu = right_turn.both(operation_union);
184         if (left_both_uu && ! right_both_uu)
185         {
186             return true;
187         }
188         if (! left_both_uu && right_both_uu)
189         {
190             return false;
191         }
192 
193         return default_order(left, right);
194     }
195 };
196 
197 
198 }} // namespace detail::overlay
199 #endif //DOXYGEN_NO_DETAIL
200 
201 
202 }} // namespace boost::geometry
203 
204 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
205