]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
5 | // This file was modified by Oracle on 2013, 2014, 2015. | |
6 | // Modifications copyright (c) 2013-2015 Oracle and/or its affiliates. | |
7 | ||
8 | // Use, modification and distribution is subject to the Boost Software License, | |
9 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
10 | // http://www.boost.org/LICENSE_1_0.txt) | |
11 | ||
12 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
13 | ||
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP | |
16 | ||
17 | #include <algorithm> | |
18 | ||
19 | #include <boost/core/ignore_unused.hpp> | |
20 | #include <boost/range/size.hpp> | |
21 | ||
22 | #include <boost/geometry/core/assert.hpp> | |
23 | ||
24 | #include <boost/geometry/util/condition.hpp> | |
25 | #include <boost/geometry/util/range.hpp> | |
26 | ||
27 | #include <boost/geometry/algorithms/detail/sub_range.hpp> | |
28 | #include <boost/geometry/algorithms/detail/single_geometry.hpp> | |
29 | ||
30 | #include <boost/geometry/algorithms/detail/relate/point_geometry.hpp> | |
31 | #include <boost/geometry/algorithms/detail/relate/result.hpp> | |
32 | #include <boost/geometry/algorithms/detail/relate/turns.hpp> | |
33 | #include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp> | |
34 | #include <boost/geometry/algorithms/detail/relate/follow_helpers.hpp> | |
35 | ||
36 | namespace boost { namespace geometry | |
37 | { | |
38 | ||
39 | #ifndef DOXYGEN_NO_DETAIL | |
40 | namespace detail { namespace relate { | |
41 | ||
42 | template <typename Result, typename BoundaryChecker, bool TransposeResult> | |
43 | class disjoint_linestring_pred | |
44 | { | |
45 | public: | |
46 | disjoint_linestring_pred(Result & res, | |
47 | BoundaryChecker const& boundary_checker) | |
48 | : m_result(res) | |
49 | , m_boundary_checker(boundary_checker) | |
50 | , m_flags(0) | |
51 | { | |
52 | if ( ! may_update<interior, exterior, '1', TransposeResult>(m_result) ) | |
53 | { | |
54 | m_flags |= 1; | |
55 | } | |
56 | if ( ! may_update<boundary, exterior, '0', TransposeResult>(m_result) ) | |
57 | { | |
58 | m_flags |= 2; | |
59 | } | |
60 | } | |
61 | ||
62 | template <typename Linestring> | |
63 | bool operator()(Linestring const& linestring) | |
64 | { | |
65 | if ( m_flags == 3 ) | |
66 | { | |
67 | return false; | |
68 | } | |
69 | ||
70 | std::size_t const count = boost::size(linestring); | |
71 | ||
72 | // invalid input | |
73 | if ( count < 2 ) | |
74 | { | |
75 | // ignore | |
76 | // TODO: throw an exception? | |
77 | return true; | |
78 | } | |
79 | ||
80 | // point-like linestring | |
81 | if ( count == 2 | |
82 | && equals::equals_point_point(range::front(linestring), | |
83 | range::back(linestring)) ) | |
84 | { | |
85 | update<interior, exterior, '0', TransposeResult>(m_result); | |
86 | } | |
87 | else | |
88 | { | |
89 | update<interior, exterior, '1', TransposeResult>(m_result); | |
90 | m_flags |= 1; | |
91 | ||
92 | // check if there is a boundary | |
93 | if ( m_flags < 2 | |
94 | && ( m_boundary_checker.template | |
95 | is_endpoint_boundary<boundary_front>(range::front(linestring)) | |
96 | || m_boundary_checker.template | |
97 | is_endpoint_boundary<boundary_back>(range::back(linestring)) ) ) | |
98 | { | |
99 | update<boundary, exterior, '0', TransposeResult>(m_result); | |
100 | m_flags |= 2; | |
101 | } | |
102 | } | |
103 | ||
104 | return m_flags != 3 | |
105 | && ! m_result.interrupt; | |
106 | } | |
107 | ||
108 | private: | |
109 | Result & m_result; | |
110 | BoundaryChecker const& m_boundary_checker; | |
111 | unsigned m_flags; | |
112 | }; | |
113 | ||
114 | template <typename Geometry1, typename Geometry2> | |
115 | struct linear_linear | |
116 | { | |
117 | static const bool interruption_enabled = true; | |
118 | ||
119 | typedef typename geometry::point_type<Geometry1>::type point1_type; | |
120 | typedef typename geometry::point_type<Geometry2>::type point2_type; | |
121 | ||
122 | template <typename Result> | |
123 | static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Result & result) | |
124 | { | |
125 | // The result should be FFFFFFFFF | |
126 | relate::set<exterior, exterior, result_dimension<Geometry1>::value>(result);// FFFFFFFFd, d in [1,9] or T | |
127 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
128 | return; | |
129 | ||
130 | // get and analyse turns | |
131 | typedef typename turns::get_turns<Geometry1, Geometry2>::turn_info turn_type; | |
132 | std::vector<turn_type> turns; | |
133 | ||
134 | interrupt_policy_linear_linear<Result> interrupt_policy(result); | |
135 | ||
136 | turns::get_turns | |
137 | < | |
138 | Geometry1, | |
139 | Geometry2, | |
140 | detail::get_turns::get_turn_info_type<Geometry1, Geometry2, turns::assign_policy<true> > | |
141 | >::apply(turns, geometry1, geometry2, interrupt_policy); | |
142 | ||
143 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
144 | return; | |
145 | ||
146 | boundary_checker<Geometry1> boundary_checker1(geometry1); | |
147 | disjoint_linestring_pred<Result, boundary_checker<Geometry1>, false> pred1(result, boundary_checker1); | |
148 | for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1); | |
149 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
150 | return; | |
151 | ||
152 | boundary_checker<Geometry2> boundary_checker2(geometry2); | |
153 | disjoint_linestring_pred<Result, boundary_checker<Geometry2>, true> pred2(result, boundary_checker2); | |
154 | for_each_disjoint_geometry_if<1, Geometry2>::apply(turns.begin(), turns.end(), geometry2, pred2); | |
155 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
156 | return; | |
157 | ||
158 | if ( turns.empty() ) | |
159 | return; | |
160 | ||
161 | // TODO: turns must be sorted and followed only if it's possible to go out and in on the same point | |
162 | // for linear geometries union operation must be detected which I guess would be quite often | |
163 | ||
164 | if ( may_update<interior, interior, '1'>(result) | |
165 | || may_update<interior, boundary, '0'>(result) | |
166 | || may_update<interior, exterior, '1'>(result) | |
167 | || may_update<boundary, interior, '0'>(result) | |
168 | || may_update<boundary, boundary, '0'>(result) | |
169 | || may_update<boundary, exterior, '0'>(result) ) | |
170 | { | |
171 | typedef turns::less<0, turns::less_op_linear_linear<0> > less; | |
172 | std::sort(turns.begin(), turns.end(), less()); | |
173 | ||
174 | turns_analyser<turn_type, 0> analyser; | |
175 | analyse_each_turn(result, analyser, | |
176 | turns.begin(), turns.end(), | |
177 | geometry1, geometry2, | |
178 | boundary_checker1, boundary_checker2); | |
179 | } | |
180 | ||
181 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
182 | return; | |
183 | ||
184 | if ( may_update<interior, interior, '1', true>(result) | |
185 | || may_update<interior, boundary, '0', true>(result) | |
186 | || may_update<interior, exterior, '1', true>(result) | |
187 | || may_update<boundary, interior, '0', true>(result) | |
188 | || may_update<boundary, boundary, '0', true>(result) | |
189 | || may_update<boundary, exterior, '0', true>(result) ) | |
190 | { | |
191 | typedef turns::less<1, turns::less_op_linear_linear<1> > less; | |
192 | std::sort(turns.begin(), turns.end(), less()); | |
193 | ||
194 | turns_analyser<turn_type, 1> analyser; | |
195 | analyse_each_turn(result, analyser, | |
196 | turns.begin(), turns.end(), | |
197 | geometry2, geometry1, | |
198 | boundary_checker2, boundary_checker1); | |
199 | } | |
200 | } | |
201 | ||
202 | template <typename Result> | |
203 | class interrupt_policy_linear_linear | |
204 | { | |
205 | public: | |
206 | static bool const enabled = true; | |
207 | ||
208 | explicit interrupt_policy_linear_linear(Result & result) | |
209 | : m_result(result) | |
210 | {} | |
211 | ||
212 | // TODO: since we update result for some operations here, we may not do it in the analyser! | |
213 | ||
214 | template <typename Range> | |
215 | inline bool apply(Range const& turns) | |
216 | { | |
217 | typedef typename boost::range_iterator<Range const>::type iterator; | |
218 | ||
219 | for (iterator it = boost::begin(turns) ; it != boost::end(turns) ; ++it) | |
220 | { | |
221 | if ( it->operations[0].operation == overlay::operation_intersection | |
222 | || it->operations[1].operation == overlay::operation_intersection ) | |
223 | { | |
224 | update<interior, interior, '1'>(m_result); | |
225 | } | |
226 | else if ( ( it->operations[0].operation == overlay::operation_union | |
227 | || it->operations[0].operation == overlay::operation_blocked | |
228 | || it->operations[1].operation == overlay::operation_union | |
229 | || it->operations[1].operation == overlay::operation_blocked ) | |
230 | && it->operations[0].position == overlay::position_middle | |
231 | && it->operations[1].position == overlay::position_middle ) | |
232 | { | |
233 | // TODO: here we could also check the boundaries and set IB,BI,BB at this point | |
234 | update<interior, interior, '0'>(m_result); | |
235 | } | |
236 | } | |
237 | ||
238 | return m_result.interrupt; | |
239 | } | |
240 | ||
241 | private: | |
242 | Result & m_result; | |
243 | }; | |
244 | ||
245 | // This analyser should be used like Input or SinglePass Iterator | |
246 | template <typename TurnInfo, std::size_t OpId> | |
247 | class turns_analyser | |
248 | { | |
249 | typedef typename TurnInfo::point_type turn_point_type; | |
250 | ||
251 | static const std::size_t op_id = OpId; | |
252 | static const std::size_t other_op_id = (OpId + 1) % 2; | |
253 | static const bool transpose_result = OpId != 0; | |
254 | ||
255 | public: | |
256 | turns_analyser() | |
257 | : m_previous_turn_ptr(NULL) | |
258 | , m_previous_operation(overlay::operation_none) | |
259 | , m_degenerated_turn_ptr(NULL) | |
260 | , m_collinear_spike_exit(false) | |
261 | {} | |
262 | ||
263 | template <typename Result, | |
264 | typename TurnIt, | |
265 | typename Geometry, | |
266 | typename OtherGeometry, | |
267 | typename BoundaryChecker, | |
268 | typename OtherBoundaryChecker> | |
269 | void apply(Result & res, TurnIt it, | |
270 | Geometry const& geometry, | |
271 | OtherGeometry const& other_geometry, | |
272 | BoundaryChecker const& boundary_checker, | |
273 | OtherBoundaryChecker const& other_boundary_checker) | |
274 | { | |
275 | overlay::operation_type const op = it->operations[op_id].operation; | |
276 | ||
277 | segment_identifier const& seg_id = it->operations[op_id].seg_id; | |
278 | segment_identifier const& other_id = it->operations[other_op_id].seg_id; | |
279 | ||
280 | bool const first_in_range = m_seg_watcher.update(seg_id); | |
281 | ||
282 | if ( op != overlay::operation_union | |
283 | && op != overlay::operation_intersection | |
284 | && op != overlay::operation_blocked ) | |
285 | { | |
286 | // degenerated turn | |
287 | if ( op == overlay::operation_continue | |
288 | && it->method == overlay::method_none | |
289 | && m_exit_watcher.is_outside(*it) | |
290 | /*&& ( m_exit_watcher.get_exit_operation() == overlay::operation_none | |
291 | || ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), *it) )*/ ) | |
292 | { | |
293 | // TODO: rewrite the above condition | |
294 | ||
295 | // WARNING! For spikes the above condition may be TRUE | |
296 | // When degenerated turns are be marked in a different way than c,c/c | |
297 | // different condition will be checked | |
298 | ||
299 | handle_degenerated(res, *it, | |
300 | geometry, other_geometry, | |
301 | boundary_checker, other_boundary_checker, | |
302 | first_in_range); | |
303 | ||
304 | // TODO: not elegant solution! should be rewritten. | |
305 | if ( it->operations[op_id].position == overlay::position_back ) | |
306 | { | |
307 | m_previous_operation = overlay::operation_blocked; | |
308 | m_exit_watcher.reset_detected_exit(); | |
309 | } | |
310 | } | |
311 | ||
312 | return; | |
313 | } | |
314 | ||
315 | // reset | |
316 | m_degenerated_turn_ptr = NULL; | |
317 | ||
318 | // handle possible exit | |
319 | bool fake_enter_detected = false; | |
320 | if ( m_exit_watcher.get_exit_operation() == overlay::operation_union ) | |
321 | { | |
322 | // real exit point - may be multiple | |
323 | // we know that we entered and now we exit | |
324 | if ( ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), *it) ) | |
325 | { | |
326 | m_exit_watcher.reset_detected_exit(); | |
327 | ||
328 | // not the last IP | |
329 | update<interior, exterior, '1', transpose_result>(res); | |
330 | } | |
331 | // fake exit point, reset state | |
332 | else if ( op == overlay::operation_intersection ) | |
333 | { | |
334 | m_exit_watcher.reset_detected_exit(); | |
335 | fake_enter_detected = true; | |
336 | } | |
337 | } | |
338 | else if ( m_exit_watcher.get_exit_operation() == overlay::operation_blocked ) | |
339 | { | |
340 | // ignore multiple BLOCKs | |
341 | if ( op == overlay::operation_blocked ) | |
342 | return; | |
343 | ||
344 | if ( op == overlay::operation_intersection | |
345 | && turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), *it) ) | |
346 | { | |
347 | fake_enter_detected = true; | |
348 | } | |
349 | ||
350 | m_exit_watcher.reset_detected_exit(); | |
351 | } | |
352 | ||
353 | // i/i, i/x, i/u | |
354 | if ( op == overlay::operation_intersection ) | |
355 | { | |
356 | bool const was_outside = m_exit_watcher.is_outside(); | |
357 | m_exit_watcher.enter(*it); | |
358 | ||
359 | // interiors overlaps | |
360 | update<interior, interior, '1', transpose_result>(res); | |
361 | ||
362 | bool const this_b = it->operations[op_id].position == overlay::position_front // ignore spikes! | |
363 | && is_ip_on_boundary<boundary_front>(it->point, | |
364 | it->operations[op_id], | |
365 | boundary_checker, | |
366 | seg_id); | |
367 | ||
368 | // going inside on boundary point | |
369 | // may be front only | |
370 | if ( this_b ) | |
371 | { | |
372 | // may be front and back | |
373 | bool const other_b = is_ip_on_boundary<boundary_any>(it->point, | |
374 | it->operations[other_op_id], | |
375 | other_boundary_checker, | |
376 | other_id); | |
377 | ||
378 | // it's also the boundary of the other geometry | |
379 | if ( other_b ) | |
380 | { | |
381 | update<boundary, boundary, '0', transpose_result>(res); | |
382 | } | |
383 | else | |
384 | { | |
385 | update<boundary, interior, '0', transpose_result>(res); | |
386 | } | |
387 | } | |
388 | // going inside on non-boundary point | |
389 | else | |
390 | { | |
391 | // if we didn't enter in the past, we were outside | |
392 | if ( was_outside | |
393 | && ! fake_enter_detected | |
394 | && it->operations[op_id].position != overlay::position_front | |
395 | && ! m_collinear_spike_exit ) | |
396 | { | |
397 | update<interior, exterior, '1', transpose_result>(res); | |
398 | ||
399 | // if it's the first IP then the first point is outside | |
400 | if ( first_in_range ) | |
401 | { | |
402 | bool const front_b = is_endpoint_on_boundary<boundary_front>( | |
403 | range::front(sub_range(geometry, seg_id)), | |
404 | boundary_checker); | |
405 | ||
406 | // if there is a boundary on the first point | |
407 | if ( front_b ) | |
408 | { | |
409 | update<boundary, exterior, '0', transpose_result>(res); | |
410 | } | |
411 | } | |
412 | } | |
413 | } | |
414 | ||
415 | m_collinear_spike_exit = false; | |
416 | } | |
417 | // u/i, u/u, u/x, x/i, x/u, x/x | |
418 | else if ( op == overlay::operation_union || op == overlay::operation_blocked ) | |
419 | { | |
420 | // TODO: is exit watcher still needed? | |
421 | // couldn't is_collinear and some going inside counter be used instead? | |
422 | ||
423 | bool const is_collinear = it->operations[op_id].is_collinear; | |
424 | bool const was_outside = m_exit_watcher.is_outside() | |
425 | && m_exit_watcher.get_exit_operation() == overlay::operation_none; | |
426 | // TODO: move the above condition into the exit_watcher? | |
427 | ||
428 | // to exit we must be currently inside and the current segment must be collinear | |
429 | if ( !was_outside && is_collinear ) | |
430 | { | |
431 | m_exit_watcher.exit(*it, false); | |
432 | // if the position is not set to back it must be a spike | |
433 | if ( it->operations[op_id].position != overlay::position_back ) | |
434 | { | |
435 | m_collinear_spike_exit = true; | |
436 | } | |
437 | } | |
438 | ||
439 | bool const op_blocked = op == overlay::operation_blocked; | |
440 | ||
441 | // we're inside and going out from inside | |
442 | // possibly going out right now | |
443 | if ( ! was_outside && is_collinear ) | |
444 | { | |
445 | if ( op_blocked | |
446 | && it->operations[op_id].position == overlay::position_back ) // ignore spikes! | |
447 | { | |
448 | // check if this is indeed the boundary point | |
449 | // NOTE: is_ip_on_boundary<>() should be called here but the result will be the same | |
450 | if ( is_endpoint_on_boundary<boundary_back>(it->point, boundary_checker) ) | |
451 | { | |
452 | // may be front and back | |
453 | bool const other_b = is_ip_on_boundary<boundary_any>(it->point, | |
454 | it->operations[other_op_id], | |
455 | other_boundary_checker, | |
456 | other_id); | |
457 | // it's also the boundary of the other geometry | |
458 | if ( other_b ) | |
459 | { | |
460 | update<boundary, boundary, '0', transpose_result>(res); | |
461 | } | |
462 | else | |
463 | { | |
464 | update<boundary, interior, '0', transpose_result>(res); | |
465 | } | |
466 | } | |
467 | } | |
468 | } | |
469 | // we're outside or intersects some segment from the outside | |
470 | else | |
471 | { | |
472 | // if we are truly outside | |
473 | if ( was_outside | |
474 | && it->operations[op_id].position != overlay::position_front | |
475 | && ! m_collinear_spike_exit | |
476 | /*&& !is_collinear*/ ) | |
477 | { | |
478 | update<interior, exterior, '1', transpose_result>(res); | |
479 | } | |
480 | ||
481 | // boundaries don't overlap - just an optimization | |
482 | if ( it->method == overlay::method_crosses ) | |
483 | { | |
484 | // the L1 is going from one side of the L2 to the other through the point | |
485 | update<interior, interior, '0', transpose_result>(res); | |
486 | ||
487 | // it's the first point in range | |
488 | if ( first_in_range ) | |
489 | { | |
490 | bool const front_b = is_endpoint_on_boundary<boundary_front>( | |
491 | range::front(sub_range(geometry, seg_id)), | |
492 | boundary_checker); | |
493 | ||
494 | // if there is a boundary on the first point | |
495 | if ( front_b ) | |
496 | { | |
497 | update<boundary, exterior, '0', transpose_result>(res); | |
498 | } | |
499 | } | |
500 | } | |
501 | // method other than crosses, check more conditions | |
502 | else | |
503 | { | |
504 | bool const this_b = is_ip_on_boundary<boundary_any>(it->point, | |
505 | it->operations[op_id], | |
506 | boundary_checker, | |
507 | seg_id); | |
508 | ||
509 | bool const other_b = is_ip_on_boundary<boundary_any>(it->point, | |
510 | it->operations[other_op_id], | |
511 | other_boundary_checker, | |
512 | other_id); | |
513 | ||
514 | // if current IP is on boundary of the geometry | |
515 | if ( this_b ) | |
516 | { | |
517 | // it's also the boundary of the other geometry | |
518 | if ( other_b ) | |
519 | { | |
520 | update<boundary, boundary, '0', transpose_result>(res); | |
521 | } | |
522 | else | |
523 | { | |
524 | update<boundary, interior, '0', transpose_result>(res); | |
525 | } | |
526 | } | |
527 | // if current IP is not on boundary of the geometry | |
528 | else | |
529 | { | |
530 | // it's also the boundary of the other geometry | |
531 | if ( other_b ) | |
532 | { | |
533 | update<interior, boundary, '0', transpose_result>(res); | |
534 | } | |
535 | else | |
536 | { | |
537 | update<interior, interior, '0', transpose_result>(res); | |
538 | } | |
539 | } | |
540 | ||
541 | // first IP on the last segment point - this means that the first point is outside | |
542 | if ( first_in_range | |
543 | && ( !this_b || op_blocked ) | |
544 | && was_outside | |
545 | && it->operations[op_id].position != overlay::position_front | |
546 | && ! m_collinear_spike_exit | |
547 | /*&& !is_collinear*/ ) | |
548 | { | |
549 | bool const front_b = is_endpoint_on_boundary<boundary_front>( | |
550 | range::front(sub_range(geometry, seg_id)), | |
551 | boundary_checker); | |
552 | ||
553 | // if there is a boundary on the first point | |
554 | if ( front_b ) | |
555 | { | |
556 | update<boundary, exterior, '0', transpose_result>(res); | |
557 | } | |
558 | } | |
559 | ||
560 | } | |
561 | } | |
562 | } | |
563 | ||
564 | // store ref to previously analysed (valid) turn | |
565 | m_previous_turn_ptr = boost::addressof(*it); | |
566 | // and previously analysed (valid) operation | |
567 | m_previous_operation = op; | |
568 | } | |
569 | ||
570 | // Called for last | |
571 | template <typename Result, | |
572 | typename TurnIt, | |
573 | typename Geometry, | |
574 | typename OtherGeometry, | |
575 | typename BoundaryChecker, | |
576 | typename OtherBoundaryChecker> | |
577 | void apply(Result & res, | |
578 | TurnIt first, TurnIt last, | |
579 | Geometry const& geometry, | |
580 | OtherGeometry const& /*other_geometry*/, | |
581 | BoundaryChecker const& boundary_checker, | |
582 | OtherBoundaryChecker const& /*other_boundary_checker*/) | |
583 | { | |
584 | boost::ignore_unused(first, last); | |
585 | //BOOST_GEOMETRY_ASSERT( first != last ); | |
586 | ||
587 | // here, the possible exit is the real one | |
588 | // we know that we entered and now we exit | |
589 | if ( /*m_exit_watcher.get_exit_operation() == overlay::operation_union // THIS CHECK IS REDUNDANT | |
590 | ||*/ m_previous_operation == overlay::operation_union | |
591 | || m_degenerated_turn_ptr ) | |
592 | { | |
593 | update<interior, exterior, '1', transpose_result>(res); | |
594 | ||
595 | BOOST_GEOMETRY_ASSERT(first != last); | |
596 | ||
597 | const TurnInfo * turn_ptr = NULL; | |
598 | if ( m_degenerated_turn_ptr ) | |
599 | turn_ptr = m_degenerated_turn_ptr; | |
600 | else if ( m_previous_turn_ptr ) | |
601 | turn_ptr = m_previous_turn_ptr; | |
602 | ||
603 | if ( turn_ptr ) | |
604 | { | |
605 | segment_identifier const& prev_seg_id = turn_ptr->operations[op_id].seg_id; | |
606 | ||
607 | //BOOST_GEOMETRY_ASSERT(!boost::empty(sub_range(geometry, prev_seg_id))); | |
608 | bool const prev_back_b = is_endpoint_on_boundary<boundary_back>( | |
609 | range::back(sub_range(geometry, prev_seg_id)), | |
610 | boundary_checker); | |
611 | ||
612 | // if there is a boundary on the last point | |
613 | if ( prev_back_b ) | |
614 | { | |
615 | update<boundary, exterior, '0', transpose_result>(res); | |
616 | } | |
617 | } | |
618 | } | |
619 | ||
620 | // Just in case, | |
621 | // reset exit watcher before the analysis of the next Linestring | |
622 | // note that if there are some enters stored there may be some error above | |
623 | m_exit_watcher.reset(); | |
624 | ||
625 | m_previous_turn_ptr = NULL; | |
626 | m_previous_operation = overlay::operation_none; | |
627 | m_degenerated_turn_ptr = NULL; | |
628 | ||
629 | // actually if this is set to true here there is some error | |
630 | // in get_turns_ll or relate_ll, an assert could be checked here | |
631 | m_collinear_spike_exit = false; | |
632 | } | |
633 | ||
634 | template <typename Result, | |
635 | typename Turn, | |
636 | typename Geometry, | |
637 | typename OtherGeometry, | |
638 | typename BoundaryChecker, | |
639 | typename OtherBoundaryChecker> | |
640 | void handle_degenerated(Result & res, | |
641 | Turn const& turn, | |
642 | Geometry const& geometry, | |
643 | OtherGeometry const& other_geometry, | |
644 | BoundaryChecker const& boundary_checker, | |
645 | OtherBoundaryChecker const& /*other_boundary_checker*/, | |
646 | bool first_in_range) | |
647 | { | |
648 | typename detail::single_geometry_return_type<Geometry const>::type | |
649 | ls1_ref = detail::single_geometry(geometry, turn.operations[op_id].seg_id); | |
650 | typename detail::single_geometry_return_type<OtherGeometry const>::type | |
651 | ls2_ref = detail::single_geometry(other_geometry, turn.operations[other_op_id].seg_id); | |
652 | ||
653 | // only one of those should be true: | |
654 | ||
655 | if ( turn.operations[op_id].position == overlay::position_front ) | |
656 | { | |
657 | // valid, point-sized | |
658 | if ( boost::size(ls2_ref) == 2 ) | |
659 | { | |
660 | bool const front_b = is_endpoint_on_boundary<boundary_front>(turn.point, boundary_checker); | |
661 | ||
662 | if ( front_b ) | |
663 | { | |
664 | update<boundary, interior, '0', transpose_result>(res); | |
665 | } | |
666 | else | |
667 | { | |
668 | update<interior, interior, '0', transpose_result>(res); | |
669 | } | |
670 | ||
671 | // operation 'c' should be last for the same IP so we know that the next point won't be the same | |
672 | update<interior, exterior, '1', transpose_result>(res); | |
673 | ||
674 | m_degenerated_turn_ptr = boost::addressof(turn); | |
675 | } | |
676 | } | |
677 | else if ( turn.operations[op_id].position == overlay::position_back ) | |
678 | { | |
679 | // valid, point-sized | |
680 | if ( boost::size(ls2_ref) == 2 ) | |
681 | { | |
682 | update<interior, exterior, '1', transpose_result>(res); | |
683 | ||
684 | bool const back_b = is_endpoint_on_boundary<boundary_back>(turn.point, boundary_checker); | |
685 | ||
686 | if ( back_b ) | |
687 | { | |
688 | update<boundary, interior, '0', transpose_result>(res); | |
689 | } | |
690 | else | |
691 | { | |
692 | update<interior, interior, '0', transpose_result>(res); | |
693 | } | |
694 | ||
695 | if ( first_in_range ) | |
696 | { | |
697 | //BOOST_GEOMETRY_ASSERT(!boost::empty(ls1_ref)); | |
698 | bool const front_b = is_endpoint_on_boundary<boundary_front>( | |
699 | range::front(ls1_ref), boundary_checker); | |
700 | if ( front_b ) | |
701 | { | |
702 | update<boundary, exterior, '0', transpose_result>(res); | |
703 | } | |
704 | } | |
705 | } | |
706 | } | |
707 | else if ( turn.operations[op_id].position == overlay::position_middle | |
708 | && turn.operations[other_op_id].position == overlay::position_middle ) | |
709 | { | |
710 | update<interior, interior, '0', transpose_result>(res); | |
711 | ||
712 | // here we don't know which one is degenerated | |
713 | ||
714 | bool const is_point1 = boost::size(ls1_ref) == 2 | |
715 | && equals::equals_point_point(range::front(ls1_ref), range::back(ls1_ref)); | |
716 | bool const is_point2 = boost::size(ls2_ref) == 2 | |
717 | && equals::equals_point_point(range::front(ls2_ref), range::back(ls2_ref)); | |
718 | ||
719 | // if the second one is degenerated | |
720 | if ( !is_point1 && is_point2 ) | |
721 | { | |
722 | update<interior, exterior, '1', transpose_result>(res); | |
723 | ||
724 | if ( first_in_range ) | |
725 | { | |
726 | //BOOST_GEOMETRY_ASSERT(!boost::empty(ls1_ref)); | |
727 | bool const front_b = is_endpoint_on_boundary<boundary_front>( | |
728 | range::front(ls1_ref), boundary_checker); | |
729 | if ( front_b ) | |
730 | { | |
731 | update<boundary, exterior, '0', transpose_result>(res); | |
732 | } | |
733 | } | |
734 | ||
735 | m_degenerated_turn_ptr = boost::addressof(turn); | |
736 | } | |
737 | } | |
738 | ||
739 | // NOTE: other.position == front and other.position == back | |
740 | // will be handled later, for the other geometry | |
741 | } | |
742 | ||
743 | private: | |
744 | exit_watcher<TurnInfo, OpId> m_exit_watcher; | |
745 | segment_watcher<same_single> m_seg_watcher; | |
746 | const TurnInfo * m_previous_turn_ptr; | |
747 | overlay::operation_type m_previous_operation; | |
748 | const TurnInfo * m_degenerated_turn_ptr; | |
749 | bool m_collinear_spike_exit; | |
750 | }; | |
751 | ||
752 | template <typename Result, | |
753 | typename TurnIt, | |
754 | typename Analyser, | |
755 | typename Geometry, | |
756 | typename OtherGeometry, | |
757 | typename BoundaryChecker, | |
758 | typename OtherBoundaryChecker> | |
759 | static inline void analyse_each_turn(Result & res, | |
760 | Analyser & analyser, | |
761 | TurnIt first, TurnIt last, | |
762 | Geometry const& geometry, | |
763 | OtherGeometry const& other_geometry, | |
764 | BoundaryChecker const& boundary_checker, | |
765 | OtherBoundaryChecker const& other_boundary_checker) | |
766 | { | |
767 | if ( first == last ) | |
768 | return; | |
769 | ||
770 | for ( TurnIt it = first ; it != last ; ++it ) | |
771 | { | |
772 | analyser.apply(res, it, | |
773 | geometry, other_geometry, | |
774 | boundary_checker, other_boundary_checker); | |
775 | ||
776 | if ( BOOST_GEOMETRY_CONDITION( res.interrupt ) ) | |
777 | return; | |
778 | } | |
779 | ||
780 | analyser.apply(res, first, last, | |
781 | geometry, other_geometry, | |
782 | boundary_checker, other_boundary_checker); | |
783 | } | |
784 | }; | |
785 | ||
786 | }} // namespace detail::relate | |
787 | #endif // DOXYGEN_NO_DETAIL | |
788 | ||
789 | }} // namespace boost::geometry | |
790 | ||
791 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP |