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 // 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_RELATE_AREAL_AREAL_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_AREAL_AREAL_HPP 16 17 #include <boost/geometry/core/topological_dimension.hpp> 18 19 #include <boost/geometry/util/condition.hpp> 20 #include <boost/geometry/util/range.hpp> 21 22 #include <boost/geometry/algorithms/num_interior_rings.hpp> 23 #include <boost/geometry/algorithms/detail/point_on_border.hpp> 24 #include <boost/geometry/algorithms/detail/sub_range.hpp> 25 #include <boost/geometry/algorithms/detail/single_geometry.hpp> 26 27 #include <boost/geometry/algorithms/detail/relate/point_geometry.hpp> 28 #include <boost/geometry/algorithms/detail/relate/turns.hpp> 29 #include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp> 30 #include <boost/geometry/algorithms/detail/relate/follow_helpers.hpp> 31 32 namespace boost { namespace geometry 33 { 34 35 #ifndef DOXYGEN_NO_DETAIL 36 namespace detail { namespace relate { 37 38 // WARNING! 39 // TODO: In the worst case calling this Pred in a loop for MultiPolygon/MultiPolygon may take O(NM) 40 // Use the rtree in this case! 41 42 // may be used to set EI and EB for an Areal geometry for which no turns were generated 43 template <typename OtherAreal, typename Result, bool TransposeResult> 44 class no_turns_aa_pred 45 { 46 public: no_turns_aa_pred(OtherAreal const & other_areal,Result & res)47 no_turns_aa_pred(OtherAreal const& other_areal, Result & res) 48 : m_result(res) 49 , m_other_areal(other_areal) 50 , m_flags(0) 51 { 52 // check which relations must be analysed 53 54 if ( ! may_update<interior, interior, '2', TransposeResult>(m_result) 55 && ! may_update<boundary, interior, '1', TransposeResult>(m_result) 56 && ! may_update<exterior, interior, '2', TransposeResult>(m_result) ) 57 { 58 m_flags |= 1; 59 } 60 61 if ( ! may_update<interior, exterior, '2', TransposeResult>(m_result) 62 && ! may_update<boundary, exterior, '1', TransposeResult>(m_result) ) 63 { 64 m_flags |= 2; 65 } 66 } 67 68 template <typename Areal> operator ()(Areal const & areal)69 bool operator()(Areal const& areal) 70 { 71 // if those flags are set nothing will change 72 if ( m_flags == 3 ) 73 { 74 return false; 75 } 76 77 typedef typename geometry::point_type<Areal>::type point_type; 78 point_type pt; 79 bool const ok = boost::geometry::point_on_border(pt, areal); 80 81 // TODO: for now ignore, later throw an exception? 82 if ( !ok ) 83 { 84 return true; 85 } 86 87 // check if the areal is inside the other_areal 88 // TODO: This is O(N) 89 // Run in a loop O(NM) - optimize! 90 int const pig = detail::within::point_in_geometry(pt, m_other_areal); 91 //BOOST_GEOMETRY_ASSERT( pig != 0 ); 92 93 // inside 94 if ( pig > 0 ) 95 { 96 update<interior, interior, '2', TransposeResult>(m_result); 97 update<boundary, interior, '1', TransposeResult>(m_result); 98 update<exterior, interior, '2', TransposeResult>(m_result); 99 m_flags |= 1; 100 101 // TODO: OPTIMIZE! 102 // Only the interior rings of other ONE single geometry must be checked 103 // NOT all geometries 104 105 // Check if any interior ring is outside 106 ring_identifier ring_id(0, -1, 0); 107 std::size_t const irings_count = geometry::num_interior_rings(areal); 108 for ( ; static_cast<std::size_t>(ring_id.ring_index) < irings_count ; 109 ++ring_id.ring_index ) 110 { 111 typename detail::sub_range_return_type<Areal const>::type 112 range_ref = detail::sub_range(areal, ring_id); 113 114 if ( boost::empty(range_ref) ) 115 { 116 // TODO: throw exception? 117 continue; // ignore 118 } 119 120 // TODO: O(N) 121 // Optimize! 122 int const hpig = detail::within::point_in_geometry(range::front(range_ref), m_other_areal); 123 124 // hole outside 125 if ( hpig < 0 ) 126 { 127 update<interior, exterior, '2', TransposeResult>(m_result); 128 update<boundary, exterior, '1', TransposeResult>(m_result); 129 m_flags |= 2; 130 break; 131 } 132 } 133 } 134 // outside 135 else 136 { 137 update<interior, exterior, '2', TransposeResult>(m_result); 138 update<boundary, exterior, '1', TransposeResult>(m_result); 139 m_flags |= 2; 140 141 // Check if any interior ring is inside 142 ring_identifier ring_id(0, -1, 0); 143 std::size_t const irings_count = geometry::num_interior_rings(areal); 144 for ( ; static_cast<std::size_t>(ring_id.ring_index) < irings_count ; 145 ++ring_id.ring_index ) 146 { 147 typename detail::sub_range_return_type<Areal const>::type 148 range_ref = detail::sub_range(areal, ring_id); 149 150 if ( boost::empty(range_ref) ) 151 { 152 // TODO: throw exception? 153 continue; // ignore 154 } 155 156 // TODO: O(N) 157 // Optimize! 158 int const hpig = detail::within::point_in_geometry(range::front(range_ref), m_other_areal); 159 160 // hole inside 161 if ( hpig > 0 ) 162 { 163 update<interior, interior, '2', TransposeResult>(m_result); 164 update<boundary, interior, '1', TransposeResult>(m_result); 165 update<exterior, interior, '2', TransposeResult>(m_result); 166 m_flags |= 1; 167 break; 168 } 169 } 170 } 171 172 return m_flags != 3 && !m_result.interrupt; 173 } 174 175 private: 176 Result & m_result; 177 OtherAreal const& m_other_areal; 178 int m_flags; 179 }; 180 181 // The implementation of an algorithm calculating relate() for A/A 182 template <typename Geometry1, typename Geometry2> 183 struct areal_areal 184 { 185 // check Linear / Areal 186 BOOST_STATIC_ASSERT(topological_dimension<Geometry1>::value == 2 187 && topological_dimension<Geometry2>::value == 2); 188 189 static const bool interruption_enabled = true; 190 191 typedef typename geometry::point_type<Geometry1>::type point1_type; 192 typedef typename geometry::point_type<Geometry2>::type point2_type; 193 194 template <typename Result> applyboost::geometry::detail::relate::areal_areal195 static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Result & result) 196 { 197 // TODO: If Areal geometry may have infinite size, change the following line: 198 199 // The result should be FFFFFFFFF 200 relate::set<exterior, exterior, result_dimension<Geometry2>::value>(result);// FFFFFFFFd, d in [1,9] or T 201 202 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 203 return; 204 205 // get and analyse turns 206 typedef typename turns::get_turns<Geometry1, Geometry2>::turn_info turn_type; 207 std::vector<turn_type> turns; 208 209 interrupt_policy_areal_areal<Result> interrupt_policy(geometry1, geometry2, result); 210 211 turns::get_turns<Geometry1, Geometry2>::apply(turns, geometry1, geometry2, interrupt_policy); 212 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 213 return; 214 215 no_turns_aa_pred<Geometry2, Result, false> pred1(geometry2, result); 216 for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1); 217 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 218 return; 219 220 no_turns_aa_pred<Geometry1, Result, true> pred2(geometry1, result); 221 for_each_disjoint_geometry_if<1, Geometry2>::apply(turns.begin(), turns.end(), geometry2, pred2); 222 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 223 return; 224 225 if ( turns.empty() ) 226 return; 227 228 if ( may_update<interior, interior, '2'>(result) 229 || may_update<interior, exterior, '2'>(result) 230 || may_update<boundary, interior, '1'>(result) 231 || may_update<boundary, exterior, '1'>(result) 232 || may_update<exterior, interior, '2'>(result) ) 233 { 234 // sort turns 235 typedef turns::less<0, turns::less_op_areal_areal<0> > less; 236 std::sort(turns.begin(), turns.end(), less()); 237 238 /*if ( may_update<interior, exterior, '2'>(result) 239 || may_update<boundary, exterior, '1'>(result) 240 || may_update<boundary, interior, '1'>(result) 241 || may_update<exterior, interior, '2'>(result) )*/ 242 { 243 // analyse sorted turns 244 turns_analyser<turn_type, 0> analyser; 245 analyse_each_turn(result, analyser, turns.begin(), turns.end()); 246 247 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 248 return; 249 } 250 251 if ( may_update<interior, interior, '2'>(result) 252 || may_update<interior, exterior, '2'>(result) 253 || may_update<boundary, interior, '1'>(result) 254 || may_update<boundary, exterior, '1'>(result) 255 || may_update<exterior, interior, '2'>(result) ) 256 { 257 // analyse rings for which turns were not generated 258 // or only i/i or u/u was generated 259 uncertain_rings_analyser<0, Result, Geometry1, Geometry2> rings_analyser(result, geometry1, geometry2); 260 analyse_uncertain_rings<0>::apply(rings_analyser, turns.begin(), turns.end()); 261 262 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 263 return; 264 } 265 } 266 267 if ( may_update<interior, interior, '2', true>(result) 268 || may_update<interior, exterior, '2', true>(result) 269 || may_update<boundary, interior, '1', true>(result) 270 || may_update<boundary, exterior, '1', true>(result) 271 || may_update<exterior, interior, '2', true>(result) ) 272 { 273 // sort turns 274 typedef turns::less<1, turns::less_op_areal_areal<1> > less; 275 std::sort(turns.begin(), turns.end(), less()); 276 277 /*if ( may_update<interior, exterior, '2', true>(result) 278 || may_update<boundary, exterior, '1', true>(result) 279 || may_update<boundary, interior, '1', true>(result) 280 || may_update<exterior, interior, '2', true>(result) )*/ 281 { 282 // analyse sorted turns 283 turns_analyser<turn_type, 1> analyser; 284 analyse_each_turn(result, analyser, turns.begin(), turns.end()); 285 286 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 287 return; 288 } 289 290 if ( may_update<interior, interior, '2', true>(result) 291 || may_update<interior, exterior, '2', true>(result) 292 || may_update<boundary, interior, '1', true>(result) 293 || may_update<boundary, exterior, '1', true>(result) 294 || may_update<exterior, interior, '2', true>(result) ) 295 { 296 // analyse rings for which turns were not generated 297 // or only i/i or u/u was generated 298 uncertain_rings_analyser<1, Result, Geometry2, Geometry1> rings_analyser(result, geometry2, geometry1); 299 analyse_uncertain_rings<1>::apply(rings_analyser, turns.begin(), turns.end()); 300 301 //if ( result.interrupt ) 302 // return; 303 } 304 } 305 } 306 307 // interrupt policy which may be passed to get_turns to interrupt the analysis 308 // based on the info in the passed result/mask 309 template <typename Result> 310 class interrupt_policy_areal_areal 311 { 312 public: 313 static bool const enabled = true; 314 interrupt_policy_areal_areal(Geometry1 const & geometry1,Geometry2 const & geometry2,Result & result)315 interrupt_policy_areal_areal(Geometry1 const& geometry1, 316 Geometry2 const& geometry2, 317 Result & result) 318 : m_result(result) 319 , m_geometry1(geometry1) 320 , m_geometry2(geometry2) 321 {} 322 323 template <typename Range> apply(Range const & turns)324 inline bool apply(Range const& turns) 325 { 326 typedef typename boost::range_iterator<Range const>::type iterator; 327 328 for (iterator it = boost::begin(turns) ; it != boost::end(turns) ; ++it) 329 { 330 per_turn<0>(*it); 331 per_turn<1>(*it); 332 } 333 334 return m_result.interrupt; 335 } 336 337 private: 338 template <std::size_t OpId, typename Turn> per_turn(Turn const & turn)339 inline void per_turn(Turn const& turn) 340 { 341 static const std::size_t other_op_id = (OpId + 1) % 2; 342 static const bool transpose_result = OpId != 0; 343 344 overlay::operation_type const op = turn.operations[OpId].operation; 345 346 if ( op == overlay::operation_union ) 347 { 348 // ignore u/u 349 /*if ( turn.operations[other_op_id].operation != overlay::operation_union ) 350 { 351 update<interior, exterior, '2', transpose_result>(m_result); 352 update<boundary, exterior, '1', transpose_result>(m_result); 353 }*/ 354 355 update<boundary, boundary, '0', transpose_result>(m_result); 356 } 357 else if ( op == overlay::operation_intersection ) 358 { 359 // ignore i/i 360 if ( turn.operations[other_op_id].operation != overlay::operation_intersection ) 361 { 362 update<interior, interior, '2', transpose_result>(m_result); 363 //update<boundary, interior, '1', transpose_result>(m_result); 364 } 365 366 update<boundary, boundary, '0', transpose_result>(m_result); 367 } 368 else if ( op == overlay::operation_continue ) 369 { 370 update<boundary, boundary, '1', transpose_result>(m_result); 371 update<interior, interior, '2', transpose_result>(m_result); 372 } 373 else if ( op == overlay::operation_blocked ) 374 { 375 update<boundary, boundary, '1', transpose_result>(m_result); 376 update<interior, exterior, '2', transpose_result>(m_result); 377 } 378 } 379 380 Result & m_result; 381 Geometry1 const& m_geometry1; 382 Geometry2 const& m_geometry2; 383 }; 384 385 // This analyser should be used like Input or SinglePass Iterator 386 // IMPORTANT! It should be called also for the end iterator - last 387 template <typename TurnInfo, std::size_t OpId> 388 class turns_analyser 389 { 390 typedef typename TurnInfo::point_type turn_point_type; 391 392 static const std::size_t op_id = OpId; 393 static const std::size_t other_op_id = (OpId + 1) % 2; 394 static const bool transpose_result = OpId != 0; 395 396 public: turns_analyser()397 turns_analyser() 398 : m_previous_turn_ptr(0) 399 , m_previous_operation(overlay::operation_none) 400 , m_enter_detected(false) 401 , m_exit_detected(false) 402 {} 403 404 template <typename Result, 405 typename TurnIt> apply(Result & result,TurnIt it)406 void apply(Result & result, TurnIt it) 407 { 408 //BOOST_GEOMETRY_ASSERT( it != last ); 409 410 overlay::operation_type const op = it->operations[op_id].operation; 411 412 if ( op != overlay::operation_union 413 && op != overlay::operation_intersection 414 && op != overlay::operation_blocked 415 && op != overlay::operation_continue ) 416 { 417 return; 418 } 419 420 segment_identifier const& seg_id = it->operations[op_id].seg_id; 421 //segment_identifier const& other_id = it->operations[other_op_id].seg_id; 422 423 const bool first_in_range = m_seg_watcher.update(seg_id); 424 425 if ( m_previous_turn_ptr ) 426 { 427 if ( m_exit_detected /*m_previous_operation == overlay::operation_union*/ ) 428 { 429 // real exit point - may be multiple 430 if ( first_in_range 431 || ! turn_on_the_same_ip<op_id>(*m_previous_turn_ptr, *it) ) 432 { 433 update_exit(result); 434 m_exit_detected = false; 435 } 436 // fake exit point, reset state 437 else if ( op != overlay::operation_union ) 438 { 439 m_exit_detected = false; 440 } 441 } 442 /*else*/ 443 if ( m_enter_detected /*m_previous_operation == overlay::operation_intersection*/ ) 444 { 445 // real entry point 446 if ( first_in_range 447 || ! turn_on_the_same_ip<op_id>(*m_previous_turn_ptr, *it) ) 448 { 449 update_enter(result); 450 m_enter_detected = false; 451 } 452 // fake entry point, reset state 453 else if ( op != overlay::operation_intersection ) 454 { 455 m_enter_detected = false; 456 } 457 } 458 } 459 460 if ( op == overlay::operation_union ) 461 { 462 // already set in interrupt policy 463 //update<boundary, boundary, '0', transpose_result>(m_result); 464 465 // ignore u/u 466 //if ( it->operations[other_op_id].operation != overlay::operation_union ) 467 { 468 m_exit_detected = true; 469 } 470 } 471 else if ( op == overlay::operation_intersection ) 472 { 473 // ignore i/i 474 if ( it->operations[other_op_id].operation != overlay::operation_intersection ) 475 { 476 // already set in interrupt policy 477 //update<interior, interior, '2', transpose_result>(result); 478 //update<boundary, boundary, '0', transpose_result>(result); 479 m_enter_detected = true; 480 } 481 } 482 else if ( op == overlay::operation_blocked ) 483 { 484 // already set in interrupt policy 485 } 486 else // if ( op == overlay::operation_continue ) 487 { 488 // already set in interrupt policy 489 } 490 491 // store ref to previously analysed (valid) turn 492 m_previous_turn_ptr = boost::addressof(*it); 493 // and previously analysed (valid) operation 494 m_previous_operation = op; 495 } 496 497 // it == last 498 template <typename Result> apply(Result & result)499 void apply(Result & result) 500 { 501 //BOOST_GEOMETRY_ASSERT( first != last ); 502 503 if ( m_exit_detected /*m_previous_operation == overlay::operation_union*/ ) 504 { 505 update_exit(result); 506 m_exit_detected = false; 507 } 508 509 if ( m_enter_detected /*m_previous_operation == overlay::operation_intersection*/ ) 510 { 511 update_enter(result); 512 m_enter_detected = false; 513 } 514 } 515 516 template <typename Result> update_exit(Result & result)517 static inline void update_exit(Result & result) 518 { 519 update<interior, exterior, '2', transpose_result>(result); 520 update<boundary, exterior, '1', transpose_result>(result); 521 } 522 523 template <typename Result> update_enter(Result & result)524 static inline void update_enter(Result & result) 525 { 526 update<boundary, interior, '1', transpose_result>(result); 527 update<exterior, interior, '2', transpose_result>(result); 528 } 529 530 private: 531 segment_watcher<same_ring> m_seg_watcher; 532 TurnInfo * m_previous_turn_ptr; 533 overlay::operation_type m_previous_operation; 534 bool m_enter_detected; 535 bool m_exit_detected; 536 }; 537 538 // call analyser.apply() for each turn in range 539 // IMPORTANT! The analyser is also called for the end iterator - last 540 template <typename Result, 541 typename Analyser, 542 typename TurnIt> analyse_each_turnboost::geometry::detail::relate::areal_areal543 static inline void analyse_each_turn(Result & res, 544 Analyser & analyser, 545 TurnIt first, TurnIt last) 546 { 547 if ( first == last ) 548 return; 549 550 for ( TurnIt it = first ; it != last ; ++it ) 551 { 552 analyser.apply(res, it); 553 554 if ( BOOST_GEOMETRY_CONDITION(res.interrupt) ) 555 return; 556 } 557 558 analyser.apply(res); 559 } 560 561 template <std::size_t OpId, typename Result, typename Geometry, typename OtherGeometry> 562 class uncertain_rings_analyser 563 { 564 static const bool transpose_result = OpId != 0; 565 static const int other_id = (OpId + 1) % 2; 566 567 public: uncertain_rings_analyser(Result & result,Geometry const & geom,OtherGeometry const & other_geom)568 inline uncertain_rings_analyser(Result & result, 569 Geometry const& geom, 570 OtherGeometry const& other_geom) 571 : geometry(geom), other_geometry(other_geom) 572 , interrupt(result.interrupt) // just in case, could be false as well 573 , m_result(result) 574 , m_flags(0) 575 { 576 // check which relations must be analysed 577 578 if ( ! may_update<interior, interior, '2', transpose_result>(m_result) ) 579 { 580 m_flags |= 1; 581 } 582 583 if ( ! may_update<interior, exterior, '2', transpose_result>(m_result) 584 && ! may_update<boundary, exterior, '1', transpose_result>(m_result) ) 585 { 586 m_flags |= 2; 587 } 588 589 if ( ! may_update<boundary, interior, '1', transpose_result>(m_result) 590 && ! may_update<exterior, interior, '2', transpose_result>(m_result) ) 591 { 592 m_flags |= 4; 593 } 594 } 595 no_turns(segment_identifier const & seg_id)596 inline void no_turns(segment_identifier const& seg_id) 597 { 598 // if those flags are set nothing will change 599 if ( m_flags == 7 ) 600 { 601 return; 602 } 603 604 typename detail::sub_range_return_type<Geometry const>::type 605 range_ref = detail::sub_range(geometry, seg_id); 606 607 if ( boost::empty(range_ref) ) 608 { 609 // TODO: throw an exception? 610 return; // ignore 611 } 612 613 // TODO: possible optimization 614 // if the range is an interior ring we may use other IPs generated for this single geometry 615 // to know which other single geometries should be checked 616 617 // TODO: optimize! e.g. use spatial index 618 // O(N) - running it in a loop gives O(NM) 619 int const pig = detail::within::point_in_geometry(range::front(range_ref), other_geometry); 620 621 //BOOST_GEOMETRY_ASSERT(pig != 0); 622 if ( pig > 0 ) 623 { 624 update<interior, interior, '2', transpose_result>(m_result); 625 m_flags |= 1; 626 627 update<boundary, interior, '1', transpose_result>(m_result); 628 update<exterior, interior, '2', transpose_result>(m_result); 629 m_flags |= 4; 630 } 631 else 632 { 633 update<boundary, exterior, '1', transpose_result>(m_result); 634 update<interior, exterior, '2', transpose_result>(m_result); 635 m_flags |= 2; 636 } 637 638 // TODO: break if all things are set 639 // also some of them could be checked outside, before the analysis 640 // In this case we shouldn't relay just on dummy flags 641 // Flags should be initialized with proper values 642 // or the result should be checked directly 643 // THIS IS ALSO TRUE FOR OTHER ANALYSERS! in L/L and L/A 644 645 interrupt = m_flags == 7 || m_result.interrupt; 646 } 647 648 template <typename TurnIt> turns(TurnIt first,TurnIt last)649 inline void turns(TurnIt first, TurnIt last) 650 { 651 // if those flags are set nothing will change 652 if ( (m_flags & 6) == 6 ) 653 { 654 return; 655 } 656 657 bool found_ii = false; 658 bool found_uu = false; 659 660 for ( TurnIt it = first ; it != last ; ++it ) 661 { 662 if ( it->operations[0].operation == overlay::operation_intersection 663 && it->operations[1].operation == overlay::operation_intersection ) 664 { 665 // ignore exterior ring 666 if ( it->operations[OpId].seg_id.ring_index >= 0 ) 667 { 668 found_ii = true; 669 } 670 } 671 else if ( it->operations[0].operation == overlay::operation_union 672 && it->operations[1].operation == overlay::operation_union ) 673 { 674 // ignore if u/u is for holes 675 //if ( it->operations[OpId].seg_id.ring_index >= 0 676 // && it->operations[other_id].seg_id.ring_index >= 0 ) 677 { 678 found_uu = true; 679 } 680 } 681 else // ignore 682 { 683 return; // don't interrupt 684 } 685 } 686 687 // only i/i was generated for this ring 688 if ( found_ii ) 689 { 690 //update<interior, interior, '0', transpose_result>(m_result); 691 //update<boundary, boundary, '0', transpose_result>(m_result); 692 update<boundary, interior, '1', transpose_result>(m_result); 693 update<exterior, interior, '2', transpose_result>(m_result); 694 m_flags |= 4; 695 } 696 697 // only u/u was generated for this ring 698 if ( found_uu ) 699 { 700 update<boundary, exterior, '1', transpose_result>(m_result); 701 update<interior, exterior, '2', transpose_result>(m_result); 702 m_flags |= 2; 703 } 704 705 interrupt = m_flags == 7 || m_result.interrupt; // interrupt if the result won't be changed in the future 706 } 707 708 Geometry const& geometry; 709 OtherGeometry const& other_geometry; 710 bool interrupt; 711 712 private: 713 Result & m_result; 714 int m_flags; 715 }; 716 717 template <std::size_t OpId> 718 class analyse_uncertain_rings 719 { 720 public: 721 template <typename Analyser, typename TurnIt> apply(Analyser & analyser,TurnIt first,TurnIt last)722 static inline void apply(Analyser & analyser, TurnIt first, TurnIt last) 723 { 724 if ( first == last ) 725 return; 726 727 for_preceding_rings(analyser, *first); 728 //analyser.per_turn(*first); 729 730 TurnIt prev = first; 731 for ( ++first ; first != last ; ++first, ++prev ) 732 { 733 // same multi 734 if ( prev->operations[OpId].seg_id.multi_index 735 == first->operations[OpId].seg_id.multi_index ) 736 { 737 // same ring 738 if ( prev->operations[OpId].seg_id.ring_index 739 == first->operations[OpId].seg_id.ring_index ) 740 { 741 //analyser.per_turn(*first); 742 } 743 // same multi, next ring 744 else 745 { 746 //analyser.end_ring(*prev); 747 analyser.turns(prev, first); 748 749 //if ( prev->operations[OpId].seg_id.ring_index + 1 750 // < first->operations[OpId].seg_id.ring_index) 751 { 752 for_no_turns_rings(analyser, 753 *first, 754 prev->operations[OpId].seg_id.ring_index + 1, 755 first->operations[OpId].seg_id.ring_index); 756 } 757 758 //analyser.per_turn(*first); 759 } 760 } 761 // next multi 762 else 763 { 764 //analyser.end_ring(*prev); 765 analyser.turns(prev, first); 766 for_following_rings(analyser, *prev); 767 for_preceding_rings(analyser, *first); 768 //analyser.per_turn(*first); 769 } 770 771 if ( analyser.interrupt ) 772 { 773 return; 774 } 775 } 776 777 //analyser.end_ring(*prev); 778 analyser.turns(prev, first); // first == last 779 for_following_rings(analyser, *prev); 780 } 781 782 private: 783 template <typename Analyser, typename Turn> for_preceding_rings(Analyser & analyser,Turn const & turn)784 static inline void for_preceding_rings(Analyser & analyser, Turn const& turn) 785 { 786 segment_identifier const& seg_id = turn.operations[OpId].seg_id; 787 788 for_no_turns_rings(analyser, turn, -1, seg_id.ring_index); 789 } 790 791 template <typename Analyser, typename Turn> for_following_rings(Analyser & analyser,Turn const & turn)792 static inline void for_following_rings(Analyser & analyser, Turn const& turn) 793 { 794 segment_identifier const& seg_id = turn.operations[OpId].seg_id; 795 796 signed_size_type 797 count = boost::numeric_cast<signed_size_type>( 798 geometry::num_interior_rings( 799 detail::single_geometry(analyser.geometry, seg_id))); 800 801 for_no_turns_rings(analyser, turn, seg_id.ring_index + 1, count); 802 } 803 804 template <typename Analyser, typename Turn> for_no_turns_rings(Analyser & analyser,Turn const & turn,signed_size_type first,signed_size_type last)805 static inline void for_no_turns_rings(Analyser & analyser, 806 Turn const& turn, 807 signed_size_type first, 808 signed_size_type last) 809 { 810 segment_identifier seg_id = turn.operations[OpId].seg_id; 811 812 for ( seg_id.ring_index = first ; seg_id.ring_index < last ; ++seg_id.ring_index ) 813 { 814 analyser.no_turns(seg_id); 815 } 816 } 817 }; 818 }; 819 820 }} // namespace detail::relate 821 #endif // DOXYGEN_NO_DETAIL 822 823 }} // namespace boost::geometry 824 825 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_AREAL_AREAL_HPP 826