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             , operation_type for_operation
75             , Geometry1 const& geometry1
76             , Geometry2 const& geometry2
77             , RobustPolicy const& robust_policy
78             , SideStrategy const& strategy)
79         : m_turns(turns)
80         , m_for_operation(for_operation)
81         , m_geometry1(geometry1)
82         , m_geometry2(geometry2)
83         , m_robust_policy(robust_policy)
84         , m_strategy(strategy)
85     {
86     }
87 
88 private :
89 
90     Turns const& m_turns;
91     operation_type m_for_operation;
92     Geometry1 const& m_geometry1;
93     Geometry2 const& m_geometry2;
94     RobustPolicy const& m_robust_policy;
95     SideStrategy const& m_strategy;
96 
97     typedef typename geometry::point_type<Geometry1>::type point_type;
98 
default_orderboost::geometry::detail::overlay::less_by_segment_ratio99     inline bool default_order(Indexed const& left, Indexed const& right) const
100     {
101         // We've nothing to sort on. Take the indexes
102         return left.turn_index < right.turn_index;
103     }
104 
consider_relative_orderboost::geometry::detail::overlay::less_by_segment_ratio105     inline bool consider_relative_order(Indexed const& left,
106                     Indexed const& right) const
107     {
108         point_type pi, pj, ri, rj, si, sj;
109 
110         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
111             left.subject->seg_id,
112             pi, pj);
113         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
114             *left.other_seg_id,
115             ri, rj);
116         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
117             *right.other_seg_id,
118             si, sj);
119 
120         int const side_rj_p = m_strategy.apply(pi, pj, rj);
121         int const side_sj_p = m_strategy.apply(pi, pj, sj);
122 
123         // Put the one turning left (1; right == -1) as last
124         if (side_rj_p != side_sj_p)
125         {
126             return side_rj_p < side_sj_p;
127         }
128 
129         int const side_sj_r = m_strategy.apply(ri, rj, sj);
130         int const side_rj_s = m_strategy.apply(si, sj, rj);
131 
132         // If they both turn left: the most left as last
133         // If they both turn right: this is not relevant, but take also here most left
134         if (side_rj_s != side_sj_r)
135         {
136             return side_rj_s < side_sj_r;
137         }
138 
139         return default_order(left, right);
140     }
141 
142 
143 public :
144 
145     // Note that left/right do NOT correspond to m_geometry1/m_geometry2
146     // but to the "indexed_turn_operation"
operator ()boost::geometry::detail::overlay::less_by_segment_ratio147     inline bool operator()(Indexed const& left, Indexed const& right) const
148     {
149         if (! (left.subject->seg_id == right.subject->seg_id))
150         {
151             return left.subject->seg_id < right.subject->seg_id;
152         }
153 
154         // Both left and right are located on the SAME segment.
155 
156         if (! (left.subject->fraction == right.subject->fraction))
157         {
158             return left.subject->fraction < right.subject->fraction;
159         }
160 
161 
162         typedef typename boost::range_value<Turns>::type turn_type;
163         turn_type const& left_turn = m_turns[left.turn_index];
164         turn_type const& right_turn = m_turns[right.turn_index];
165 
166         // First check "real" intersection (crosses)
167         // -> distance zero due to precision, solve it by sorting
168         if (left_turn.method == method_crosses
169             && right_turn.method == method_crosses)
170         {
171             return consider_relative_order(left, right);
172         }
173 
174         bool const left_both_xx = left_turn.both(operation_blocked);
175         bool const right_both_xx = right_turn.both(operation_blocked);
176         if (left_both_xx && ! right_both_xx)
177         {
178             return true;
179         }
180         if (! left_both_xx && right_both_xx)
181         {
182             return false;
183         }
184 
185         bool const left_both_uu = left_turn.both(operation_union);
186         bool const right_both_uu = right_turn.both(operation_union);
187         if (left_both_uu && ! right_both_uu)
188         {
189             return true;
190         }
191         if (! left_both_uu && right_both_uu)
192         {
193             return false;
194         }
195 
196         return default_order(left, right);
197     }
198 };
199 
200 
201 }} // namespace detail::overlay
202 #endif //DOXYGEN_NO_DETAIL
203 
204 
205 }} // namespace boost::geometry
206 
207 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
208