1 files changed, 134 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/relate/boundary_checker.hpp b/boost/geometry/algorithms/detail/relate/boundary_checker.hpp
new file mode 100644
index 0000000000..f98c3e9b82
--- /dev/null
+++ b/boost/geometry/algorithms/detail/relate/boundary_checker.hpp
@@ -0,0 +1,134 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2014 Oracle and/or its affiliates.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
+
+#include <boost/geometry/util/range.hpp>
+#include <boost/geometry/algorithms/num_points.hpp>
+#include <boost/geometry/algorithms/detail/sub_range.hpp>
+
+#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace relate {
+
+enum boundary_query { boundary_front, boundary_back, boundary_any };
+
+template <typename Geometry,
+          typename Tag = typename geometry::tag<Geometry>::type>
+class boundary_checker {};
+
+template <typename Geometry>
+class boundary_checker<Geometry, linestring_tag>
+{
+    typedef typename point_type<Geometry>::type point_type;
+
+public:
+    boundary_checker(Geometry const& g)
+        : has_boundary( boost::size(g) >= 2
+                     && !detail::equals::equals_point_point(range::front(g), range::back(g)) )
+        , geometry(g)
+    {}
+
+    template <boundary_query BoundaryQuery>
+    bool is_endpoint_boundary(point_type const& pt) const
+    {
+        boost::ignore_unused_variable_warning(pt);
+#ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
+        // may give false positives for INT
+        BOOST_ASSERT( (BoundaryQuery == boundary_front || BoundaryQuery == boundary_any)
+                   && detail::equals::equals_point_point(pt, range::front(geometry))
+                   || (BoundaryQuery == boundary_back || BoundaryQuery == boundary_any)
+                   && detail::equals::equals_point_point(pt, range::back(geometry)) );
+#endif
+        return has_boundary;
+    }
+
+private:
+    bool has_boundary;
+    Geometry const& geometry;
+};
+
+template <typename Geometry>
+class boundary_checker<Geometry, multi_linestring_tag>
+{
+    typedef typename point_type<Geometry>::type point_type;
+
+public:
+    boundary_checker(Geometry const& g)
+        : is_filled(false), geometry(g)
+    {}
+
+    // First call O(NlogN)
+    // Each next call O(logN)
+    template <boundary_query BoundaryQuery>
+    bool is_endpoint_boundary(point_type const& pt) const
+    {
+        typedef typename boost::range_size<Geometry>::type size_type;
+        size_type multi_count = boost::size(geometry);
+
+        if ( multi_count < 1 )
+            return false;
+
+        if ( ! is_filled )
+        {
+            //boundary_points.clear();
+            boundary_points.reserve(multi_count * 2);
+
+            typedef typename boost::range_iterator<Geometry const>::type multi_iterator;
+            for ( multi_iterator it = boost::begin(geometry) ;
+                  it != boost::end(geometry) ; ++ it )
+            {
+                // empty or point - no boundary
+                if ( boost::size(*it) < 2 )
+                    continue;
+
+                // linear ring or point - no boundary
+                if ( equals::equals_point_point(range::front(*it), range::back(*it)) )
+                    continue;
+
+                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>());
+
+            is_filled = true;
+        }
+
+        std::size_t equal_points_count
+            = boost::size(
+                std::equal_range(boundary_points.begin(),
+                                 boundary_points.end(),
+                                 pt,
+                                 geometry::less<point_type>())
+            );
+
+        return equal_points_count % 2 != 0;// && equal_points_count > 0; // the number is odd and > 0
+    }
+
+private:
+    mutable bool is_filled;
+    // TODO: store references/pointers instead of points?
+    mutable std::vector<point_type> boundary_points;
+
+    Geometry const& geometry;
+};
+
+}} // namespace detail::relate
+#endif // DOXYGEN_NO_DETAIL
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP