/usr/include/boost/geometry/algorithms/detail/relate
Edit: /usr/include/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp (23242B)
// Boost.Geometry
// Copyright (c) 2017-2019 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace relate
{
template
<
typename Geometry,
typename EqPPStrategy,
typename Tag = typename tag::type
>
struct multi_point_geometry_eb
{
template
static inline bool apply(MultiPoint const& ,
detail::relate::topology_check const& )
{
return true;
}
};
template
struct multi_point_geometry_eb
{
template
struct boundary_visitor
{
boundary_visitor(Points const& points)
: m_points(points)
, m_boundary_found(false)
{}
template
struct find_pred
{
find_pred(Point const& point)
: m_point(point)
{}
template
bool operator()(Pt const& pt) const
{
return detail::equals::equals_point_point(pt, m_point, EqPPStrategy());
}
Point const& m_point;
};
template
bool apply(Point const& boundary_point)
{
if (std::find_if(m_points.begin(), m_points.end(), find_pred(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
static inline bool apply(MultiPoint const& multi_point,
detail::relate::topology_check const& tc)
{
boundary_visitor visitor(multi_point);
tc.for_each_boundary_point(visitor);
return visitor.result();
}
};
template
struct multi_point_geometry_eb
{
// TODO: CS-specific less compare strategy derived from EqPPStrategy
typedef geometry::less less_type;
template
struct boundary_visitor
{
boundary_visitor(Points const& points)
: m_points(points)
, m_boundary_found(false)
{}
template
bool apply(Point const& boundary_point)
{
if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, less_type()))
{
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
static inline bool apply(MultiPoint const& multi_point,
detail::relate::topology_check const& tc)
{
typedef typename boost::range_value::type point_type;
typedef std::vector points_type;
points_type points(boost::begin(multi_point), boost::end(multi_point));
std::sort(points.begin(), points.end(), less_type());
boundary_visitor visitor(points);
tc.for_each_boundary_point(visitor);
return visitor.result();
}
};
// SingleGeometry - Linear or Areal
template
struct multi_point_single_geometry
{
static const bool interruption_enabled = true;
template
static inline void apply(MultiPoint const& multi_point,
SingleGeometry const& single_geometry,
Result & result,
Strategy const& strategy)
{
typedef typename point_type::type point2_type;
typedef model::box box2_type;
typedef typename Strategy::equals_point_point_strategy_type eq_pp_strategy_type;
typedef typename Strategy::disjoint_point_box_strategy_type d_pb_strategy_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::type iterator;
for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
{
if (! (relate::may_update(result)
|| relate::may_update(result)
|| relate::may_update(result) ) )
{
break;
}
// The default strategy is enough for Point/Box
if (detail::disjoint::disjoint_point_box(*it, box2, d_pb_strategy_type()))
{
relate::set(result);
}
else
{
int in_val = detail::within::point_in_geometry(*it, single_geometry, strategy);
if (in_val > 0) // within
{
relate::set(result);
}
else if (in_val == 0)
{
relate::set(result);
}
else // in_val < 0 - not within
{
relate::set(result);
}
}
if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
{
return;
}
}
typedef detail::relate::topology_check
<
SingleGeometry, eq_pp_strategy_type
> tc_t;
if ( relate::may_update(result)
|| relate::may_update(result) )
{
tc_t tc(single_geometry);
if ( relate::may_update(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(result);
}
if ( relate::may_update(result)
&& tc.has_boundary() )
{
if (multi_point_geometry_eb
<
SingleGeometry, eq_pp_strategy_type
>::apply(multi_point, tc))
{
relate::set(result);
}
}
}
relate::set::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
class multi_point_multi_geometry_ii_ib
{
template
struct expand_box_point
{
template
static inline void apply(Box& total, Point const& point)
{
geometry::expand(total, point, ExpandPointStrategy());
}
};
template
struct expand_box_box_pair
{
template
static inline void apply(Box& total, BoxPair const& box_pair)
{
geometry::expand(total, box_pair.first, ExpandBoxStrategy());
}
};
template
struct overlaps_box_point
{
template
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,
DisjointPointBoxStrategy());
}
};
template
struct overlaps_box_box_pair
{
template
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,
DisjointBoxBoxStrategy());
}
};
template
class item_visitor_type
{
typedef typename PtSegStrategy::equals_point_point_strategy_type pp_strategy_type;
typedef typename PtSegStrategy::disjoint_point_box_strategy_type d_pp_strategy_type;
typedef detail::relate::topology_check topology_check_type;
public:
item_visitor_type(MultiGeometry const& multi_geometry,
topology_check_type const& tc,
Result & result,
PtSegStrategy const& strategy)
: m_multi_geometry(multi_geometry)
, m_tc(tc)
, m_result(result)
, m_strategy(strategy)
{}
template
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, d_pp_strategy_type()))
{
typename boost::range_value::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(m_result);
}
else if (in_val == 0)
{
if (m_tc.check_boundary_point(point))
relate::set(m_result);
else
relate::set(m_result);
}
}
if ( BOOST_GEOMETRY_CONDITION(m_result.interrupt) )
{
return false;
}
if (! (relate::may_update(m_result)
|| relate::may_update(m_result) ) )
{
return false;
}
return true;
}
private:
MultiGeometry const& m_multi_geometry;
topology_check_type const& m_tc;
Result & m_result;
PtSegStrategy const& m_strategy;
};
public:
typedef typename point_type::type point1_type;
typedef typename point_type::type point2_type;
typedef model::box box1_type;
typedef model::box box2_type;
typedef std::pair box_pair_type;
template
static inline void apply(MultiPoint const& multi_point,
MultiGeometry const& multi_geometry,
std::vector const& boxes,
detail::relate::topology_check
<
MultiGeometry,
typename Strategy::equals_point_point_strategy_type
> const& tc,
Result & result,
Strategy const& strategy)
{
item_visitor_type visitor(multi_geometry, tc, result, strategy);
typedef expand_box_point
<
typename Strategy::expand_point_strategy_type
> expand_box_point_type;
typedef overlaps_box_point
<
typename Strategy::disjoint_point_box_strategy_type
> overlaps_box_point_type;
typedef expand_box_box_pair
<
typename Strategy::envelope_strategy_type::box_expand_strategy_type
> expand_box_box_pair_type;
typedef overlaps_box_box_pair
<
typename Strategy::disjoint_box_box_strategy_type
> overlaps_box_box_pair_type;
geometry::partition
<
box1_type
>::apply(multi_point, boxes, visitor,
expand_box_point_type(),
overlaps_box_point_type(),
expand_box_box_pair_type(),
overlaps_box_box_pair_type());
}
};
// MultiGeometry - Linear or Areal
// part of the algorithm calculating II, IB and IE
// using rtree
template
struct multi_point_multi_geometry_ii_ib_ie
{
typedef typename point_type::type point1_type;
typedef typename point_type::type point2_type;
typedef model::box box1_type;
typedef model::box box2_type;
typedef std::pair box_pair_type;
typedef std::vector boxes_type;
typedef typename boxes_type::const_iterator boxes_iterator;
template
static inline void apply(MultiPoint const& multi_point,
MultiGeometry const& multi_geometry,
std::vector const& boxes,
detail::relate::topology_check
<
MultiGeometry,
typename Strategy::equals_point_point_strategy_type
> const& tc,
Result & result,
Strategy const& strategy)
{
typedef strategy::index::services::from_strategy
<
Strategy
> index_strategy_from;
typedef index::parameters
<
index::rstar<4>, typename index_strategy_from::type
> index_parameters_type;
index::rtree
rtree(boxes.begin(), boxes.end(),
index_parameters_type(index::rstar<4>(), index_strategy_from::get(strategy)));
typedef typename boost::range_const_iterator::type iterator;
for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
{
if (! (relate::may_update(result)
|| relate::may_update(result)
|| relate::may_update(result) ) )
{
return;
}
typename boost::range_value::type const& point = *it;
boxes_type boxes_found;
rtree.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::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(result);
found_ii_or_ib = true;
}
else if (in_val == 0) // on boundary of single
{
if (tc.check_boundary_point(point))
relate::set(result);
else
relate::set(result);
found_ii_or_ib = true;
}
}
// neither interior nor boundary found -> exterior
if (found_ii_or_ib == false)
{
relate::set(result);
}
if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
{
return;
}
}
}
};
// MultiGeometry - Linear or Areal
template
struct multi_point_multi_geometry
{
static const bool interruption_enabled = true;
template
static inline void apply(MultiPoint const& multi_point,
MultiGeometry const& multi_geometry,
Result & result,
Strategy const& strategy)
{
typedef typename point_type::type point2_type;
typedef model::box box2_type;
typedef std::pair box_pair_type;
typedef typename Strategy::equals_point_point_strategy_type eq_pp_strategy_type;
typename Strategy::envelope_strategy_type const
envelope_strategy = strategy.get_envelope_strategy();
std::size_t count2 = boost::size(multi_geometry);
std::vector 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 tc_t;
tc_t tc(multi_geometry);
if ( relate::may_update(result)
|| relate::may_update(result)
|| relate::may_update(result) )
{
// If there is no need to calculate IE, use partition
if (! relate::may_update(result) )
{
multi_point_multi_geometry_ii_ib
::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
}
else // otherwise use rtree
{
multi_point_multi_geometry_ii_ib_ie
::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
}
}
if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
{
return;
}
if ( relate::may_update(result)
|| relate::may_update(result) )
{
if ( relate::may_update(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(result);
}
if ( relate::may_update(result)
&& tc.has_boundary() )
{
if (multi_point_geometry_eb
<
MultiGeometry, eq_pp_strategy_type
>::apply(multi_point, tc))
{
relate::set(result);
}
}
}
relate::set::value, Transpose>(result);
}
};
template
<
typename MultiPoint, typename Geometry,
bool Transpose = false,
bool isMulti = boost::is_same
<
typename tag_cast
<
typename tag::type, multi_tag
>::type,
multi_tag
>::value
>
struct multi_point_geometry
: multi_point_single_geometry
{};
template
struct multi_point_geometry
: multi_point_multi_geometry
{};
// transposed result of multi_point_geometry
template
struct geometry_multi_point
{
static const bool interruption_enabled = true;
template
static inline void apply(Geometry const& geometry, MultiPoint const& multi_point,
Result & result, Strategy const& strategy)
{
multi_point_geometry::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