Imported Upstream version 1.65.0upstream/1.65.0

Change-Id: Icf8400b375482cb11bcf77440a6934ba360d6ba4
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>

1 files changed, 33 insertions, 21 deletions

diff --git a/boost/geometry/algorithms/detail/relate/point_point.hpp b/boost/geometry/algorithms/detail/relate/point_point.hpp
index b41d346f0b..68d8be031e 100644
--- a/boost/geometry/algorithms/detail/relate/point_point.hpp
+++ b/boost/geometry/algorithms/detail/relate/point_point.hpp
@@ -165,22 +165,41 @@ struct multipoint_multipoint
             }
         }
 
-// TODO: ADD A CHECK TO THE RESULT INDICATING IF THE FIRST AND/OR SECOND GEOMETRY MUST BE ANALYSED
+        // The geometry containing smaller number of points will be analysed first
+        if ( boost::size(multi_point1) < boost::size(multi_point2) )
+        {
+            search_both<false>(multi_point1, multi_point2, result);
+        }
+        else
+        {
+            search_both<true>(multi_point2, multi_point1, result);
+        }
 
-// TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed
-//       so if e.g. only I/I must be analysed we musn't check the other MPt
+        relate::set<exterior, exterior, result_dimension<MultiPoint1>::value>(result);
+    }
 
-// TODO: Also, the geometry with the smaller number of points may be analysed first
-        //if ( boost::size(multi_point1) < boost::size(multi_point2) )
+    template <bool Transpose, typename MPt1, typename MPt2, typename Result>
+    static inline void search_both(MPt1 const& first_sorted_mpt, MPt2 const& first_iterated_mpt,
+                                   Result & result)
+    {
+        if ( relate::may_update<interior, interior, '0'>(result)
+          || relate::may_update<interior, exterior, '0'>(result)
+          || relate::may_update<exterior, interior, '0'>(result) )
+        {
+            // NlogN + MlogN
+            bool is_disjoint = search<Transpose>(first_sorted_mpt, first_iterated_mpt, result);
 
-        // NlogN + MlogN
-        bool all_handled = search<false>(multi_point1, multi_point2, result);
-        
-        if ( BOOST_GEOMETRY_CONDITION(all_handled || result.interrupt) )
-            return;
+            if ( BOOST_GEOMETRY_CONDITION(is_disjoint || result.interrupt) )
+                return;
+        }
 
-        // MlogM + NlogM
-        search<true>(multi_point2, multi_point1, result);
+        if ( relate::may_update<interior, interior, '0'>(result)
+          || relate::may_update<interior, exterior, '0'>(result)
+          || relate::may_update<exterior, interior, '0'>(result) )
+        {
+            // MlogM + NlogM
+            search<! Transpose>(first_iterated_mpt, first_sorted_mpt, result);
+        }
     }
 
     template <bool Transpose,
@@ -215,9 +234,6 @@ struct multipoint_multipoint
                 break;
         }
 
-        // an optimization
-        bool all_handled = false;
-
         if ( found_inside ) // some point of MP2 is equal to some of MP1
         {
 // TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed
@@ -234,14 +250,10 @@ struct multipoint_multipoint
         {
             relate::set<interior, exterior, '0', Transpose>(result);
             relate::set<exterior, interior, '0', Transpose>(result);
-
-            // if no point is intersecting the other MPt then we musn't analyse the reversed case
-            all_handled = true;
         }
 
-        relate::set<exterior, exterior, result_dimension<point_type>::value, Transpose>(result);
-
-        return all_handled;
+        // if no point is intersecting the other MPt then we musn't analyse the reversed case
+        return ! found_inside;
     }
 };