1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2017 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // Use, modification and distribution is subject to the Boost Software License,
6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP
11
12 #include <cstddef>
13 #include <vector>
14
15 #include <boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp>
16 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
17
18 namespace boost { namespace geometry
19 {
20
21 #ifndef DOXYGEN_NO_DETAIL
22 namespace detail { namespace overlay
23 {
24
check_pairs(std::vector<sort_by_side::rank_with_rings> const & aggregation,signed_size_type incoming_region_id,std::size_t first,std::size_t last)25 inline bool check_pairs(std::vector<sort_by_side::rank_with_rings> const& aggregation,
26 signed_size_type incoming_region_id,
27 std::size_t first, std::size_t last)
28 {
29 // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
30
31 for (std::size_t i = first; i <= last; i += 2)
32 {
33 sort_by_side::rank_with_rings const& curr = aggregation[i];
34 sort_by_side::rank_with_rings const& next = aggregation[i + 1];
35 int const curr_id = curr.region_id();
36 int const next_id = next.region_id();
37
38 bool const possible =
39 curr.rings.size() == 2
40 && curr.is_isolated()
41 && curr.has_unique_region_id()
42 && next.rings.size() == 2
43 && next.is_isolated()
44 && next.has_unique_region_id()
45 && curr_id == next_id
46 && curr_id != incoming_region_id;
47
48 if (! possible)
49 {
50 return false;
51 }
52 }
53
54 return true;
55 }
56
intersection_pattern_common_interior1(std::size_t & selected_rank,std::vector<sort_by_side::rank_with_rings> const & aggregation)57 inline bool intersection_pattern_common_interior1(std::size_t& selected_rank,
58 std::vector<sort_by_side::rank_with_rings> const& aggregation)
59 {
60 // Pattern: coming from exterior ring, encountering an isolated
61 // parallel interior ring, which should be skipped, and the first
62 // left (normally intersection takes first right) should be taken.
63 // Solves cases #case_133_multi
64 // and #case_recursive_boxes_49
65
66 std::size_t const n = aggregation.size();
67 if (n < 4)
68 {
69 return false;
70 }
71
72 sort_by_side::rank_with_rings const& incoming = aggregation.front();
73 sort_by_side::rank_with_rings const& outgoing = aggregation.back();
74
75 bool const incoming_ok =
76 incoming.all_from()
77 && incoming.rings.size() == 1
78 && incoming.has_only(operation_intersection);
79
80 if (! incoming_ok)
81 {
82 return false;
83 }
84
85 bool const outgoing_ok =
86 outgoing.all_to()
87 && outgoing.rings.size() == 1
88 && outgoing.has_only(operation_intersection)
89 && outgoing.region_id() == incoming.region_id();
90
91 if (! outgoing_ok)
92 {
93 return false;
94 }
95
96 if (check_pairs(aggregation, incoming.region_id(), 1, n - 2))
97 {
98 selected_rank = n - 1;
99 return true;
100 }
101 return false;
102 }
103
intersection_pattern_common_interior2(std::size_t & selected_rank,std::vector<sort_by_side::rank_with_rings> const & aggregation)104 inline bool intersection_pattern_common_interior2(std::size_t& selected_rank,
105 std::vector<sort_by_side::rank_with_rings> const& aggregation)
106 {
107 // Pattern: coming from two exterior rings, encountering two isolated
108 // equal interior rings
109
110 // See (for example, for ii) #case_recursive_boxes_53:
111
112 // INCOMING:
113 // Rank 0 {11[0] (s:0, m:0) i F rgn: 1 ISO} {13[1] (s:1, m:0) i F rgn: 1 ISO}
114
115 // PAIR:
116 // Rank 1 {13[0] (s:0, r:1, m:0) i T rgn: 3 ISO ->16} {11[1] (s:1, r:5, m:0) i T rgn: 3 ISO ->16}
117 // Rank 2 {13[0] (s:0, r:1, m:0) i F rgn: 3 ISO} {11[1] (s:1, r:5, m:0) i F rgn: 3 ISO}
118
119 // LEAVING (in the same direction, take last one)
120 // Rank 3 {11[0] (s:0, m:0) i T rgn: 1 ISO ->10} {13[1] (s:1, m:0) i T rgn: 1 ISO ->10}
121
122
123 std::size_t const n = aggregation.size();
124 if (n < 4)
125 {
126 return false;
127 }
128
129 sort_by_side::rank_with_rings const& incoming = aggregation.front();
130 sort_by_side::rank_with_rings const& outgoing = aggregation.back();
131
132 bool const incoming_ok =
133 incoming.all_from()
134 && incoming.rings.size() == 2
135 && incoming.has_unique_region_id();
136
137 if (! incoming_ok)
138 {
139 return false;
140 }
141
142 bool const outgoing_ok =
143 outgoing.all_to()
144 && outgoing.rings.size() == 2
145 && outgoing.has_unique_region_id()
146 && outgoing.region_id() == incoming.region_id();
147
148 if (! outgoing_ok)
149 {
150 return false;
151 }
152
153 bool const operation_ok =
154 (incoming.has_only(operation_continue) && outgoing.has_only(operation_continue))
155 || (incoming.has_only(operation_intersection) && outgoing.has_only(operation_intersection));
156
157 if (! operation_ok)
158 {
159 return false;
160 }
161
162 // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
163 if (check_pairs(aggregation, incoming.region_id(), 1, n - 2))
164 {
165 selected_rank = n - 1;
166 return true;
167 }
168 return false;
169 }
170
intersection_pattern_common_interior3(std::size_t & selected_rank,std::vector<sort_by_side::rank_with_rings> const & aggregation)171 inline bool intersection_pattern_common_interior3(std::size_t& selected_rank,
172 std::vector<sort_by_side::rank_with_rings> const& aggregation)
173 {
174 // Pattern: approaches colocated turn (exterior+interior) from two
175 // different directions, and both leaves in the same direction
176
177 // See #case_136_multi:
178 // INCOMING:
179 //Rank 0 {10[0] (s:0, m:0) c F rgn: 1 ISO}
180
181 // PAIR:
182 //Rank 1 {14[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->16} {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->16}
183 //Rank 2 {14[0] (s:0, r:0, m:0) i F rgn: 2 ISO} {11[1] (s:1, r:1, m:0) i F rgn: 2 ISO}
184
185 // LEAVING (select this one):
186 //Rank 3 {10[0] (s:0, m:0) c T rgn: 1 ISO ->12} {10[1] (s:1, m:0) c T rgn: 1 ISO ->12}
187
188 // ADDITIONALLY: (other polygon coming in)
189 //Rank 4 {10[1] (s:1, m:0) c F rgn: 1 ISO}
190
191 std::size_t const n = aggregation.size();
192 if (n < 4)
193 {
194 return false;
195 }
196
197 sort_by_side::rank_with_rings const& incoming = aggregation.front();
198 sort_by_side::rank_with_rings const& outgoing = aggregation[n - 2];
199 sort_by_side::rank_with_rings const& last = aggregation.back();
200
201 bool const incoming_ok =
202 incoming.all_from()
203 && incoming.rings.size() == 1
204 && incoming.has_only(operation_continue);
205
206 if (! incoming_ok)
207 {
208 return false;
209 }
210
211 bool const outgoing_ok =
212 outgoing.all_to()
213 && outgoing.rings.size() == 2
214 && outgoing.has_only(operation_continue)
215 && outgoing.has_unique_region_id()
216 && outgoing.region_id() == incoming.region_id()
217 && last.all_from()
218 && last.rings.size() == 1
219 && last.region_id() == incoming.region_id()
220 && last.all_from();
221
222 if (! outgoing_ok)
223 {
224 return false;
225 }
226
227 // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
228 if (check_pairs(aggregation, incoming.region_id(), 1, n - 3))
229 {
230 selected_rank = n - 2;
231 return true;
232 }
233 return false;
234 }
235
236
intersection_pattern_common_interior4(std::size_t & selected_rank,std::vector<sort_by_side::rank_with_rings> const & aggregation)237 inline bool intersection_pattern_common_interior4(std::size_t& selected_rank,
238 std::vector<sort_by_side::rank_with_rings> const& aggregation)
239 {
240 // Pattern: approaches colocated turn (exterior+interior) from same
241 // direction, but leaves in two different directions
242
243 // See #case_137_multi:
244
245 // INCOMING:
246 //Rank 0 {11[0] (s:0, m:0) i F rgn: 1 ISO} {10[1] (s:1, m:0) i F rgn: 1 ISO}
247
248 // PAIR:
249 //Rank 1 {13[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->15} {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->15}
250 //Rank 2 {13[0] (s:0, r:0, m:0) i F rgn: 2 ISO} {11[1] (s:1, r:1, m:0) i F rgn: 2 ISO}
251
252 // LEAVING (in two different directions, take last one)
253 //Rank 3 {10[1] (s:1, m:0) i T rgn: 1 ISO ->0}
254 //Rank 4 {11[0] (s:0, m:0) i T rgn: 1 ISO ->12}
255
256 std::size_t const n = aggregation.size();
257 if (n < 4)
258 {
259 return false;
260 }
261
262 sort_by_side::rank_with_rings const& incoming = aggregation.front();
263 sort_by_side::rank_with_rings const& extra = aggregation[n - 2];
264 sort_by_side::rank_with_rings const& outgoing = aggregation.back();
265
266 bool const incoming_ok =
267 incoming.all_from()
268 && incoming.rings.size() == 2
269 && incoming.has_unique_region_id()
270 && incoming.has_only(operation_intersection);
271
272 if (! incoming_ok)
273 {
274 return false;
275 }
276
277 bool const outgoing_ok =
278 outgoing.all_to()
279 && outgoing.rings.size() == 1
280 && outgoing.has_only(operation_intersection)
281 && outgoing.region_id() == incoming.region_id()
282 && extra.all_to()
283 && extra.rings.size() == 1
284 && extra.has_only(operation_intersection)
285 && extra.region_id() == incoming.region_id();
286
287 if (! outgoing_ok)
288 {
289 return false;
290 }
291
292 // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
293 if (check_pairs(aggregation, incoming.region_id(), 1, n - 3))
294 {
295 selected_rank = n - 1;
296 return true;
297 }
298 return false;
299 }
300
301 }} // namespace detail::overlay
302 #endif // DOXYGEN_NO_DETAIL
303
304 }} // namespace boost::geometry
305
306 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP
307