ceph/src/boost/libs/geometry/include/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, 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:
  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>
  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>
 195     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
 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>
 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>
 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                     // not correct e.g. for G1 touching G2 in a point where a hole is touching the exterior ring
 363                     // in this case 2 turns i/... and u/u will be generated for this IP
 364                     //update<interior, interior, '2', transpose_result>(m_result);
 365
 366                     //update<boundary, interior, '1', transpose_result>(m_result);
 367                 }*/
 368
 369                 update<boundary, boundary, '0', transpose_result>(m_result);
 370             }
 371             else if ( op == overlay::operation_continue )
 372             {
 373                 update<boundary, boundary, '1', transpose_result>(m_result);
 374                 update<interior, interior, '2', transpose_result>(m_result);
 375             }
 376             else if ( op == overlay::operation_blocked )
 377             {
 378                 update<boundary, boundary, '1', transpose_result>(m_result);
 379                 update<interior, exterior, '2', transpose_result>(m_result);
 380             }
 381         }
 382
 383         Result & m_result;
 384         Geometry1 const& m_geometry1;
 385         Geometry2 const& m_geometry2;
 386     };
 387
 388     // This analyser should be used like Input or SinglePass Iterator
 389     // IMPORTANT! It should be called also for the end iterator - last
 390     template <typename TurnInfo, std::size_t OpId>
 391     class turns_analyser
 392     {
 393         typedef typename TurnInfo::point_type turn_point_type;
 394
 395         static const std::size_t op_id = OpId;
 396         static const std::size_t other_op_id = (OpId + 1) % 2;
 397         static const bool transpose_result = OpId != 0;
 398
 399     public:
 400         turns_analyser()
 401             : m_previous_turn_ptr(0)
 402             , m_previous_operation(overlay::operation_none)
 403             , m_enter_detected(false)
 404             , m_exit_detected(false)
 405         {}
 406
 407         template <typename Result,
 408                   typename TurnIt>
 409         void apply(Result & result, TurnIt it)
 410         {
 411             //BOOST_GEOMETRY_ASSERT( it != last );
 412
 413             overlay::operation_type const op = it->operations[op_id].operation;
 414
 415             if ( op != overlay::operation_union
 416               && op != overlay::operation_intersection
 417               && op != overlay::operation_blocked
 418               && op != overlay::operation_continue )
 419             {
 420                 return;
 421             }
 422
 423             segment_identifier const& seg_id = it->operations[op_id].seg_id;
 424             //segment_identifier const& other_id = it->operations[other_op_id].seg_id;
 425
 426             const bool first_in_range = m_seg_watcher.update(seg_id);
 427
 428             if ( m_previous_turn_ptr )
 429             {
 430                 if ( m_exit_detected /*m_previous_operation == overlay::operation_union*/ )
 431                 {
 432                     // real exit point - may be multiple
 433                     if ( first_in_range
 434                       || ! turn_on_the_same_ip<op_id>(*m_previous_turn_ptr, *it) )
 435                     {
 436                         update_exit(result);
 437                         m_exit_detected = false;
 438                     }
 439                     // fake exit point, reset state
 440                     else if ( op != overlay::operation_union )
 441                     {
 442                         m_exit_detected = false;
 443                     }
 444                 }
 445                 /*else*/
 446                 if ( m_enter_detected /*m_previous_operation == overlay::operation_intersection*/ )
 447                 {
 448                     // real entry point
 449                     if ( first_in_range
 450                       || ! turn_on_the_same_ip<op_id>(*m_previous_turn_ptr, *it) )
 451                     {
 452                         update_enter(result);
 453                         m_enter_detected = false;
 454                     }
 455                     // fake entry point, reset state
 456                     else if ( op != overlay::operation_intersection )
 457                     {
 458                         m_enter_detected = false;
 459                     }
 460                 }
 461             }
 462
 463             if ( op == overlay::operation_union )
 464             {
 465                 // already set in interrupt policy
 466                 //update<boundary, boundary, '0', transpose_result>(m_result);
 467
 468                 // ignore u/u
 469                 //if ( it->operations[other_op_id].operation != overlay::operation_union )
 470                 {
 471                     m_exit_detected = true;
 472                 }
 473             }
 474             else if ( op == overlay::operation_intersection )
 475             {
 476                 // ignore i/i
 477                 if ( it->operations[other_op_id].operation != overlay::operation_intersection )
 478                 {
 479                     // this was set in the interrupt policy but it was wrong
 480                     // also here it's wrong since it may be a fake entry point
 481                     //update<interior, interior, '2', transpose_result>(result);
 482
 483                     // already set in interrupt policy
 484                     //update<boundary, boundary, '0', transpose_result>(result);
 485                     m_enter_detected = true;
 486                 }
 487             }
 488             else if ( op == overlay::operation_blocked )
 489             {
 490                 // already set in interrupt policy
 491             }
 492             else // if ( op == overlay::operation_continue )
 493             {
 494                 // already set in interrupt policy
 495             }
 496
 497             // store ref to previously analysed (valid) turn
 498             m_previous_turn_ptr = boost::addressof(*it);
 499             // and previously analysed (valid) operation
 500             m_previous_operation = op;
 501         }
 502
 503         // it == last
 504         template <typename Result>
 505         void apply(Result & result)
 506         {
 507             //BOOST_GEOMETRY_ASSERT( first != last );
 508
 509             if ( m_exit_detected /*m_previous_operation == overlay::operation_union*/ )
 510             {
 511                 update_exit(result);
 512                 m_exit_detected = false;
 513             }
 514
 515             if ( m_enter_detected /*m_previous_operation == overlay::operation_intersection*/ )
 516             {
 517                 update_enter(result);
 518                 m_enter_detected = false;
 519             }
 520         }
 521
 522         template <typename Result>
 523         static inline void update_exit(Result & result)
 524         {
 525             update<interior, exterior, '2', transpose_result>(result);
 526             update<boundary, exterior, '1', transpose_result>(result);
 527         }
 528
 529         template <typename Result>
 530         static inline void update_enter(Result & result)
 531         {
 532             update<interior, interior, '2', transpose_result>(result);
 533             update<boundary, interior, '1', transpose_result>(result);
 534             update<exterior, interior, '2', transpose_result>(result);
 535         }
 536
 537     private:
 538         segment_watcher<same_ring> m_seg_watcher;
 539         TurnInfo * m_previous_turn_ptr;
 540         overlay::operation_type m_previous_operation;
 541         bool m_enter_detected;
 542         bool m_exit_detected;
 543     };
 544
 545     // call analyser.apply() for each turn in range
 546     // IMPORTANT! The analyser is also called for the end iterator - last
 547     template <typename Result,
 548               typename Analyser,
 549               typename TurnIt>
 550     static inline void analyse_each_turn(Result & res,
 551                                          Analyser & analyser,
 552                                          TurnIt first, TurnIt last)
 553     {
 554         if ( first == last )
 555             return;
 556
 557         for ( TurnIt it = first ; it != last ; ++it )
 558         {
 559             analyser.apply(res, it);
 560
 561             if ( BOOST_GEOMETRY_CONDITION(res.interrupt) )
 562                 return;
 563         }
 564
 565         analyser.apply(res);
 566     }
 567
 568     template <std::size_t OpId, typename Result, typename Geometry, typename OtherGeometry>
 569     class uncertain_rings_analyser
 570     {
 571         static const bool transpose_result = OpId != 0;
 572         static const int other_id = (OpId + 1) % 2;
 573
 574     public:
 575         inline uncertain_rings_analyser(Result & result,
 576                                         Geometry const& geom,
 577                                         OtherGeometry const& other_geom)
 578             : geometry(geom), other_geometry(other_geom)
 579             , interrupt(result.interrupt) // just in case, could be false as well
 580             , m_result(result)
 581             , m_flags(0)
 582         {
 583             // check which relations must be analysed
 584             // NOTE: 1 and 4 could probably be connected
 585
 586             if ( ! may_update<interior, interior, '2', transpose_result>(m_result) )
 587             {
 588                 m_flags |= 1;
 589             }
 590
 591             if ( ! may_update<interior, exterior, '2', transpose_result>(m_result)
 592               && ! may_update<boundary, exterior, '1', transpose_result>(m_result) )
 593             {
 594                 m_flags |= 2;
 595             }
 596
 597             if ( ! may_update<boundary, interior, '1', transpose_result>(m_result)
 598               && ! may_update<exterior, interior, '2', transpose_result>(m_result) )
 599             {
 600                 m_flags |= 4;
 601             }
 602         }
 603
 604         inline void no_turns(segment_identifier const& seg_id)
 605         {
 606             // if those flags are set nothing will change
 607             if ( m_flags == 7 )
 608             {
 609                 return;
 610             }
 611
 612             typename detail::sub_range_return_type<Geometry const>::type
 613                 range_ref = detail::sub_range(geometry, seg_id);
 614
 615             if ( boost::empty(range_ref) )
 616             {
 617                 // TODO: throw an exception?
 618                 return; // ignore
 619             }
 620
 621             // TODO: possible optimization
 622             // if the range is an interior ring we may use other IPs generated for this single geometry
 623             // to know which other single geometries should be checked
 624
 625             // TODO: optimize! e.g. use spatial index
 626             // O(N) - running it in a loop gives O(NM)
 627             int const pig = detail::within::point_in_geometry(range::front(range_ref), other_geometry);
 628
 629             //BOOST_GEOMETRY_ASSERT(pig != 0);
 630             if ( pig > 0 )
 631             {
 632                 update<interior, interior, '2', transpose_result>(m_result);
 633                 m_flags |= 1;
 634
 635                 update<boundary, interior, '1', transpose_result>(m_result);
 636                 update<exterior, interior, '2', transpose_result>(m_result);
 637                 m_flags |= 4;
 638             }
 639             else
 640             {
 641                 update<boundary, exterior, '1', transpose_result>(m_result);
 642                 update<interior, exterior, '2', transpose_result>(m_result);
 643                 m_flags |= 2;
 644             }
 645
 646 // TODO: break if all things are set
 647 // also some of them could be checked outside, before the analysis
 648 // In this case we shouldn't relay just on dummy flags
 649 // Flags should be initialized with proper values
 650 // or the result should be checked directly
 651 // THIS IS ALSO TRUE FOR OTHER ANALYSERS! in L/L and L/A
 652
 653             interrupt = m_flags == 7 || m_result.interrupt;
 654         }
 655
 656         template <typename TurnIt>
 657         inline void turns(TurnIt first, TurnIt last)
 658         {
 659             // if those flags are set nothing will change
 660             if ( (m_flags & 6) == 6 )
 661             {
 662                 return;
 663             }
 664
 665             bool found_ii = false;
 666             bool found_uu = false;
 667
 668             for ( TurnIt it = first ; it != last ; ++it )
 669             {
 670                 if ( it->operations[0].operation == overlay::operation_intersection
 671                   && it->operations[1].operation == overlay::operation_intersection )
 672                 {
 673                     found_ii = true;
 674                 }
 675                 else if ( it->operations[0].operation == overlay::operation_union
 676                        && it->operations[1].operation == overlay::operation_union )
 677                 {
 678                     found_uu = true;
 679                 }
 680                 else // ignore
 681                 {
 682                     return; // don't interrupt
 683                 }
 684             }
 685
 686             // only i/i was generated for this ring
 687             if ( found_ii )
 688             {
 689                 update<interior, interior, '2', transpose_result>(m_result);
 690                 m_flags |= 1;
 691
 692                 //update<boundary, boundary, '0', transpose_result>(m_result);
 693
 694                 update<boundary, interior, '1', transpose_result>(m_result);
 695                 update<exterior, interior, '2', transpose_result>(m_result);
 696                 m_flags |= 4;
 697             }
 698
 699             // only u/u was generated for this ring
 700             if ( found_uu )
 701             {
 702                 update<boundary, exterior, '1', transpose_result>(m_result);
 703                 update<interior, exterior, '2', transpose_result>(m_result);
 704                 m_flags |= 2;
 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             signed_size_type
 799                 count = boost::numeric_cast<signed_size_type>(
 800                             geometry::num_interior_rings(
 801                                 detail::single_geometry(analyser.geometry, seg_id)));
 802
 803             for_no_turns_rings(analyser, turn, seg_id.ring_index + 1, count);
 804         }
 805
 806         template <typename Analyser, typename Turn>
 807         static inline void for_no_turns_rings(Analyser & analyser,
 808                                               Turn const& turn,
 809                                               signed_size_type first,
 810                                               signed_size_type last)
 811         {
 812             segment_identifier seg_id = turn.operations[OpId].seg_id;
 813
 814             for ( seg_id.ring_index = first ; seg_id.ring_index < last ; ++seg_id.ring_index )
 815             {
 816                 analyser.no_turns(seg_id);
 817             }
 818         }
 819     };
 820 };
 821
 822 }} // namespace detail::relate
 823 #endif // DOXYGEN_NO_DETAIL
 824
 825 }} // namespace boost::geometry
 826
 827 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_AREAL_AREAL_HPP