Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:35:13 

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002 
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 
0005 // This file was modified by Oracle on 2013-2022.
0006 // Modifications copyright (c) 2013-2022 Oracle and/or its affiliates.
0007 
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009 
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013 
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_AREAL_AREAL_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_AREAL_AREAL_HPP
0016 
0017 #include <boost/geometry/core/topological_dimension.hpp>
0018 
0019 #include <boost/geometry/util/condition.hpp>
0020 #include <boost/geometry/util/range.hpp>
0021 
0022 #include <boost/geometry/algorithms/num_interior_rings.hpp>
0023 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
0024 #include <boost/geometry/algorithms/detail/sub_range.hpp>
0025 #include <boost/geometry/algorithms/detail/single_geometry.hpp>
0026 
0027 #include <boost/geometry/algorithms/detail/relate/point_geometry.hpp>
0028 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
0029 #include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp>
0030 #include <boost/geometry/algorithms/detail/relate/follow_helpers.hpp>
0031 
0032 #include <boost/geometry/geometries/helper_geometry.hpp>
0033 
0034 namespace boost { namespace geometry
0035 {
0036 
0037 #ifndef DOXYGEN_NO_DETAIL
0038 namespace detail { namespace relate {
0039 
0040 // WARNING!
0041 // TODO: In the worst case calling this Pred in a loop for MultiPolygon/MultiPolygon may take O(NM)
0042 // Use the rtree in this case!
0043 
0044 // may be used to set EI and EB for an Areal geometry for which no turns were generated
0045 template
0046 <
0047     typename OtherAreal,
0048     typename Result,
0049     typename PointInArealStrategy,
0050     bool TransposeResult
0051 >
0052 class no_turns_aa_pred
0053 {
0054 public:
0055     no_turns_aa_pred(OtherAreal const& other_areal,
0056                      Result & res,
0057                      PointInArealStrategy const& point_in_areal_strategy)
0058         : m_result(res)
0059         , m_point_in_areal_strategy(point_in_areal_strategy)
0060         , m_other_areal(other_areal)
0061         , m_flags(0)
0062     {
0063         // check which relations must be analysed
0064 
0065         if ( ! may_update<interior, interior, '2', TransposeResult>(m_result)
0066           && ! may_update<boundary, interior, '1', TransposeResult>(m_result)
0067           && ! may_update<exterior, interior, '2', TransposeResult>(m_result) )
0068         {
0069             m_flags |= 1;
0070         }
0071 
0072         if ( ! may_update<interior, exterior, '2', TransposeResult>(m_result)
0073           && ! may_update<boundary, exterior, '1', TransposeResult>(m_result) )
0074         {
0075             m_flags |= 2;
0076         }
0077     }
0078 
0079     template <typename Areal>
0080     bool operator()(Areal const& areal)
0081     {
0082         using detail::within::point_in_geometry;
0083 
0084         // if those flags are set nothing will change
0085         if ( m_flags == 3 )
0086         {
0087             return false;
0088         }
0089 
0090         using point_type = typename geometry::point_type<Areal>::type;
0091         typename helper_geometry<point_type>::type pt;
0092         bool const ok = geometry::point_on_border(pt, areal);
0093 
0094         // TODO: for now ignore, later throw an exception?
0095         if ( !ok )
0096         {
0097             return true;
0098         }
0099 
0100         // check if the areal is inside the other_areal
0101         // TODO: This is O(N)
0102         // Run in a loop O(NM) - optimize!
0103         int const pig = point_in_geometry(pt,
0104                                           m_other_areal,
0105                                           m_point_in_areal_strategy);
0106         //BOOST_GEOMETRY_ASSERT( pig != 0 );
0107 
0108         // inside
0109         if ( pig > 0 )
0110         {
0111             update<interior, interior, '2', TransposeResult>(m_result);
0112             update<boundary, interior, '1', TransposeResult>(m_result);
0113             update<exterior, interior, '2', TransposeResult>(m_result);
0114             m_flags |= 1;
0115 
0116             // TODO: OPTIMIZE!
0117             // Only the interior rings of other ONE single geometry must be checked
0118             // NOT all geometries
0119 
0120             // Check if any interior ring is outside
0121             ring_identifier ring_id(0, -1, 0);
0122             std::size_t const irings_count = geometry::num_interior_rings(areal);
0123             for ( ; static_cast<std::size_t>(ring_id.ring_index) < irings_count ;
0124                     ++ring_id.ring_index )
0125             {
0126                 typename detail::sub_range_return_type<Areal const>::type
0127                     range_ref = detail::sub_range(areal, ring_id);
0128 
0129                 if ( boost::empty(range_ref) )
0130                 {
0131                     // TODO: throw exception?
0132                     continue; // ignore
0133                 }
0134 
0135                 // TODO: O(N)
0136                 // Optimize!
0137                 int const hpig = point_in_geometry(range::front(range_ref),
0138                                                    m_other_areal,
0139                                                    m_point_in_areal_strategy);
0140 
0141                 // hole outside
0142                 if ( hpig < 0 )
0143                 {
0144                     update<interior, exterior, '2', TransposeResult>(m_result);
0145                     update<boundary, exterior, '1', TransposeResult>(m_result);
0146                     m_flags |= 2;
0147                     break;
0148                 }
0149             }
0150         }
0151         // outside
0152         else
0153         {
0154             update<interior, exterior, '2', TransposeResult>(m_result);
0155             update<boundary, exterior, '1', TransposeResult>(m_result);
0156             m_flags |= 2;
0157 
0158             // Check if any interior ring is inside
0159             ring_identifier ring_id(0, -1, 0);
0160             std::size_t const irings_count = geometry::num_interior_rings(areal);
0161             for ( ; static_cast<std::size_t>(ring_id.ring_index) < irings_count ;
0162                     ++ring_id.ring_index )
0163             {
0164                 typename detail::sub_range_return_type<Areal const>::type
0165                     range_ref = detail::sub_range(areal, ring_id);
0166 
0167                 if ( boost::empty(range_ref) )
0168                 {
0169                     // TODO: throw exception?
0170                     continue; // ignore
0171                 }
0172 
0173                 // TODO: O(N)
0174                 // Optimize!
0175                 int const hpig = point_in_geometry(range::front(range_ref),
0176                                                    m_other_areal,
0177                                                    m_point_in_areal_strategy);
0178 
0179                 // hole inside
0180                 if ( hpig > 0 )
0181                 {
0182                     update<interior, interior, '2', TransposeResult>(m_result);
0183                     update<boundary, interior, '1', TransposeResult>(m_result);
0184                     update<exterior, interior, '2', TransposeResult>(m_result);
0185                     m_flags |= 1;
0186                     break;
0187                 }
0188             }
0189         }
0190 
0191         return m_flags != 3 && !m_result.interrupt;
0192     }
0193 
0194 private:
0195     Result & m_result;
0196     PointInArealStrategy const& m_point_in_areal_strategy;
0197     OtherAreal const& m_other_areal;
0198     int m_flags;
0199 };
0200 
0201 // The implementation of an algorithm calculating relate() for A/A
0202 template <typename Geometry1, typename Geometry2>
0203 struct areal_areal
0204 {
0205     // check Linear / Areal
0206     BOOST_STATIC_ASSERT(topological_dimension<Geometry1>::value == 2
0207                      && topological_dimension<Geometry2>::value == 2);
0208 
0209     static const bool interruption_enabled = true;
0210 
0211     template <typename Result, typename Strategy>
0212     static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0213                              Result & result,
0214                              Strategy const& strategy)
0215     {
0216 // TODO: If Areal geometry may have infinite size, change the following line:
0217 
0218         update<exterior, exterior, result_dimension<Geometry2>::value>(result);// FFFFFFFFd, d in [1,9] or T
0219 
0220         if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0221             return;
0222 
0223         // get and analyse turns
0224         using turn_type = typename turns::get_turns
0225             <
0226                 Geometry1, Geometry2
0227             >::template turn_info_type<Strategy>::type;
0228         std::vector<turn_type> turns;
0229 
0230         interrupt_policy_areal_areal<Result> interrupt_policy(geometry1, geometry2, result);
0231 
0232         turns::get_turns<Geometry1, Geometry2>::apply(turns, geometry1, geometry2, interrupt_policy, strategy);
0233         if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0234             return;
0235 
0236         no_turns_aa_pred<Geometry2, Result, Strategy, false>
0237             pred1(geometry2, result, strategy);
0238         for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1);
0239         if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0240             return;
0241 
0242         no_turns_aa_pred<Geometry1, Result, Strategy, true>
0243             pred2(geometry1, result, strategy);
0244         for_each_disjoint_geometry_if<1, Geometry2>::apply(turns.begin(), turns.end(), geometry2, pred2);
0245         if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0246             return;
0247 
0248         if ( turns.empty() )
0249             return;
0250 
0251         if ( may_update<interior, interior, '2'>(result)
0252           || may_update<interior, exterior, '2'>(result)
0253           || may_update<boundary, interior, '1'>(result)
0254           || may_update<boundary, exterior, '1'>(result)
0255           || may_update<exterior, interior, '2'>(result) )
0256         {
0257             // sort turns
0258             using less_t = turns::less<0, turns::less_op_areal_areal<0>, Strategy>;
0259             std::sort(turns.begin(), turns.end(), less_t());
0260 
0261             /*if ( may_update<interior, exterior, '2'>(result)
0262               || may_update<boundary, exterior, '1'>(result)
0263               || may_update<boundary, interior, '1'>(result)
0264               || may_update<exterior, interior, '2'>(result) )*/
0265             {
0266                 // analyse sorted turns
0267                 turns_analyser<turn_type, 0> analyser;
0268                 analyse_each_turn(result, analyser, turns.begin(), turns.end(), strategy);
0269 
0270                 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0271                     return;
0272             }
0273 
0274             if ( may_update<interior, interior, '2'>(result)
0275               || may_update<interior, exterior, '2'>(result)
0276               || may_update<boundary, interior, '1'>(result)
0277               || may_update<boundary, exterior, '1'>(result)
0278               || may_update<exterior, interior, '2'>(result) )
0279             {
0280                 // analyse rings for which turns were not generated
0281                 // or only i/i or u/u was generated
0282                 uncertain_rings_analyser<0, Result, Geometry1, Geometry2, Strategy>
0283                     rings_analyser(result, geometry1, geometry2, strategy);
0284                 analyse_uncertain_rings<0>::apply(rings_analyser, turns.begin(), turns.end());
0285 
0286                 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0287                     return;
0288             }
0289         }
0290 
0291         if ( may_update<interior, interior, '2', true>(result)
0292           || may_update<interior, exterior, '2', true>(result)
0293           || may_update<boundary, interior, '1', true>(result)
0294           || may_update<boundary, exterior, '1', true>(result)
0295           || may_update<exterior, interior, '2', true>(result) )
0296         {
0297             // sort turns
0298             using less_t = turns::less<1, turns::less_op_areal_areal<1>, Strategy>;
0299             std::sort(turns.begin(), turns.end(), less_t());
0300 
0301             /*if ( may_update<interior, exterior, '2', true>(result)
0302               || may_update<boundary, exterior, '1', true>(result)
0303               || may_update<boundary, interior, '1', true>(result)
0304               || may_update<exterior, interior, '2', true>(result) )*/
0305             {
0306                 // analyse sorted turns
0307                 turns_analyser<turn_type, 1> analyser;
0308                 analyse_each_turn(result, analyser, turns.begin(), turns.end(), strategy);
0309 
0310                 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0311                     return;
0312             }
0313 
0314             if ( may_update<interior, interior, '2', true>(result)
0315               || may_update<interior, exterior, '2', true>(result)
0316               || may_update<boundary, interior, '1', true>(result)
0317               || may_update<boundary, exterior, '1', true>(result)
0318               || may_update<exterior, interior, '2', true>(result) )
0319             {
0320                 // analyse rings for which turns were not generated
0321                 // or only i/i or u/u was generated
0322                 uncertain_rings_analyser<1, Result, Geometry2, Geometry1, Strategy>
0323                     rings_analyser(result, geometry2, geometry1, strategy);
0324                 analyse_uncertain_rings<1>::apply(rings_analyser, turns.begin(), turns.end());
0325 
0326                 //if ( result.interrupt )
0327                 //    return;
0328             }
0329         }
0330     }
0331 
0332     // interrupt policy which may be passed to get_turns to interrupt the analysis
0333     // based on the info in the passed result/mask
0334     template <typename Result>
0335     class interrupt_policy_areal_areal
0336     {
0337     public:
0338         static bool const enabled = true;
0339 
0340         interrupt_policy_areal_areal(Geometry1 const& geometry1,
0341                                      Geometry2 const& geometry2,
0342                                      Result & result)
0343             : m_result(result)
0344             , m_geometry1(geometry1)
0345             , m_geometry2(geometry2)
0346         {}
0347 
0348         template <typename Range>
0349         inline bool apply(Range const& turns)
0350         {
0351             for (auto it = boost::begin(turns) ; it != boost::end(turns) ; ++it)
0352             {
0353                 per_turn<0>(*it);
0354                 per_turn<1>(*it);
0355             }
0356 
0357             return m_result.interrupt;
0358         }
0359 
0360     private:
0361         template <std::size_t OpId, typename Turn>
0362         inline void per_turn(Turn const& turn)
0363         {
0364             //static const std::size_t other_op_id = (OpId + 1) % 2;
0365             static const bool transpose_result = OpId != 0;
0366 
0367             overlay::operation_type const op = turn.operations[OpId].operation;
0368 
0369             if ( op == overlay::operation_union )
0370             {
0371                 // ignore u/u
0372                 /*if ( turn.operations[other_op_id].operation != overlay::operation_union )
0373                 {
0374                     update<interior, exterior, '2', transpose_result>(m_result);
0375                     update<boundary, exterior, '1', transpose_result>(m_result);
0376                 }*/
0377 
0378                 update<boundary, boundary, '0', transpose_result>(m_result);
0379             }
0380             else if ( op == overlay::operation_intersection )
0381             {
0382                 // ignore i/i
0383                 /*if ( turn.operations[other_op_id].operation != overlay::operation_intersection )
0384                 {
0385                     // not correct e.g. for G1 touching G2 in a point where a hole is touching the exterior ring
0386                     // in this case 2 turns i/... and u/u will be generated for this IP
0387                     //update<interior, interior, '2', transpose_result>(m_result);
0388 
0389                     //update<boundary, interior, '1', transpose_result>(m_result);
0390                 }*/
0391 
0392                 update<boundary, boundary, '0', transpose_result>(m_result);
0393             }
0394             else if ( op == overlay::operation_continue )
0395             {
0396                 update<boundary, boundary, '1', transpose_result>(m_result);
0397                 update<interior, interior, '2', transpose_result>(m_result);
0398             }
0399             else if ( op == overlay::operation_blocked )
0400             {
0401                 update<boundary, boundary, '1', transpose_result>(m_result);
0402                 update<interior, exterior, '2', transpose_result>(m_result);
0403             }
0404         }
0405 
0406         Result & m_result;
0407         Geometry1 const& m_geometry1;
0408         Geometry2 const& m_geometry2;
0409     };
0410 
0411     // This analyser should be used like Input or SinglePass Iterator
0412     // IMPORTANT! It should be called also for the end iterator - last
0413     template <typename TurnInfo, std::size_t OpId>
0414     class turns_analyser
0415     {
0416         typedef typename TurnInfo::point_type turn_point_type;
0417 
0418         static const std::size_t op_id = OpId;
0419         static const std::size_t other_op_id = (OpId + 1) % 2;
0420         static const bool transpose_result = OpId != 0;
0421 
0422     public:
0423         turns_analyser()
0424             : m_previous_turn_ptr(0)
0425             , m_previous_operation(overlay::operation_none)
0426             , m_enter_detected(false)
0427             , m_exit_detected(false)
0428         {}
0429 
0430         template <typename Result, typename TurnIt, typename EqPPStrategy>
0431         void apply(Result & result, TurnIt it, EqPPStrategy const& strategy)
0432         {
0433             //BOOST_GEOMETRY_ASSERT( it != last );
0434 
0435             overlay::operation_type const op = it->operations[op_id].operation;
0436 
0437             if ( op != overlay::operation_union
0438               && op != overlay::operation_intersection
0439               && op != overlay::operation_blocked
0440               && op != overlay::operation_continue )
0441             {
0442                 return;
0443             }
0444 
0445             segment_identifier const& seg_id = it->operations[op_id].seg_id;
0446             //segment_identifier const& other_id = it->operations[other_op_id].seg_id;
0447 
0448             const bool first_in_range = m_seg_watcher.update(seg_id);
0449 
0450             if ( m_previous_turn_ptr )
0451             {
0452                 if ( m_exit_detected /*m_previous_operation == overlay::operation_union*/ )
0453                 {
0454                     // real exit point - may be multiple
0455                     if ( first_in_range
0456                       || ! turn_on_the_same_ip<op_id>(*m_previous_turn_ptr, *it, strategy) )
0457                     {
0458                         update_exit(result);
0459                         m_exit_detected = false;
0460                     }
0461                     // fake exit point, reset state
0462                     else if ( op != overlay::operation_union )
0463                     {
0464                         m_exit_detected = false;
0465                     }
0466                 }
0467                 /*else*/
0468                 if ( m_enter_detected /*m_previous_operation == overlay::operation_intersection*/ )
0469                 {
0470                     // real entry point
0471                     if ( first_in_range
0472                       || ! turn_on_the_same_ip<op_id>(*m_previous_turn_ptr, *it, strategy) )
0473                     {
0474                         update_enter(result);
0475                         m_enter_detected = false;
0476                     }
0477                     // fake entry point, reset state
0478                     else if ( op != overlay::operation_intersection )
0479                     {
0480                         m_enter_detected = false;
0481                     }
0482                 }
0483             }
0484 
0485             if ( op == overlay::operation_union )
0486             {
0487                 // already set in interrupt policy
0488                 //update<boundary, boundary, '0', transpose_result>(m_result);
0489 
0490                 // ignore u/u
0491                 //if ( it->operations[other_op_id].operation != overlay::operation_union )
0492                 {
0493                     m_exit_detected = true;
0494                 }
0495             }
0496             else if ( op == overlay::operation_intersection )
0497             {
0498                 // ignore i/i
0499                 if ( it->operations[other_op_id].operation != overlay::operation_intersection )
0500                 {
0501                     // this was set in the interrupt policy but it was wrong
0502                     // also here it's wrong since it may be a fake entry point
0503                     //update<interior, interior, '2', transpose_result>(result);
0504 
0505                     // already set in interrupt policy
0506                     //update<boundary, boundary, '0', transpose_result>(result);
0507                     m_enter_detected = true;
0508                 }
0509             }
0510             else if ( op == overlay::operation_blocked )
0511             {
0512                 // already set in interrupt policy
0513             }
0514             else // if ( op == overlay::operation_continue )
0515             {
0516                 // already set in interrupt policy
0517             }
0518 
0519             // store ref to previously analysed (valid) turn
0520             m_previous_turn_ptr = boost::addressof(*it);
0521             // and previously analysed (valid) operation
0522             m_previous_operation = op;
0523         }
0524 
0525         // it == last
0526         template <typename Result>
0527         void apply(Result & result)
0528         {
0529             //BOOST_GEOMETRY_ASSERT( first != last );
0530 
0531             if ( m_exit_detected /*m_previous_operation == overlay::operation_union*/ )
0532             {
0533                 update_exit(result);
0534                 m_exit_detected = false;
0535             }
0536 
0537             if ( m_enter_detected /*m_previous_operation == overlay::operation_intersection*/ )
0538             {
0539                 update_enter(result);
0540                 m_enter_detected = false;
0541             }
0542         }
0543 
0544         template <typename Result>
0545         static inline void update_exit(Result & result)
0546         {
0547             update<interior, exterior, '2', transpose_result>(result);
0548             update<boundary, exterior, '1', transpose_result>(result);
0549         }
0550 
0551         template <typename Result>
0552         static inline void update_enter(Result & result)
0553         {
0554             update<interior, interior, '2', transpose_result>(result);
0555             update<boundary, interior, '1', transpose_result>(result);
0556             update<exterior, interior, '2', transpose_result>(result);
0557         }
0558 
0559     private:
0560         segment_watcher<same_ring> m_seg_watcher;
0561         TurnInfo * m_previous_turn_ptr;
0562         overlay::operation_type m_previous_operation;
0563         bool m_enter_detected;
0564         bool m_exit_detected;
0565     };
0566 
0567     // call analyser.apply() for each turn in range
0568     // IMPORTANT! The analyser is also called for the end iterator - last
0569     template
0570     <
0571         typename Result,
0572         typename Analyser,
0573         typename TurnIt,
0574         typename EqPPStrategy
0575     >
0576     static inline void analyse_each_turn(Result & res,
0577                                          Analyser & analyser,
0578                                          TurnIt first, TurnIt last,
0579                                          EqPPStrategy const& strategy)
0580     {
0581         if ( first == last )
0582             return;
0583 
0584         for ( TurnIt it = first ; it != last ; ++it )
0585         {
0586             analyser.apply(res, it, strategy);
0587 
0588             if ( BOOST_GEOMETRY_CONDITION(res.interrupt) )
0589                 return;
0590         }
0591 
0592         analyser.apply(res);
0593     }
0594 
0595     template
0596     <
0597         std::size_t OpId,
0598         typename Result,
0599         typename Geometry,
0600         typename OtherGeometry,
0601         typename PointInArealStrategy
0602     >
0603     class uncertain_rings_analyser
0604     {
0605         static const bool transpose_result = OpId != 0;
0606         static const int other_id = (OpId + 1) % 2;
0607 
0608     public:
0609         inline uncertain_rings_analyser(Result & result,
0610                                         Geometry const& geom,
0611                                         OtherGeometry const& other_geom,
0612                                         PointInArealStrategy const& point_in_areal_strategy)
0613             : geometry(geom)
0614             , other_geometry(other_geom)
0615             , interrupt(result.interrupt) // just in case, could be false as well
0616             , m_result(result)
0617             , m_point_in_areal_strategy(point_in_areal_strategy)
0618             , m_flags(0)
0619         {
0620             // check which relations must be analysed
0621             // NOTE: 1 and 4 could probably be connected
0622 
0623             if ( ! may_update<interior, interior, '2', transpose_result>(m_result) )
0624             {
0625                 m_flags |= 1;
0626             }
0627 
0628             if ( ! may_update<interior, exterior, '2', transpose_result>(m_result)
0629               && ! may_update<boundary, exterior, '1', transpose_result>(m_result) )
0630             {
0631                 m_flags |= 2;
0632             }
0633 
0634             if ( ! may_update<boundary, interior, '1', transpose_result>(m_result)
0635               && ! may_update<exterior, interior, '2', transpose_result>(m_result) )
0636             {
0637                 m_flags |= 4;
0638             }
0639         }
0640 
0641         inline void no_turns(segment_identifier const& seg_id)
0642         {
0643             // if those flags are set nothing will change
0644             if ( m_flags == 7 )
0645             {
0646                 return;
0647             }
0648 
0649             auto const& sub_range = detail::sub_range(geometry, seg_id);
0650 
0651             if ( boost::empty(sub_range) )
0652             {
0653                 // TODO: throw an exception?
0654                 return; // ignore
0655             }
0656 
0657             // TODO: possible optimization
0658             // if the range is an interior ring we may use other IPs generated for this single geometry
0659             // to know which other single geometries should be checked
0660 
0661             // TODO: optimize! e.g. use spatial index
0662             // O(N) - running it in a loop gives O(NM)
0663             using detail::within::point_in_geometry;
0664             int const pig = point_in_geometry(range::front(sub_range),
0665                                               other_geometry,
0666                                               m_point_in_areal_strategy);
0667 
0668             //BOOST_GEOMETRY_ASSERT(pig != 0);
0669             if ( pig > 0 )
0670             {
0671                 update<interior, interior, '2', transpose_result>(m_result);
0672                 m_flags |= 1;
0673 
0674                 update<boundary, interior, '1', transpose_result>(m_result);
0675                 update<exterior, interior, '2', transpose_result>(m_result);
0676                 m_flags |= 4;
0677             }
0678             else
0679             {
0680                 update<boundary, exterior, '1', transpose_result>(m_result);
0681                 update<interior, exterior, '2', transpose_result>(m_result);
0682                 m_flags |= 2;
0683             }
0684 
0685 // TODO: break if all things are set
0686 // also some of them could be checked outside, before the analysis
0687 // In this case we shouldn't relay just on dummy flags
0688 // Flags should be initialized with proper values
0689 // or the result should be checked directly
0690 // THIS IS ALSO TRUE FOR OTHER ANALYSERS! in L/L and L/A
0691 
0692             interrupt = m_flags == 7 || m_result.interrupt;
0693         }
0694 
0695         template <typename TurnIt>
0696         inline void turns(TurnIt first, TurnIt last)
0697         {
0698             // if those flags are set nothing will change
0699             if ( (m_flags & 6) == 6 )
0700             {
0701                 return;
0702             }
0703 
0704             bool found_ii = false;
0705             bool found_uu = false;
0706 
0707             for ( TurnIt it = first ; it != last ; ++it )
0708             {
0709                 if ( it->operations[0].operation == overlay::operation_intersection
0710                   && it->operations[1].operation == overlay::operation_intersection )
0711                 {
0712                     found_ii = true;
0713                 }
0714                 else if ( it->operations[0].operation == overlay::operation_union
0715                        && it->operations[1].operation == overlay::operation_union )
0716                 {
0717                     found_uu = true;
0718                 }
0719                 else // ignore
0720                 {
0721                     return; // don't interrupt
0722                 }
0723             }
0724 
0725             // only i/i was generated for this ring
0726             if ( found_ii )
0727             {
0728                 update<interior, interior, '2', transpose_result>(m_result);
0729                 m_flags |= 1;
0730 
0731                 //update<boundary, boundary, '0', transpose_result>(m_result);
0732 
0733                 update<boundary, interior, '1', transpose_result>(m_result);
0734                 update<exterior, interior, '2', transpose_result>(m_result);
0735                 m_flags |= 4;
0736             }
0737 
0738             // only u/u was generated for this ring
0739             if ( found_uu )
0740             {
0741                 update<boundary, exterior, '1', transpose_result>(m_result);
0742                 update<interior, exterior, '2', transpose_result>(m_result);
0743                 m_flags |= 2;
0744             }
0745 
0746             interrupt = m_flags == 7 || m_result.interrupt; // interrupt if the result won't be changed in the future
0747         }
0748 
0749         Geometry const& geometry;
0750         OtherGeometry const& other_geometry;
0751         bool interrupt;
0752 
0753     private:
0754         Result & m_result;
0755         PointInArealStrategy const& m_point_in_areal_strategy;
0756         int m_flags;
0757     };
0758 
0759     template <std::size_t OpId>
0760     class analyse_uncertain_rings
0761     {
0762     public:
0763         template <typename Analyser, typename TurnIt>
0764         static inline void apply(Analyser & analyser, TurnIt first, TurnIt last)
0765         {
0766             if ( first == last )
0767                 return;
0768 
0769             for_preceding_rings(analyser, *first);
0770             //analyser.per_turn(*first);
0771 
0772             TurnIt prev = first;
0773             for ( ++first ; first != last ; ++first, ++prev )
0774             {
0775                 // same multi
0776                 if ( prev->operations[OpId].seg_id.multi_index
0777                   == first->operations[OpId].seg_id.multi_index )
0778                 {
0779                     // same ring
0780                     if ( prev->operations[OpId].seg_id.ring_index
0781                       == first->operations[OpId].seg_id.ring_index )
0782                     {
0783                         //analyser.per_turn(*first);
0784                     }
0785                     // same multi, next ring
0786                     else
0787                     {
0788                         //analyser.end_ring(*prev);
0789                         analyser.turns(prev, first);
0790 
0791                         //if ( prev->operations[OpId].seg_id.ring_index + 1
0792                         //   < first->operations[OpId].seg_id.ring_index)
0793                         {
0794                             for_no_turns_rings(analyser,
0795                                                *first,
0796                                                prev->operations[OpId].seg_id.ring_index + 1,
0797                                                first->operations[OpId].seg_id.ring_index);
0798                         }
0799 
0800                         //analyser.per_turn(*first);
0801                     }
0802                 }
0803                 // next multi
0804                 else
0805                 {
0806                     //analyser.end_ring(*prev);
0807                     analyser.turns(prev, first);
0808                     for_following_rings(analyser, *prev);
0809                     for_preceding_rings(analyser, *first);
0810                     //analyser.per_turn(*first);
0811                 }
0812 
0813                 if ( analyser.interrupt )
0814                 {
0815                     return;
0816                 }
0817             }
0818 
0819             //analyser.end_ring(*prev);
0820             analyser.turns(prev, first); // first == last
0821             for_following_rings(analyser, *prev);
0822         }
0823 
0824     private:
0825         template <typename Analyser, typename Turn>
0826         static inline void for_preceding_rings(Analyser & analyser, Turn const& turn)
0827         {
0828             segment_identifier const& seg_id = turn.operations[OpId].seg_id;
0829 
0830             for_no_turns_rings(analyser, turn, -1, seg_id.ring_index);
0831         }
0832 
0833         template <typename Analyser, typename Turn>
0834         static inline void for_following_rings(Analyser & analyser, Turn const& turn)
0835         {
0836             segment_identifier const& seg_id = turn.operations[OpId].seg_id;
0837 
0838             signed_size_type
0839                 count = boost::numeric_cast<signed_size_type>(
0840                             geometry::num_interior_rings(
0841                                 detail::single_geometry(analyser.geometry, seg_id)));
0842 
0843             for_no_turns_rings(analyser, turn, seg_id.ring_index + 1, count);
0844         }
0845 
0846         template <typename Analyser, typename Turn>
0847         static inline void for_no_turns_rings(Analyser & analyser,
0848                                               Turn const& turn,
0849                                               signed_size_type first,
0850                                               signed_size_type last)
0851         {
0852             segment_identifier seg_id = turn.operations[OpId].seg_id;
0853 
0854             for ( seg_id.ring_index = first ; seg_id.ring_index < last ; ++seg_id.ring_index )
0855             {
0856                 analyser.no_turns(seg_id);
0857             }
0858         }
0859     };
0860 };
0861 
0862 }} // namespace detail::relate
0863 #endif // DOXYGEN_NO_DETAIL
0864 
0865 }} // namespace boost::geometry
0866 
0867 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_AREAL_AREAL_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!