]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands. | |
11fdf7f2 | 4 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. |
b32b8144 FG |
5 | |
6 | // Use, modification and distribution is subject to the Boost Software License, | |
7 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | ||
10 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP | |
11 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP | |
12 | ||
13 | #include <boost/range.hpp> | |
14 | ||
15 | #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> | |
16 | #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> | |
17 | #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> | |
11fdf7f2 | 18 | #include <boost/geometry/algorithms/covered_by.hpp> |
b32b8144 FG |
19 | #include <boost/geometry/algorithms/within.hpp> |
20 | ||
21 | namespace boost { namespace geometry | |
22 | { | |
23 | ||
24 | #ifndef DOXYGEN_NO_DETAIL | |
25 | namespace detail { namespace overlay | |
26 | { | |
27 | ||
11fdf7f2 TL |
28 | template <overlay_type OverlayType> |
29 | struct check_within | |
30 | { | |
31 | template <typename Turn, typename Geometry0, typename Geometry1> | |
32 | static inline | |
33 | bool apply(Turn const& turn, Geometry0 const& geometry0, | |
34 | Geometry1 const& geometry1) | |
35 | { | |
36 | // Operations 0 and 1 have the same source index in self-turns | |
37 | return turn.operations[0].seg_id.source_index == 0 | |
38 | ? geometry::within(turn.point, geometry1) | |
39 | : geometry::within(turn.point, geometry0); | |
40 | } | |
41 | ||
42 | }; | |
43 | ||
44 | template <> | |
45 | struct check_within<overlay_difference> | |
46 | { | |
47 | template <typename Turn, typename Geometry0, typename Geometry1> | |
48 | static inline | |
49 | bool apply(Turn const& turn, Geometry0 const& geometry0, | |
50 | Geometry1 const& geometry1) | |
51 | { | |
52 | // difference = intersection(a, reverse(b)) | |
53 | // therefore we should reverse the meaning of within for geometry1 | |
54 | return turn.operations[0].seg_id.source_index == 0 | |
55 | ? ! geometry::covered_by(turn.point, geometry1) | |
56 | : geometry::within(turn.point, geometry0); | |
57 | } | |
58 | }; | |
59 | ||
b32b8144 FG |
60 | struct discard_turns |
61 | { | |
62 | template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1> | |
63 | static inline | |
64 | void apply(Turns& , Clusters const& , Geometry0 const& , Geometry1 const& ) | |
65 | {} | |
66 | }; | |
67 | ||
68 | template <overlay_type OverlayType, operation_type OperationType> | |
69 | struct discard_closed_turns : discard_turns {}; | |
70 | ||
71 | // It is only implemented for operation_union, not in buffer | |
72 | template <> | |
73 | struct discard_closed_turns<overlay_union, operation_union> | |
74 | { | |
75 | ||
76 | template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1> | |
77 | static inline | |
11fdf7f2 | 78 | void apply(Turns& turns, Clusters const& /*clusters*/, |
b32b8144 FG |
79 | Geometry0 const& geometry0, Geometry1 const& geometry1) |
80 | { | |
81 | typedef typename boost::range_value<Turns>::type turn_type; | |
82 | ||
83 | for (typename boost::range_iterator<Turns>::type | |
84 | it = boost::begin(turns); | |
85 | it != boost::end(turns); | |
86 | ++it) | |
87 | { | |
88 | turn_type& turn = *it; | |
89 | ||
11fdf7f2 TL |
90 | if (! turn.discarded |
91 | && is_self_turn<overlay_union>(turn) | |
92 | && check_within<overlay_union>::apply(turn, | |
93 | geometry0, geometry1)) | |
b32b8144 | 94 | { |
11fdf7f2 | 95 | // Turn is in the interior of other geometry |
b32b8144 FG |
96 | turn.discarded = true; |
97 | } | |
98 | } | |
99 | } | |
100 | }; | |
101 | ||
11fdf7f2 | 102 | template <overlay_type OverlayType> |
b32b8144 FG |
103 | struct discard_self_intersection_turns |
104 | { | |
105 | private : | |
106 | ||
b32b8144 FG |
107 | template <typename Turns, typename Clusters> |
108 | static inline | |
109 | bool is_self_cluster(signed_size_type cluster_id, | |
110 | const Turns& turns, Clusters const& clusters) | |
111 | { | |
112 | typename Clusters::const_iterator cit = clusters.find(cluster_id); | |
113 | if (cit == clusters.end()) | |
114 | { | |
115 | return false; | |
116 | } | |
117 | ||
118 | cluster_info const& cinfo = cit->second; | |
119 | for (std::set<signed_size_type>::const_iterator it | |
120 | = cinfo.turn_indices.begin(); | |
121 | it != cinfo.turn_indices.end(); ++it) | |
122 | { | |
11fdf7f2 | 123 | if (! is_self_turn<OverlayType>(turns[*it])) |
b32b8144 FG |
124 | { |
125 | return false; | |
126 | } | |
127 | } | |
128 | ||
129 | return true; | |
130 | } | |
131 | ||
b32b8144 FG |
132 | template <typename Turns, typename Clusters, |
133 | typename Geometry0, typename Geometry1> | |
134 | static inline | |
135 | void discard_clusters(Turns& turns, Clusters const& clusters, | |
136 | Geometry0 const& geometry0, Geometry1 const& geometry1) | |
137 | { | |
138 | for (typename Clusters::const_iterator cit = clusters.begin(); | |
139 | cit != clusters.end(); ++cit) | |
140 | { | |
11fdf7f2 | 141 | signed_size_type const cluster_id = cit->first; |
b32b8144 FG |
142 | |
143 | // If there are only self-turns in the cluster, the cluster should | |
144 | // be located within the other geometry, for intersection | |
11fdf7f2 TL |
145 | if (! cit->second.turn_indices.empty() |
146 | && is_self_cluster(cluster_id, turns, clusters)) | |
b32b8144 FG |
147 | { |
148 | cluster_info const& cinfo = cit->second; | |
11fdf7f2 TL |
149 | signed_size_type const index = *cinfo.turn_indices.begin(); |
150 | if (! check_within<OverlayType>::apply(turns[index], | |
151 | geometry0, geometry1)) | |
b32b8144 FG |
152 | { |
153 | // Discard all turns in cluster | |
11fdf7f2 TL |
154 | for (std::set<signed_size_type>::const_iterator sit |
155 | = cinfo.turn_indices.begin(); | |
b32b8144 FG |
156 | sit != cinfo.turn_indices.end(); ++sit) |
157 | { | |
158 | turns[*sit].discarded = true; | |
159 | } | |
160 | } | |
161 | } | |
162 | } | |
163 | } | |
164 | ||
165 | public : | |
166 | ||
167 | template <typename Turns, typename Clusters, | |
168 | typename Geometry0, typename Geometry1> | |
169 | static inline | |
170 | void apply(Turns& turns, Clusters const& clusters, | |
171 | Geometry0 const& geometry0, Geometry1 const& geometry1) | |
172 | { | |
173 | discard_clusters(turns, clusters, geometry0, geometry1); | |
174 | ||
175 | typedef typename boost::range_value<Turns>::type turn_type; | |
176 | ||
177 | for (typename boost::range_iterator<Turns>::type | |
178 | it = boost::begin(turns); | |
179 | it != boost::end(turns); | |
180 | ++it) | |
181 | { | |
182 | turn_type& turn = *it; | |
183 | ||
b32b8144 FG |
184 | // It is a ii self-turn |
185 | // Check if it is within the other geometry | |
11fdf7f2 TL |
186 | if (! turn.discarded |
187 | && is_self_turn<overlay_intersection>(turn) | |
188 | && ! check_within<OverlayType>::apply(turn, geometry0, geometry1)) | |
b32b8144 | 189 | { |
11fdf7f2 TL |
190 | // It is not within another geometry, set it as non startable. |
191 | // It still might be traveled (#case_recursive_boxes_70) | |
192 | turn.operations[0].enriched.startable = false; | |
193 | turn.operations[1].enriched.startable = false; | |
b32b8144 FG |
194 | } |
195 | } | |
196 | } | |
197 | }; | |
198 | ||
11fdf7f2 | 199 | |
b32b8144 FG |
200 | template <overlay_type OverlayType, operation_type OperationType> |
201 | struct discard_open_turns : discard_turns {}; | |
202 | ||
11fdf7f2 | 203 | // Handler for intersection |
b32b8144 FG |
204 | template <> |
205 | struct discard_open_turns<overlay_intersection, operation_intersection> | |
11fdf7f2 | 206 | : discard_self_intersection_turns<overlay_intersection> {}; |
b32b8144 | 207 | |
11fdf7f2 TL |
208 | // Handler for difference, with different meaning of 'within' |
209 | template <> | |
210 | struct discard_open_turns<overlay_difference, operation_intersection> | |
211 | : discard_self_intersection_turns<overlay_difference> {}; | |
b32b8144 FG |
212 | |
213 | }} // namespace detail::overlay | |
214 | #endif //DOXYGEN_NO_DETAIL | |
215 | ||
216 | ||
217 | }} // namespace boost::geometry | |
218 | ||
219 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP |