/usr/include/boost/geometry/algorithms/detail/disjoint
Edit: /usr/include/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp (18575B)
// Boost.Geometry (aka GGL, Generic Geometry Library)
// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
// Copyright (c) 2014-2019, Oracle and/or its affiliates.
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
// Contributed and/or modified by Adam Wulkiewicz, 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_DISJOINT_MULTIPOINT_GEOMETRY_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace disjoint
{
class multipoint_multipoint
{
private:
template
class unary_disjoint_predicate
: geometry::less
{
private:
typedef geometry::less base_type;
public:
unary_disjoint_predicate(Iterator first, Iterator last)
: base_type(), m_first(first), m_last(last)
{}
template
inline bool apply(Point const& point) const
{
return !std::binary_search(m_first,
m_last,
point,
static_cast(*this));
}
private:
Iterator m_first, m_last;
};
public:
template
static inline bool apply(MultiPoint1 const& multipoint1,
MultiPoint2 const& multipoint2,
Strategy const&)
{
typedef typename Strategy::cs_tag cs_tag;
typedef geometry::less less_type;
BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) );
typedef typename boost::range_value::type point1_type;
std::vector points1(boost::begin(multipoint1),
boost::end(multipoint1));
std::sort(points1.begin(), points1.end(), less_type());
typedef unary_disjoint_predicate
<
typename std::vector::const_iterator,
cs_tag
> predicate_type;
return check_iterator_range
<
predicate_type
>::apply(boost::begin(multipoint2),
boost::end(multipoint2),
predicate_type(points1.begin(), points1.end()));
}
};
template
class multipoint_linear
{
private:
template
struct expand_box_point
{
template
static inline void apply(Box& total, Point const& point)
{
geometry::expand(total, point, ExpandPointBoxStrategy());
}
};
template
struct expand_box_segment
{
explicit expand_box_segment(EnvelopeStrategy const& strategy)
: m_strategy(strategy)
{}
template
inline void apply(Box& total, Segment const& segment) const
{
geometry::expand(total,
geometry::return_envelope(segment, m_strategy),
typename EnvelopeStrategy::box_expand_strategy_type());
}
EnvelopeStrategy const& m_strategy;
};
template
struct overlaps_box_point
{
template
static inline bool apply(Box const& box, Point const& point)
{
// The default strategy is enough in this case
return ! detail::disjoint::disjoint_point_box(point, box,
DisjointPointBoxStrategy());
}
};
template
struct overlaps_box_segment
{
explicit overlaps_box_segment(DisjointStrategy const& strategy)
: m_strategy(strategy)
{}
template
inline bool apply(Box const& box, Segment const& segment) const
{
return ! dispatch::disjoint::apply(segment, box, m_strategy);
}
DisjointStrategy const& m_strategy;
};
template
class item_visitor_type
{
public:
item_visitor_type(PtSegStrategy const& strategy)
: m_intersection_found(false)
, m_strategy(strategy)
{}
template
inline bool apply(Item1 const& item1, Item2 const& item2)
{
if (! m_intersection_found
&& ! dispatch::disjoint::apply(item1, item2, m_strategy))
{
m_intersection_found = true;
return false;
}
return true;
}
inline bool intersection_found() const { return m_intersection_found; }
private:
bool m_intersection_found;
PtSegStrategy const& m_strategy;
};
// structs for partition -- end
class segment_range
{
public:
typedef geometry::segment_iterator const_iterator;
typedef const_iterator iterator;
segment_range(Linear const& linear)
: m_linear(linear)
{}
const_iterator begin() const
{
return geometry::segments_begin(m_linear);
}
const_iterator end() const
{
return geometry::segments_end(m_linear);
}
private:
Linear const& m_linear;
};
public:
template
static inline bool apply(MultiPoint const& multipoint, Linear const& linear, Strategy const& strategy)
{
item_visitor_type visitor(strategy);
typedef typename Strategy::expand_point_strategy_type expand_point_strategy_type;
typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type;
typedef typename Strategy::disjoint_point_box_strategy_type disjoint_pb_strategy_type;
// TODO: disjoint Segment/Box may be called in partition multiple times
// possibly for non-cartesian segments which could be slow. We should consider
// passing a range of bounding boxes of segments after calculating them once.
// Alternatively instead of a range of segments a range of Segment/Envelope pairs
// should be passed, where envelope would be lazily calculated when needed the first time
geometry::partition
<
geometry::model::box::type>
>::apply(multipoint, segment_range(linear), visitor,
expand_box_point(),
overlaps_box_point(),
expand_box_segment(strategy.get_envelope_strategy()),
overlaps_box_segment(strategy.get_disjoint_strategy()));
return ! visitor.intersection_found();
}
template
static inline bool apply(Linear const& linear, MultiPoint const& multipoint, Strategy const& strategy)
{
return apply(multipoint, linear, strategy);
}
};
template
class multi_point_single_geometry
{
public:
template
static inline bool apply(MultiPoint const& multi_point,
SingleGeometry const& single_geometry,
Strategy const& strategy)
{
typedef typename Strategy::disjoint_point_box_strategy_type d_pb_strategy_type;
typedef typename point_type::type point1_type;
typedef typename point_type::type point2_type;
typedef model::box 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::type iterator;
for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
{
// The default strategy is enough for Point/Box
if (! detail::disjoint::disjoint_point_box(*it, box2, d_pb_strategy_type())
&& ! dispatch::disjoint::apply(*it, single_geometry, strategy))
{
return false;
}
}
return true;
}
template
static inline bool apply(SingleGeometry const& single_geometry, MultiPoint const& multi_point, Strategy const& strategy)
{
return apply(multi_point, single_geometry, strategy);
}
};
template
class multi_point_multi_geometry
{
private:
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
inline void apply(Box& total, BoxPair const& box_pair) const
{
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
inline bool apply(Box const& box, BoxPair const& box_pair) const
{
// The default strategy is enough for Box/Box
return ! detail::disjoint::disjoint_box_box(box_pair.first, box,
DisjointBoxBoxStrategy());
}
};
template
class item_visitor_type
{
public:
item_visitor_type(MultiGeometry const& multi_geometry,
PtSegStrategy const& strategy)
: m_intersection_found(false)
, m_multi_geometry(multi_geometry)
, m_strategy(strategy)
{}
template
inline bool apply(Point const& point, BoxPair const& box_pair)
{
typedef typename PtSegStrategy::disjoint_point_box_strategy_type d_pb_strategy_type;
typedef typename boost::range_value::type single_type;
// The default strategy is enough for Point/Box
if (! m_intersection_found
&& ! detail::disjoint::disjoint_point_box(point, box_pair.first, d_pb_strategy_type())
&& ! dispatch::disjoint::apply(point, range::at(m_multi_geometry, box_pair.second), m_strategy))
{
m_intersection_found = true;
return false;
}
return true;
}
inline bool intersection_found() const { return m_intersection_found; }
private:
bool m_intersection_found;
MultiGeometry const& m_multi_geometry;
PtSegStrategy const& m_strategy;
};
// structs for partition -- end
public:
template
static inline bool apply(MultiPoint const& multi_point, MultiGeometry const& multi_geometry, Strategy const& strategy)
{
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;
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;
}
item_visitor_type visitor(multi_geometry, 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());
return ! visitor.intersection_found();
}
template
static inline bool apply(MultiGeometry const& multi_geometry, MultiPoint const& multi_point, Strategy const& strategy)
{
return apply(multi_point, multi_geometry, strategy);
}
};
template ::type>
struct multipoint_areal
: multi_point_single_geometry
{};
template
struct multipoint_areal
: multi_point_multi_geometry
{};
}} // namespace detail::disjoint
#endif // DOXYGEN_NO_DETAIL
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
template
struct disjoint
<
Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false
> : detail::disjoint::multirange_constant_size_geometry
{};
template
struct disjoint
<
MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false
> : detail::disjoint::multirange_constant_size_geometry
{};
template
struct disjoint
<
MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false
> : detail::disjoint::multirange_constant_size_geometry
{};
template
<
typename MultiPoint1,
typename MultiPoint2,
std::size_t DimensionCount
>
struct disjoint
<
MultiPoint1, MultiPoint2, DimensionCount,
multi_point_tag, multi_point_tag, false
>
{
template
static inline bool apply(MultiPoint1 const& multipoint1,
MultiPoint2 const& multipoint2,
Strategy const& strategy)
{
if ( boost::size(multipoint2) < boost::size(multipoint1) )
{
return detail::disjoint::multipoint_multipoint
::apply(multipoint2, multipoint1, strategy);
}
return detail::disjoint::multipoint_multipoint
::apply(multipoint1, multipoint2, strategy);
}
};
template
struct disjoint
<
Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false
> : detail::disjoint::multipoint_linear
{};
template
struct disjoint
<
MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false
> : detail::disjoint::multipoint_linear
{};
template
struct disjoint
<
Areal, MultiPoint, DimensionCount, areal_tag, multi_point_tag, false
> : detail::disjoint::multipoint_areal
{};
template
struct disjoint
<
MultiPoint, Areal, DimensionCount, multi_point_tag, areal_tag, false
> : detail::disjoint::multipoint_areal
{};
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP