boost/geometry/algorithms/detail/relate/areal_areal.hpp

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