summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/relate
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/relate')
-rw-r--r--boost/geometry/algorithms/detail/relate/implementation.hpp11
-rw-r--r--boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp568
-rw-r--r--boost/geometry/algorithms/detail/relate/point_geometry.hpp38
-rw-r--r--boost/geometry/algorithms/detail/relate/point_point.hpp54
-rw-r--r--boost/geometry/algorithms/detail/relate/topology_check.hpp244
5 files changed, 791 insertions, 124 deletions
diff --git a/boost/geometry/algorithms/detail/relate/implementation.hpp b/boost/geometry/algorithms/detail/relate/implementation.hpp
index 3bd0f806c1..8f7942d46e 100644
--- a/boost/geometry/algorithms/detail/relate/implementation.hpp
+++ b/boost/geometry/algorithms/detail/relate/implementation.hpp
@@ -23,6 +23,7 @@
#include <boost/geometry/algorithms/detail/relate/point_geometry.hpp>
#include <boost/geometry/algorithms/detail/relate/linear_linear.hpp>
#include <boost/geometry/algorithms/detail/relate/linear_areal.hpp>
+#include <boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp>
#include <boost/geometry/algorithms/detail/relate/areal_areal.hpp>
#include <boost/geometry/strategies/intersection.hpp>
@@ -81,6 +82,16 @@ struct relate<Geometry, Point, Tag1, point_tag, TopDim1, 0, true>
: detail::relate::geometry_point<Geometry, Point>
{};
+template <typename MultiPoint, typename Geometry, typename Tag2, int TopDim2>
+struct relate<MultiPoint, Geometry, multi_point_tag, Tag2, 0, TopDim2, false>
+ : detail::relate::multi_point_geometry<MultiPoint, Geometry>
+{};
+
+template <typename Geometry, typename MultiPoint, typename Tag1, int TopDim1>
+struct relate<Geometry, MultiPoint, Tag1, multi_point_tag, TopDim1, 0, false>
+ : detail::relate::geometry_multi_point<Geometry, MultiPoint>
+{};
+
template <typename Linear1, typename Linear2, typename Tag1, typename Tag2>
struct relate<Linear1, Linear2, Tag1, Tag2, 1, 1, true>
diff --git a/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp b/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp
new file mode 100644
index 0000000000..47c6963b87
--- /dev/null
+++ b/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp
@@ -0,0 +1,568 @@
+// Boost.Geometry
+
+// Copyright (c) 2017 Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
+
+// 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)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP
+
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
+#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
+#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
+#include <boost/geometry/algorithms/detail/relate/result.hpp>
+#include <boost/geometry/algorithms/detail/relate/topology_check.hpp>
+#include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
+#include <boost/geometry/algorithms/envelope.hpp>
+
+#include <boost/geometry/core/is_areal.hpp>
+#include <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/geometries/box.hpp>
+
+#include <boost/geometry/index/rtree.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace relate
+{
+
+template
+<
+ typename Geometry,
+ typename Tag = typename tag<Geometry>::type
+>
+struct multi_point_geometry_eb
+{
+ template <typename MultiPoint>
+ static inline bool apply(MultiPoint const& ,
+ detail::relate::topology_check<Geometry> const& )
+ {
+ return true;
+ }
+};
+
+template <typename Geometry>
+struct multi_point_geometry_eb<Geometry, linestring_tag>
+{
+ template <typename Points>
+ struct boundary_visitor
+ {
+ boundary_visitor(Points const& points)
+ : m_points(points)
+ , m_boundary_found(false)
+ {}
+
+ template <typename Point>
+ struct find_pred
+ {
+ find_pred(Point const& point)
+ : m_point(point)
+ {}
+
+ template <typename Pt>
+ bool operator()(Pt const& pt) const
+ {
+ return detail::equals::equals_point_point(pt, m_point);
+ }
+
+ Point const& m_point;
+ };
+
+ template <typename Point>
+ bool apply(Point const& boundary_point)
+ {
+ if (std::find_if(m_points.begin(), m_points.end(), find_pred<Point>(boundary_point)) == m_points.end())
+ {
+ m_boundary_found = true;
+ return false;
+ }
+ return true;
+ }
+
+ bool result() const { return m_boundary_found; }
+
+ private:
+ Points const& m_points;
+ bool m_boundary_found;
+ };
+
+ template <typename MultiPoint>
+ static inline bool apply(MultiPoint const& multi_point,
+ detail::relate::topology_check<Geometry> const& tc)
+ {
+ boundary_visitor<MultiPoint> visitor(multi_point);
+ tc.for_each_boundary_point(visitor);
+ return visitor.result();
+ }
+};
+
+template <typename Geometry>
+struct multi_point_geometry_eb<Geometry, multi_linestring_tag>
+{
+ template <typename Points>
+ struct boundary_visitor
+ {
+ boundary_visitor(Points const& points)
+ : m_points(points)
+ , m_boundary_found(false)
+ {}
+
+ template <typename Point>
+ bool apply(Point const& boundary_point)
+ {
+ if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, relate::less()))
+ {
+ m_boundary_found = true;
+ return false;
+ }
+ return true;
+ }
+
+ bool result() const { return m_boundary_found; }
+
+ private:
+ Points const& m_points;
+ bool m_boundary_found;
+ };
+
+ template <typename MultiPoint>
+ static inline bool apply(MultiPoint const& multi_point,
+ detail::relate::topology_check<Geometry> const& tc)
+ {
+ typedef typename boost::range_value<MultiPoint>::type point_type;
+ typedef std::vector<point_type> points_type;
+ points_type points(boost::begin(multi_point), boost::end(multi_point));
+ std::sort(points.begin(), points.end(), relate::less());
+
+ boundary_visitor<points_type> visitor(points);
+ tc.for_each_boundary_point(visitor);
+ return visitor.result();
+ }
+};
+
+// SingleGeometry - Linear or Areal
+template <typename MultiPoint, typename SingleGeometry, bool Transpose = false>
+struct multi_point_single_geometry
+{
+ static const bool interruption_enabled = true;
+
+ template <typename Result, typename Strategy>
+ static inline void apply(MultiPoint const& multi_point,
+ SingleGeometry const& single_geometry,
+ Result & result,
+ Strategy const& strategy)
+ {
+ typedef typename point_type<SingleGeometry>::type point2_type;
+ typedef model::box<point2_type> box2_type;
+
+ box2_type box2;
+ geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy());
+ geometry::detail::expand_by_epsilon(box2);
+
+ typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
+ for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
+ {
+ if (! (relate::may_update<interior, interior, '0', Transpose>(result)
+ || relate::may_update<interior, boundary, '0', Transpose>(result)
+ || relate::may_update<interior, exterior, '0', Transpose>(result) ) )
+ {
+ break;
+ }
+
+ // The default strategy is enough for Point/Box
+ if (detail::disjoint::disjoint_point_box(*it, box2))
+ {
+ relate::set<interior, exterior, '0', Transpose>(result);
+ }
+ else
+ {
+ int in_val = detail::within::point_in_geometry(*it, single_geometry, strategy);
+
+ if (in_val > 0) // within
+ {
+ relate::set<interior, interior, '0', Transpose>(result);
+ }
+ else if (in_val == 0)
+ {
+ relate::set<interior, boundary, '0', Transpose>(result);
+ }
+ else // in_val < 0 - not within
+ {
+ relate::set<interior, exterior, '0', Transpose>(result);
+ }
+ }
+
+ if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
+ {
+ return;
+ }
+ }
+
+ typedef detail::relate::topology_check<SingleGeometry> tc_t;
+ if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
+ || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
+ {
+ tc_t tc(single_geometry);
+
+ if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
+ && tc.has_interior() )
+ {
+ // TODO: this is not true if a linestring is degenerated to a point
+ // then the interior has topological dimension = 0, not 1
+ relate::set<exterior, interior, tc_t::interior, Transpose>(result);
+ }
+
+ if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result)
+ && tc.has_boundary() )
+ {
+ if (multi_point_geometry_eb<SingleGeometry>::apply(multi_point, tc))
+ relate::set<exterior, boundary, tc_t::boundary, Transpose>(result);
+ }
+ }
+
+ relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result);
+ }
+};
+
+
+// MultiGeometry - Linear or Areal
+// part of the algorithm calculating II and IB when no IE has to be calculated
+// using partition()
+template <typename MultiPoint, typename MultiGeometry, bool Transpose>
+class multi_point_multi_geometry_ii_ib
+{
+ struct expand_box_point
+ {
+ template <typename Box, typename Point>
+ static inline void apply(Box& total, Point const& point)
+ {
+ geometry::expand(total, point);
+ }
+ };
+
+ struct expand_box_box_pair
+ {
+ template <typename Box, typename BoxPair>
+ static inline void apply(Box& total, BoxPair const& box_pair)
+ {
+ geometry::expand(total, box_pair.first);
+ }
+ };
+
+ struct overlaps_box_point
+ {
+ template <typename Box, typename Point>
+ static inline bool apply(Box const& box, Point const& point)
+ {
+ // The default strategy is enough for Point/Box
+ return ! detail::disjoint::disjoint_point_box(point, box);
+ }
+ };
+
+ struct overlaps_box_box_pair
+ {
+ template <typename Box, typename BoxPair>
+ static inline bool apply(Box const& box, BoxPair const& box_pair)
+ {
+ // The default strategy is enough for Box/Box
+ return ! detail::disjoint::disjoint_box_box(box_pair.first, box);
+ }
+ };
+
+ template <typename Result, typename PtSegStrategy>
+ class item_visitor_type
+ {
+ public:
+ item_visitor_type(MultiGeometry const& multi_geometry,
+ detail::relate::topology_check<MultiGeometry> const& tc,
+ Result & result,
+ PtSegStrategy const& strategy)
+ : m_multi_geometry(multi_geometry)
+ , m_tc(tc)
+ , m_result(result)
+ , m_strategy(strategy)
+ {}
+
+ template <typename Point, typename BoxPair>
+ inline bool apply(Point const& point, BoxPair const& box_pair)
+ {
+ // The default strategy is enough for Point/Box
+ if (! detail::disjoint::disjoint_point_box(point, box_pair.first))
+ {
+ typename boost::range_value<MultiGeometry>::type const&
+ single = range::at(m_multi_geometry, box_pair.second);
+
+ int in_val = detail::within::point_in_geometry(point, single, m_strategy);
+
+ if (in_val > 0) // within
+ {
+ relate::set<interior, interior, '0', Transpose>(m_result);
+ }
+ else if (in_val == 0)
+ {
+ if (m_tc.check_boundary_point(point))
+ relate::set<interior, boundary, '0', Transpose>(m_result);
+ else
+ relate::set<interior, interior, '0', Transpose>(m_result);
+ }
+ }
+
+ if ( BOOST_GEOMETRY_CONDITION(m_result.interrupt) )
+ {
+ return false;
+ }
+
+ if (! (relate::may_update<interior, interior, '0', Transpose>(m_result)
+ || relate::may_update<interior, boundary, '0', Transpose>(m_result) ) )
+ {
+ return false;
+ }
+
+ return true;
+ }
+
+
+ private:
+ MultiGeometry const& m_multi_geometry;
+ detail::relate::topology_check<MultiGeometry> const& m_tc;
+ Result & m_result;
+ PtSegStrategy const& m_strategy;
+ };
+
+public:
+ typedef typename point_type<MultiPoint>::type point1_type;
+ typedef typename point_type<MultiGeometry>::type point2_type;
+ typedef model::box<point1_type> box1_type;
+ typedef model::box<point2_type> box2_type;
+ typedef std::pair<box2_type, std::size_t> box_pair_type;
+
+ template <typename Result, typename Strategy>
+ static inline void apply(MultiPoint const& multi_point,
+ MultiGeometry const& multi_geometry,
+ std::vector<box_pair_type> const& boxes,
+ detail::relate::topology_check<MultiGeometry> const& tc,
+ Result & result,
+ Strategy const& strategy)
+ {
+ item_visitor_type<Result, Strategy> visitor(multi_geometry, tc, result, strategy);
+
+ geometry::partition
+ <
+ box1_type
+ >::apply(multi_point, boxes, visitor,
+ expand_box_point(),
+ overlaps_box_point(),
+ expand_box_box_pair(),
+ overlaps_box_box_pair());
+ }
+
+};
+
+// MultiGeometry - Linear or Areal
+// part of the algorithm calculating II, IB and IE
+// using rtree
+template <typename MultiPoint, typename MultiGeometry, bool Transpose>
+struct multi_point_multi_geometry_ii_ib_ie
+{
+ typedef typename point_type<MultiPoint>::type point1_type;
+ typedef typename point_type<MultiGeometry>::type point2_type;
+ typedef model::box<point1_type> box1_type;
+ typedef model::box<point2_type> box2_type;
+ typedef std::pair<box2_type, std::size_t> box_pair_type;
+ typedef std::vector<box_pair_type> boxes_type;
+ typedef typename boxes_type::const_iterator boxes_iterator;
+
+ template <typename Result, typename Strategy>
+ static inline void apply(MultiPoint const& multi_point,
+ MultiGeometry const& multi_geometry,
+ std::vector<box_pair_type> const& boxes,
+ detail::relate::topology_check<MultiGeometry> const& tc,
+ Result & result,
+ Strategy const& strategy)
+ {
+ index::rtree<box_pair_type, index::rstar<4> > rt(boxes.begin(), boxes.end());
+
+ typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
+ for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
+ {
+ if (! (relate::may_update<interior, interior, '0', Transpose>(result)
+ || relate::may_update<interior, boundary, '0', Transpose>(result)
+ || relate::may_update<interior, exterior, '0', Transpose>(result) ) )
+ {
+ return;
+ }
+
+ typename boost::range_value<MultiPoint>::type const& point = *it;
+
+ boxes_type boxes_found;
+ rt.query(index::intersects(point), std::back_inserter(boxes_found));
+
+ bool found_ii_or_ib = false;
+ for (boxes_iterator bi = boxes_found.begin() ; bi != boxes_found.end() ; ++bi)
+ {
+ typename boost::range_value<MultiGeometry>::type const&
+ single = range::at(multi_geometry, bi->second);
+
+ int in_val = detail::within::point_in_geometry(point, single, strategy);
+
+ if (in_val > 0) // within
+ {
+ relate::set<interior, interior, '0', Transpose>(result);
+ found_ii_or_ib = true;
+ }
+ else if (in_val == 0) // on boundary of single
+ {
+ if (tc.check_boundary_point(point))
+ relate::set<interior, boundary, '0', Transpose>(result);
+ else
+ relate::set<interior, interior, '0', Transpose>(result);
+ found_ii_or_ib = true;
+ }
+ }
+
+ // neither interior nor boundary found -> exterior
+ if (found_ii_or_ib == false)
+ {
+ relate::set<interior, exterior, '0', Transpose>(result);
+ }
+
+ if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
+ {
+ return;
+ }
+ }
+ }
+};
+
+// MultiGeometry - Linear or Areal
+template <typename MultiPoint, typename MultiGeometry, bool Transpose = false>
+struct multi_point_multi_geometry
+{
+ static const bool interruption_enabled = true;
+
+ template <typename Result, typename Strategy>
+ static inline void apply(MultiPoint const& multi_point,
+ MultiGeometry const& multi_geometry,
+ Result & result,
+ Strategy const& strategy)
+ {
+ typedef typename point_type<MultiGeometry>::type point2_type;
+ typedef model::box<point2_type> box2_type;
+ typedef std::pair<box2_type, std::size_t> box_pair_type;
+
+ typename Strategy::envelope_strategy_type const
+ envelope_strategy = strategy.get_envelope_strategy();
+
+ std::size_t count2 = boost::size(multi_geometry);
+ std::vector<box_pair_type> boxes(count2);
+ for (std::size_t i = 0 ; i < count2 ; ++i)
+ {
+ geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy);
+ geometry::detail::expand_by_epsilon(boxes[i].first);
+ boxes[i].second = i;
+ }
+
+ typedef detail::relate::topology_check<MultiGeometry> tc_t;
+ tc_t tc(multi_geometry);
+
+ if ( relate::may_update<interior, interior, '0', Transpose>(result)
+ || relate::may_update<interior, boundary, '0', Transpose>(result)
+ || relate::may_update<interior, exterior, '0', Transpose>(result) )
+ {
+ // If there is no need to calculate IE, use partition
+ if (! relate::may_update<interior, exterior, '0', Transpose>(result) )
+ {
+ multi_point_multi_geometry_ii_ib<MultiPoint, MultiGeometry, Transpose>
+ ::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
+ }
+ else // otherwise use rtree
+ {
+ multi_point_multi_geometry_ii_ib_ie<MultiPoint, MultiGeometry, Transpose>
+ ::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
+ }
+ }
+
+ if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
+ {
+ return;
+ }
+
+ if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
+ || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
+ {
+ if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
+ && tc.has_interior() )
+ {
+ // TODO: this is not true if a linestring is degenerated to a point
+ // then the interior has topological dimension = 0, not 1
+ relate::set<exterior, interior, tc_t::interior, Transpose>(result);
+ }
+
+ if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result)
+ && tc.has_boundary() )
+ {
+ if (multi_point_geometry_eb<MultiGeometry>::apply(multi_point, tc))
+ relate::set<exterior, boundary, tc_t::boundary, Transpose>(result);
+ }
+ }
+
+ relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result);
+ }
+
+};
+
+
+template
+<
+ typename MultiPoint, typename Geometry,
+ bool Transpose = false,
+ bool isMulti = boost::is_same
+ <
+ typename tag_cast
+ <
+ typename tag<Geometry>::type, multi_tag
+ >::type,
+ multi_tag
+ >::value
+>
+struct multi_point_geometry
+ : multi_point_single_geometry<MultiPoint, Geometry, Transpose>
+{};
+
+template <typename MultiPoint, typename Geometry, bool Transpose>
+struct multi_point_geometry<MultiPoint, Geometry, Transpose, true>
+ : multi_point_multi_geometry<MultiPoint, Geometry, Transpose>
+{};
+
+
+// transposed result of multi_point_geometry
+template <typename Geometry, typename MultiPoint>
+struct geometry_multi_point
+{
+ static const bool interruption_enabled = true;
+
+ template <typename Result, typename Strategy>
+ static inline void apply(Geometry const& geometry, MultiPoint const& multi_point,
+ Result & result, Strategy const& strategy)
+ {
+ multi_point_geometry<MultiPoint, Geometry, true>::apply(multi_point, geometry, result, strategy);
+ }
+};
+
+}} // namespace detail::relate
+#endif // DOXYGEN_NO_DETAIL
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP
diff --git a/boost/geometry/algorithms/detail/relate/point_geometry.hpp b/boost/geometry/algorithms/detail/relate/point_geometry.hpp
index a0c6c0d49b..e78a404b21 100644
--- a/boost/geometry/algorithms/detail/relate/point_geometry.hpp
+++ b/boost/geometry/algorithms/detail/relate/point_geometry.hpp
@@ -60,29 +60,27 @@ struct point_geometry
if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
return;
- // the point is on the boundary
- if ( pig == 0 )
+ typedef detail::relate::topology_check<Geometry> tc_t;
+ if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
+ || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
{
- // NOTE: even for MLs, if there is at least one boundary point,
- // somewhere there must be another one
-
- // check if there are other boundaries outside
- typedef detail::relate::topology_check<Geometry> tc_t;
- //tc_t tc(geometry, point);
- //if ( tc.has_interior )
- relate::set<exterior, interior, tc_t::interior, Transpose>(result);
- //if ( tc.has_boundary )
- relate::set<exterior, boundary, tc_t::boundary, Transpose>(result);
- }
- else
- {
- // check if there is a boundary in Geometry
- typedef detail::relate::topology_check<Geometry> tc_t;
- tc_t tc(geometry);
- if ( tc.has_interior )
+ // the point is on the boundary
+ if ( pig == 0 )
+ {
+ // NOTE: even for MLs, if there is at least one boundary point,
+ // somewhere there must be another one
relate::set<exterior, interior, tc_t::interior, Transpose>(result);
- if ( tc.has_boundary )
relate::set<exterior, boundary, tc_t::boundary, Transpose>(result);
+ }
+ else
+ {
+ // check if there is a boundary in Geometry
+ tc_t tc(geometry);
+ if ( tc.has_interior() )
+ relate::set<exterior, interior, tc_t::interior, Transpose>(result);
+ if ( tc.has_boundary() )
+ relate::set<exterior, boundary, tc_t::boundary, Transpose>(result);
+ }
}
}
};
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;
}
};
diff --git a/boost/geometry/algorithms/detail/relate/topology_check.hpp b/boost/geometry/algorithms/detail/relate/topology_check.hpp
index caa8a3c22d..654999d8fb 100644
--- a/boost/geometry/algorithms/detail/relate/topology_check.hpp
+++ b/boost/geometry/algorithms/detail/relate/topology_check.hpp
@@ -1,22 +1,23 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
-// Copyright (c) 2014, Oracle and/or its affiliates.
+// Copyright (c) 2014-2017, Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// 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_TOPOLOGY_CHECK_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
-#include <boost/geometry/util/range.hpp>
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
-#include <boost/geometry/policies/compare.hpp>
+#include <boost/geometry/algorithms/detail/relate/less.hpp>
#include <boost/geometry/util/has_nan_coordinate.hpp>
+#include <boost/geometry/util/range.hpp>
+
namespace boost { namespace geometry {
@@ -51,31 +52,63 @@ struct topology_check<Linestring, linestring_tag>
static const char interior = '1';
static const char boundary = '0';
- bool has_interior;
- bool has_boundary;
-
topology_check(Linestring const& ls)
+ : m_ls(ls)
+ , m_is_initialized(false)
+ {}
+
+ bool has_interior() const
{
- init(ls, 0); /*dummy param*/
+ init();
+ return m_has_interior;
}
- template <typename IgnoreBoundaryPoint>
- topology_check(Linestring const& ls, IgnoreBoundaryPoint const& ibp)
+ bool has_boundary() const
{
- init(ls, ibp); /*dummy param, won't be used*/
+ init();
+ return m_has_boundary;
}
- // Even if some point is on the boundary, if the Linestring has the boundary,
- // there will be second boundary point different than IgnoreBoundaryPoint
- template <typename IgnoreBoundaryPoint>
- void init(Linestring const& ls, IgnoreBoundaryPoint const&)
+ /*template <typename Point>
+ bool check_boundary_point(Point const& point) const
{
- std::size_t count = boost::size(ls);
- has_interior = count > 0;
+ init();
+ return m_has_boundary
+ && ( equals::equals_point_point(point, range::front(m_ls))
+ || equals::equals_point_point(point, range::back(m_ls)) );
+ }*/
+
+ template <typename Visitor>
+ void for_each_boundary_point(Visitor & visitor) const
+ {
+ init();
+ if (m_has_boundary)
+ {
+ if (visitor.apply(range::front(m_ls)))
+ visitor.apply(range::back(m_ls));
+ }
+ }
+
+private:
+ void init() const
+ {
+ if (m_is_initialized)
+ return;
+
+ std::size_t count = boost::size(m_ls);
+ m_has_interior = count > 0;
// NOTE: Linestring with all points equal is treated as 1d linear ring
- has_boundary = count > 1
- && ! detail::equals::equals_point_point(range::front(ls), range::back(ls));
+ m_has_boundary = count > 1
+ && ! detail::equals::equals_point_point(range::front(m_ls), range::back(m_ls));
+
+ m_is_initialized = true;
}
+
+ Linestring const& m_ls;
+ mutable bool m_is_initialized;
+
+ mutable bool m_has_interior;
+ mutable bool m_has_boundary;
};
template <typename MultiLinestring>
@@ -84,29 +117,58 @@ struct topology_check<MultiLinestring, multi_linestring_tag>
static const char interior = '1';
static const char boundary = '0';
- bool has_interior;
- bool has_boundary;
-
topology_check(MultiLinestring const& mls)
+ : m_mls(mls)
+ , m_is_initialized(false)
+ {}
+
+ bool has_interior() const
{
- init(mls, not_ignoring_counter());
+ init();
+ return m_has_interior;
}
- template <typename IgnoreBoundaryPoint>
- topology_check(MultiLinestring const& mls, IgnoreBoundaryPoint const& ibp)
+ bool has_boundary() const
{
- init(mls, ignoring_counter<IgnoreBoundaryPoint>(ibp));
+ init();
+ return m_has_boundary;
}
- template <typename OddCounter>
- void init(MultiLinestring const& mls, OddCounter const& odd_counter)
+ template <typename Point>
+ bool check_boundary_point(Point const& point) const
{
- typedef typename geometry::point_type<MultiLinestring>::type point_type;
- std::vector<point_type> endpoints;
- endpoints.reserve(boost::size(mls) * 2);
+ init();
+
+ if (! m_has_boundary)
+ return false;
+
+ std::size_t count = count_equal(m_endpoints.begin(), m_endpoints.end(), point);
+
+ return count % 2 != 0; // odd count -> boundary
+ }
+
+ template <typename Visitor>
+ void for_each_boundary_point(Visitor & visitor) const
+ {
+ init();
+ if (m_has_boundary)
+ {
+ for_each_boundary_point(m_endpoints.begin(), m_endpoints.end(), visitor);
+ }
+ }
+
+private:
+ void init() const
+ {
+ if (m_is_initialized)
+ return;
+
+ m_endpoints.reserve(boost::size(m_mls) * 2);
+
+ m_has_interior = false;
typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator;
- for ( ls_iterator it = boost::begin(mls) ; it != boost::end(mls) ; ++it )
+ for ( ls_iterator it = boost::begin(m_mls) ; it != boost::end(m_mls) ; ++it )
{
typename boost::range_reference<MultiLinestring const>::type
ls = *it;
@@ -115,7 +177,7 @@ struct topology_check<MultiLinestring, multi_linestring_tag>
if (count > 0)
{
- has_interior = true;
+ m_has_interior = true;
}
if (count > 1)
@@ -138,62 +200,59 @@ struct topology_check<MultiLinestring, multi_linestring_tag>
// is not used anywhere in the code, still it's safer this way
if (! geometry::has_nan_coordinate(front_pt))
{
- endpoints.push_back(front_pt);
+ m_endpoints.push_back(front_pt);
}
if (! geometry::has_nan_coordinate(back_pt))
{
- endpoints.push_back(back_pt);
+ m_endpoints.push_back(back_pt);
}
}
}
}
- has_boundary = false;
+ m_has_boundary = false;
- if ( !endpoints.empty() )
+ if (! m_endpoints.empty() )
{
- std::sort(endpoints.begin(), endpoints.end(), geometry::less<point_type>());
- has_boundary = odd_counter(endpoints.begin(), endpoints.end());
+ std::sort(m_endpoints.begin(), m_endpoints.end(), relate::less());
+ m_has_boundary = find_odd_count(m_endpoints.begin(), m_endpoints.end());
}
+
+ m_is_initialized = true;
}
- struct not_ignoring_counter
+ template <typename It, typename Point>
+ static inline std::size_t count_equal(It first, It last, Point const& point)
{
- template <typename It>
- bool operator()(It first, It last) const
- {
- return find_odd_count(first, last);
- }
- };
+ std::pair<It, It> rng = std::equal_range(first, last, point, relate::less());
+ return (std::size_t)std::distance(rng.first, rng.second);
+ }
- template <typename Point>
- struct ignoring_counter
+ template <typename It>
+ static inline bool find_odd_count(It first, It last)
{
- ignoring_counter(Point const& pt) : m_pt(pt) {}
+ interrupting_visitor visitor;
+ for_each_boundary_point(first, last, visitor);
+ return visitor.found;
+ }
- template <typename It>
- bool operator()(It first, It last) const
+ struct interrupting_visitor
+ {
+ bool found;
+ interrupting_visitor() : found(false) {}
+ template <typename Point>
+ bool apply(Point const&)
{
- typedef typename std::iterator_traits<It>::value_type point_type;
-
- std::pair<It, It> ignore_range
- = std::equal_range(first, last, m_pt,
- geometry::less<point_type>());
-
- if ( find_odd_count(first, ignore_range.first) )
- return true;
-
- return find_odd_count(ignore_range.second, last);
+ found = true;
+ return false;
}
-
- Point const& m_pt;
};
- template <typename It>
- static inline bool find_odd_count(It first, It last)
+ template <typename It, typename Visitor>
+ static void for_each_boundary_point(It first, It last, Visitor& visitor)
{
if ( first == last )
- return false;
+ return;
std::size_t count = 1;
It prev = first;
@@ -203,8 +262,14 @@ struct topology_check<MultiLinestring, multi_linestring_tag>
// the end of the equal points subrange
if ( ! equals::equals_point_point(*first, *prev) )
{
+ // odd count -> boundary
if ( count % 2 != 0 )
- return true;
+ {
+ if (! visitor.apply(*prev))
+ {
+ return;
+ }
+ }
count = 1;
}
@@ -214,8 +279,22 @@ struct topology_check<MultiLinestring, multi_linestring_tag>
}
}
- return count % 2 != 0;
+ // odd count -> boundary
+ if ( count % 2 != 0 )
+ {
+ visitor.apply(*prev);
+ }
}
+
+private:
+ MultiLinestring const& m_mls;
+ mutable bool m_is_initialized;
+
+ mutable bool m_has_interior;
+ mutable bool m_has_boundary;
+
+ typedef typename geometry::point_type<MultiLinestring>::type point_type;
+ mutable std::vector<point_type> m_endpoints;
};
template <typename Ring>
@@ -223,12 +302,11 @@ struct topology_check<Ring, ring_tag>
{
static const char interior = '2';
static const char boundary = '1';
- static const bool has_interior = true;
- static const bool has_boundary = true;
topology_check(Ring const&) {}
- template <typename P>
- topology_check(Ring const&, P const&) {}
+
+ static bool has_interior() { return true; }
+ static bool has_boundary() { return true; }
};
template <typename Polygon>
@@ -236,12 +314,11 @@ struct topology_check<Polygon, polygon_tag>
{
static const char interior = '2';
static const char boundary = '1';
- static const bool has_interior = true;
- static const bool has_boundary = true;
-
+
topology_check(Polygon const&) {}
- template <typename P>
- topology_check(Polygon const&, P const&) {}
+
+ static bool has_interior() { return true; }
+ static bool has_boundary() { return true; }
};
template <typename MultiPolygon>
@@ -249,12 +326,13 @@ struct topology_check<MultiPolygon, multi_polygon_tag>
{
static const char interior = '2';
static const char boundary = '1';
- static const bool has_interior = true;
- static const bool has_boundary = true;
-
+
topology_check(MultiPolygon const&) {}
- template <typename P>
- topology_check(MultiPolygon const&, P const&) {}
+
+ static bool has_interior() { return true; }
+ static bool has_boundary() { return true; }
+ template <typename Point>
+ static bool check_boundary_point(Point const& ) { return true; }
};
}} // namespace detail::relate