Imported Upstream version 1.58.0upstream/1.58.0

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

6 files changed, 309 insertions, 147 deletions

diff --git a/boost/geometry/algorithms/detail/is_simple/areal.hpp b/boost/geometry/algorithms/detail/is_simple/areal.hpp
index 9a1a16507a..623632c44e 100644
--- a/boost/geometry/algorithms/detail/is_simple/areal.hpp
+++ b/boost/geometry/algorithms/detail/is_simple/areal.hpp
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
-// Copyright (c) 2014, Oracle and/or its affiliates.
+// Copyright (c) 2014-2015, Oracle and/or its affiliates.
 
 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
 
@@ -19,6 +19,7 @@
 #include <boost/geometry/core/tags.hpp>
 
 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
+#include <boost/geometry/algorithms/detail/is_simple/failure_policy.hpp>
 #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp>
 
 #include <boost/geometry/algorithms/dispatch/is_simple.hpp>
@@ -38,11 +39,12 @@ struct is_simple_ring
 {
     static inline bool apply(Ring const& ring)
     {
+        simplicity_failure_policy policy;
         return
             !detail::is_valid::has_duplicates
                 <
                     Ring, geometry::closure<Ring>::value
-                >::apply(ring);
+                >::apply(ring, policy);
     }
 };
 
diff --git a/boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp b/boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp
index 75c37c68f8..196d89b925 100644
--- a/boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp
+++ b/boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
-// Copyright (c) 2014, Oracle and/or its affiliates.
+// Copyright (c) 2014-2015, Oracle and/or its affiliates.
 
 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
 
@@ -18,6 +18,8 @@
 #include <boost/range.hpp>
 
 #include <boost/geometry/core/point_type.hpp>
+#include <boost/geometry/core/tag.hpp>
+#include <boost/geometry/core/tags.hpp>
 
 #include <boost/geometry/util/range.hpp>
 
@@ -26,7 +28,8 @@
 #include <boost/geometry/policies/compare.hpp>
 
 #include <boost/geometry/algorithms/equals.hpp>
-#endif
+#include <boost/geometry/algorithms/not_implemented.hpp>
+#endif // BOOST_GEOMETRY_TEST_DEBUG
 
 
 namespace boost { namespace geometry
@@ -37,39 +40,67 @@ namespace detail { namespace is_simple
 
 
 #ifdef BOOST_GEOMETRY_TEST_DEBUG
-template <typename MultiLinestring>
-inline void debug_print_boundary_points(MultiLinestring const& multilinestring)
+template <typename Linear, typename Tag = typename tag<Linear>::type>
+struct debug_boundary_points_printer
+    : not_implemented<Linear>
+{};
+
+template <typename Linestring>
+struct debug_boundary_points_printer<Linestring, linestring_tag>
 {
-    typedef typename point_type<MultiLinestring>::type point_type;
-    typedef std::vector<point_type> point_vector;
+    static inline void apply(Linestring const& linestring)
+    {
+        std::cout << "boundary points: ";
+        std::cout << " " << geometry::dsv(range::front(linestring));
+        std::cout << " " << geometry::dsv(range::back(linestring));
+        std::cout << std::endl << std::endl;
+    }
+};
 
-    point_vector boundary_points;
-    for (typename boost::range_iterator<MultiLinestring const>::type it
-             = boost::begin(multilinestring);
-         it != boost::end(multilinestring); ++it)
+template <typename MultiLinestring>
+struct debug_boundary_points_printer<MultiLinestring, multi_linestring_tag>
+{
+    static inline void apply(MultiLinestring const& multilinestring)
     {
-        if ( boost::size(*it) > 1
-             && !geometry::equals(range::front(*it), range::back(*it)) )
+        typedef typename point_type<MultiLinestring>::type point_type;
+        typedef std::vector<point_type> point_vector;
+
+        point_vector boundary_points;
+        for (typename boost::range_iterator<MultiLinestring const>::type it
+                 = boost::begin(multilinestring);
+             it != boost::end(multilinestring); ++it)
         {
-            boundary_points.push_back( range::front(*it) );
-            boundary_points.push_back( range::back(*it) );
+            if ( boost::size(*it) > 1
+                 && !geometry::equals(range::front(*it), range::back(*it)) )
+            {
+                boundary_points.push_back( range::front(*it) );
+                boundary_points.push_back( range::back(*it) );
+            }
         }
-    }
 
-    std::sort(boundary_points.begin(), boundary_points.end(),
-              geometry::less<point_type>());
+        std::sort(boundary_points.begin(), boundary_points.end(),
+                  geometry::less<point_type>());
 
-    std::cout << "boundary points: ";
-    for (typename point_vector::const_iterator pit = boundary_points.begin();
-         pit != boundary_points.end(); ++pit)
-    {
-        std::cout << " " << geometry::dsv(*pit);
+        std::cout << "boundary points: ";
+        for (typename point_vector::const_iterator
+                 pit = boundary_points.begin();
+             pit != boundary_points.end(); ++pit)
+        {
+            std::cout << " " << geometry::dsv(*pit);
+        }
+        std::cout << std::endl << std::endl;
     }
-    std::cout << std::endl << std::endl;
+};
+
+
+template <typename Linear>
+inline void debug_print_boundary_points(Linear const& linear)
+{
+    debug_boundary_points_printer<Linear>::apply(linear);
 }
 #else
-template <typename MultiLinestring>
-inline void debug_print_boundary_points(MultiLinestring const&)
+template <typename Linear>
+inline void debug_print_boundary_points(Linear const&)
 {
 }
 #endif // BOOST_GEOMETRY_TEST_DEBUG
diff --git a/boost/geometry/algorithms/detail/is_simple/failure_policy.hpp b/boost/geometry/algorithms/detail/is_simple/failure_policy.hpp
new file mode 100644
index 0000000000..6504edd1d5
--- /dev/null
+++ b/boost/geometry/algorithms/detail/is_simple/failure_policy.hpp
@@ -0,0 +1,53 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2015, Oracle and/or its affiliates.
+
+// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+
+// Licensed under the Boost Software License version 1.0.
+// http://www.boost.org/users/license.html
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_FAILURE_POLICY_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_FAILURE_POLICY_HPP
+
+#include <boost/geometry/algorithms/validity_failure_type.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace is_simple
+{
+
+
+struct simplicity_failure_policy
+{
+    template <validity_failure_type Failure>
+    static inline bool apply()
+    {
+        return Failure == no_failure;
+    }
+
+    template <validity_failure_type Failure, typename Data>
+    static inline bool apply(Data const&)
+    {
+        return apply<Failure>();
+    }
+
+    template <validity_failure_type Failure, typename Data1, typename Data2>
+    static inline bool apply(Data1 const&, Data2 const&)
+    {
+        return apply<Failure>();
+    }
+};
+
+
+}} // namespace detail::is_simple
+#endif // DOXYGEN_NO_DETAIL
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_FAILURE_POLICY_HPP
diff --git a/boost/geometry/algorithms/detail/is_simple/interface.hpp b/boost/geometry/algorithms/detail/is_simple/interface.hpp
index 4239664ed1..fd84826970 100644
--- a/boost/geometry/algorithms/detail/is_simple/interface.hpp
+++ b/boost/geometry/algorithms/detail/is_simple/interface.hpp
@@ -10,8 +10,8 @@
 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_INTERFACE_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_INTERFACE_HPP
 
-#include <boost/variant/static_visitor.hpp>
 #include <boost/variant/apply_visitor.hpp>
+#include <boost/variant/static_visitor.hpp>
 #include <boost/variant/variant_fwd.hpp>
 
 #include <boost/geometry/geometries/concepts/check.hpp>
diff --git a/boost/geometry/algorithms/detail/is_simple/linear.hpp b/boost/geometry/algorithms/detail/is_simple/linear.hpp
index f2efcb309d..4f3e875eef 100644
--- a/boost/geometry/algorithms/detail/is_simple/linear.hpp
+++ b/boost/geometry/algorithms/detail/is_simple/linear.hpp
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
-// Copyright (c) 2014, Oracle and/or its affiliates.
+// Copyright (c) 2014-2015, Oracle and/or its affiliates.
 
 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
 
@@ -19,6 +19,7 @@
 #include <boost/geometry/core/closure.hpp>
 #include <boost/geometry/core/coordinate_type.hpp>
 #include <boost/geometry/core/point_type.hpp>
+#include <boost/geometry/core/tag.hpp>
 #include <boost/geometry/core/tags.hpp>
 
 #include <boost/geometry/util/range.hpp>
@@ -29,8 +30,10 @@
 
 #include <boost/geometry/algorithms/equals.hpp>
 #include <boost/geometry/algorithms/intersects.hpp>
+#include <boost/geometry/algorithms/not_implemented.hpp>
 
 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
+#include <boost/geometry/algorithms/detail/signed_index_type.hpp>
 
 #include <boost/geometry/algorithms/detail/disjoint/linear_linear.hpp>
 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
@@ -40,6 +43,7 @@
 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
 
 #include <boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp>
+#include <boost/geometry/algorithms/detail/is_simple/failure_policy.hpp>
 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
 
 #include <boost/geometry/algorithms/dispatch/is_simple.hpp>
@@ -54,108 +58,211 @@ namespace detail { namespace is_simple
 {
 
 
-template <typename Linestring, bool CheckSelfIntersections = true>
-struct is_simple_linestring
+template <typename Turn>
+inline bool check_segment_indices(Turn const& turn,
+                                  signed_index_type last_index)
 {
-    static inline bool apply(Linestring const& linestring)
+    return
+        (turn.operations[0].seg_id.segment_index == 0
+         && turn.operations[1].seg_id.segment_index == last_index)
+        ||
+        (turn.operations[0].seg_id.segment_index == 0
+         && turn.operations[1].seg_id.segment_index == last_index);
+}
+
+
+template <typename Geometry, typename Tag = typename tag<Geometry>::type>
+class is_acceptable_turn
+    : not_implemented<Geometry>
+{};
+
+template <typename Linestring>
+class is_acceptable_turn<Linestring, linestring_tag>
+{
+public:
+    is_acceptable_turn(Linestring const& linestring)
+        : m_linestring(linestring)
+        , m_is_closed(geometry::equals(range::front(linestring),
+                                       range::back(linestring)))
+    {}
+
+    template <typename Turn>
+    inline bool apply(Turn const& turn) const
     {
-        return !detail::is_valid::has_duplicates
-                    <
-                        Linestring, closed
-                    >::apply(linestring)
-            && !detail::is_valid::has_spikes
-                    <
-                        Linestring, closed
-                    >::apply(linestring)
-            && !(CheckSelfIntersections && geometry::intersects(linestring));
+        BOOST_ASSERT(boost::size(m_linestring) > 1);
+        return m_is_closed
+            && turn.method == overlay::method_none
+            && check_segment_indices(turn, boost::size(m_linestring) - 2)
+            && turn.operations[0].fraction.is_zero();
     }
-};
-
 
+private:
+    Linestring const& m_linestring;
+    bool const m_is_closed;
+};
 
 template <typename MultiLinestring>
-class is_simple_multilinestring
+class is_acceptable_turn<MultiLinestring, multi_linestring_tag>
 {
 private:
-    class is_acceptable_turn
+    typedef typename boost::range_value<MultiLinestring>::type linestring_type;
+    typedef is_acceptable_turn<linestring_type> base_type;
+
+    template <typename Point, typename Linestring>
+    static inline bool is_boundary_point_of(Point const& point,
+                                            Linestring const& linestring)
     {
-    private:
-        template <typename Point, typename Linestring>
-        static inline bool is_boundary_point_of(Point const& point,
-                                                Linestring const& linestring)
-        {
-            BOOST_ASSERT( boost::size(linestring) > 1 );
-            return
-                !geometry::equals(range::front(linestring),
-                                  range::back(linestring))
-                &&
-                ( geometry::equals(point, range::front(linestring))
-                  || geometry::equals(point, range::back(linestring)) );
-        }
+        BOOST_ASSERT(boost::size(linestring) > 1);
+        return
+            ! geometry::equals(range::front(linestring),
+                               range::back(linestring))
+            &&
+            (geometry::equals(point, range::front(linestring))
+             || geometry::equals(point, range::back(linestring)));
+    }
+
+    template <typename Turn, typename Linestring>
+    static inline bool is_closing_point_of(Turn const& turn,
+                                           Linestring const& linestring)
+    {
+        BOOST_ASSERT(boost::size(linestring) > 1);
+        return
+            turn.method == overlay::method_none
+            &&
+            check_segment_indices(turn, boost::size(linestring) - 2)
+            &&
+            geometry::equals(range::front(linestring), range::back(linestring))
+            &&
+            turn.operations[0].fraction.is_zero();
+            ;
+    }
+
+    template <typename Linestring1, typename Linestring2>
+    static inline bool have_same_boundary_points(Linestring1 const& ls1,
+                                                 Linestring2 const& ls2)
+    {
+        return
+            geometry::equals(range::front(ls1), range::front(ls2))
+            ?
+            geometry::equals(range::back(ls1), range::back(ls2))
+            :
+            (geometry::equals(range::front(ls1), range::back(ls2))
+             &&
+             geometry::equals(range::back(ls1), range::front(ls2)))
+            ;
+    }
+
+public:
+    is_acceptable_turn(MultiLinestring const& multilinestring)
+        : m_multilinestring(multilinestring)
+    {}
+
+    template <typename Turn>
+    inline bool apply(Turn const& turn) const
+    {
+        linestring_type const& ls1 =
+            range::at(m_multilinestring, turn.operations[0].seg_id.multi_index);
 
-        template <typename Linestring1, typename Linestring2>
-        static inline bool have_same_boundary_points(Linestring1 const& ls1,
-                                                     Linestring2 const& ls2)
+        linestring_type const& ls2 =
+            range::at(m_multilinestring, turn.operations[1].seg_id.multi_index);
+
+        if (turn.operations[0].seg_id.multi_index
+            == turn.operations[1].seg_id.multi_index)
         {
-            return
-                geometry::equals(range::front(ls1), range::front(ls2))
-                ?
-                geometry::equals(range::back(ls1), range::back(ls2))
-                :
-                (geometry::equals(range::front(ls1), range::back(ls2))
-                 &&
-                 geometry::equals(range::back(ls1), range::front(ls2))
-                 )
-                ;
+            return is_closing_point_of(turn, ls1);
         }
 
-    public:
-        is_acceptable_turn(MultiLinestring const& multilinestring)
-            : m_multilinestring(multilinestring)
-        {}
+        return
+            is_boundary_point_of(turn.point, ls1)
+            && is_boundary_point_of(turn.point, ls2)
+            &&
+            ( boost::size(ls1) != 2
+              || boost::size(ls2) != 2
+              || ! have_same_boundary_points(ls1, ls2) );
+    }
 
-        template <typename Turn>
-        inline bool apply(Turn const& turn) const
-        {
-            typedef typename boost::range_value
+private:
+    MultiLinestring const& m_multilinestring;
+};
+
+
+template <typename Linear>
+inline bool has_self_intersections(Linear const& linear)
+{
+    typedef typename point_type<Linear>::type point_type;
+
+    // compute self turns
+    typedef detail::overlay::turn_info
+        <
+            point_type,
+            geometry::segment_ratio
                 <
-                    MultiLinestring
-                >::type linestring;
-
-            linestring const& ls1 =
-                range::at(m_multilinestring,
-                          turn.operations[0].seg_id.multi_index);
-
-            linestring const& ls2 =
-                range::at(m_multilinestring,
-                          turn.operations[1].seg_id.multi_index);
-
-            return
-                is_boundary_point_of(turn.point, ls1)
-                && is_boundary_point_of(turn.point, ls2)
-                &&
-                ( boost::size(ls1) != 2
-                  || boost::size(ls2) != 2
-                  || !have_same_boundary_points(ls1, ls2) );
-        }
+                    typename geometry::coordinate_type<point_type>::type
+                >
+        > turn_info;
 
-    private:
-        MultiLinestring const& m_multilinestring;        
-    };
+    std::deque<turn_info> turns;
 
+    typedef detail::overlay::get_turn_info
+        <
+            detail::disjoint::assign_disjoint_policy
+        > turn_policy;
 
-public:
-    static inline bool apply(MultiLinestring const& multilinestring)
+    is_acceptable_turn<Linear> predicate(linear);
+    detail::overlay::predicate_based_interrupt_policy
+        <
+            is_acceptable_turn<Linear>
+        > interrupt_policy(predicate);
+
+    detail::self_get_turn_points::get_turns
+        <
+            turn_policy
+        >::apply(linear,
+                 detail::no_rescale_policy(),
+                 turns,
+                 interrupt_policy);
+
+    detail::is_valid::debug_print_turns(turns.begin(), turns.end());
+    debug_print_boundary_points(linear);
+
+    return interrupt_policy.has_intersections;
+}
+
+
+template <typename Linestring, bool CheckSelfIntersections = true>
+struct is_simple_linestring
+{
+    static inline bool apply(Linestring const& linestring)
     {
-        typedef typename boost::range_value<MultiLinestring>::type linestring;
-        typedef typename point_type<MultiLinestring>::type point_type;
-        typedef point_type point;
+        simplicity_failure_policy policy;
+        return ! detail::is_valid::has_duplicates
+                    <
+                        Linestring, closed
+                    >::apply(linestring, policy)
+            && ! detail::is_valid::has_spikes
+                    <
+                        Linestring, closed
+                    >::apply(linestring, policy)
+            && ! (CheckSelfIntersections && has_self_intersections(linestring));
+    }
+};
 
 
+template <typename MultiLinestring>
+struct is_simple_multilinestring
+{
+    static inline bool apply(MultiLinestring const& multilinestring)
+    {
         // check each of the linestrings for simplicity
-        if ( !detail::check_iterator_range
+        // but do not compute self-intersections yet; these will be
+        // computed for the entire multilinestring
+        if ( ! detail::check_iterator_range
                  <
-                     is_simple_linestring<linestring>,
+                     is_simple_linestring
+                         <
+                             typename boost::range_value<MultiLinestring>::type,
+                             false // do not compute self-intersections
+                         >,
                      false // do not allow empty multilinestring
                  >::apply(boost::begin(multilinestring),
                           boost::end(multilinestring))
@@ -164,44 +271,8 @@ public:
             return false;
         }
 
-
-        // compute self turns
-        typedef detail::overlay::turn_info
-            <
-                point_type,
-                geometry::segment_ratio
-                <
-                    typename geometry::coordinate_type<point>::type
-                >
-            > turn_info;
-
-        std::deque<turn_info> turns;
-
-        typedef detail::overlay::get_turn_info
-            <
-                detail::disjoint::assign_disjoint_policy
-            > turn_policy;
-
-        is_acceptable_turn predicate(multilinestring);
-        detail::overlay::predicate_based_interrupt_policy
-            <
-                is_acceptable_turn
-            > interrupt_policy(predicate);
-
-        detail::self_get_turn_points::get_turns
-            <
-                turn_policy
-            >::apply(multilinestring,
-                     detail::no_rescale_policy(),
-                     turns,
-                     interrupt_policy);
-
-        detail::is_valid::debug_print_turns(turns.begin(), turns.end());
-        debug_print_boundary_points(multilinestring);
-
-        return !interrupt_policy.has_intersections;
+        return ! has_self_intersections(multilinestring);
     }
-
 };
 
 
diff --git a/boost/geometry/algorithms/detail/is_simple/multipoint.hpp b/boost/geometry/algorithms/detail/is_simple/multipoint.hpp
index d996eb64e9..71c9e6ba90 100644
--- a/boost/geometry/algorithms/detail/is_simple/multipoint.hpp
+++ b/boost/geometry/algorithms/detail/is_simple/multipoint.hpp
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
-// Copyright (c) 2014, Oracle and/or its affiliates.
+// Copyright (c) 2014-2015, Oracle and/or its affiliates.
 
 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
 
@@ -21,6 +21,7 @@
 #include <boost/geometry/policies/compare.hpp>
 
 #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp>
+#include <boost/geometry/algorithms/detail/is_simple/failure_policy.hpp>
 
 #include <boost/geometry/algorithms/dispatch/is_simple.hpp>
 
@@ -48,7 +49,11 @@ struct is_simple_multipoint
         std::sort(boost::begin(mp), boost::end(mp),
                   geometry::less<typename point_type<MultiPoint>::type>());
 
-        return !detail::is_valid::has_duplicates<MultiPoint, closed>::apply(mp);
+        simplicity_failure_policy policy;
+        return !detail::is_valid::has_duplicates
+            <
+                MultiPoint, closed
+            >::apply(mp, policy);
     }
 };