[ceph.git] / ceph / src / boost / boost / geometry / algorithms / detail / disjoint / multipoint_geometry.hpp

// 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 <algorithm>
#include <vector>

#include <boost/range.hpp>
#include <boost/mpl/assert.hpp>

#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/core/tag.hpp>
#include <boost/geometry/core/tags.hpp>

#include <boost/geometry/geometries/box.hpp>

#include <boost/geometry/iterators/segment_iterator.hpp>

#include <boost/geometry/algorithms/envelope.hpp>
#include <boost/geometry/algorithms/expand.hpp>

#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
#include <boost/geometry/algorithms/detail/partition.hpp>
#include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
#include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp>
#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
#include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
#include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>

#include <boost/geometry/algorithms/dispatch/disjoint.hpp>

#include <boost/geometry/policies/compare.hpp>


namespace boost { namespace geometry
{


#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace disjoint
{


class multipoint_multipoint
{
private:
    template <typename Iterator, typename CSTag>
    class unary_disjoint_predicate
        : geometry::less<void, -1, CSTag>
    {
    private:
        typedef geometry::less<void, -1, CSTag> base_type;

    public:
        unary_disjoint_predicate(Iterator first, Iterator last)
            : base_type(), m_first(first), m_last(last)
        {}

        template <typename Point>
        inline bool apply(Point const& point) const
        {
            return !std::binary_search(m_first,
                                       m_last,
                                       point,
                                       static_cast<base_type const&>(*this));
        }

    private:
        Iterator m_first, m_last;
    };

public:
    template <typename MultiPoint1, typename MultiPoint2, typename Strategy>
    static inline bool apply(MultiPoint1 const& multipoint1,
                             MultiPoint2 const& multipoint2,
                             Strategy const&)
    {
        typedef typename Strategy::cs_tag cs_tag;
        typedef geometry::less<void, -1, cs_tag> less_type;

        BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) );

        typedef typename boost::range_value<MultiPoint1>::type point1_type;

        std::vector<point1_type> points1(boost::begin(multipoint1),
                                         boost::end(multipoint1));

        std::sort(points1.begin(), points1.end(), less_type());

        typedef unary_disjoint_predicate
            <
                typename std::vector<point1_type>::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 <typename MultiPoint, typename Linear>
class multipoint_linear
{
private:
    template <typename ExpandPointBoxStrategy>
    struct expand_box_point
    {
        template <typename Box, typename Point>
        static inline void apply(Box& total, Point const& point)
        {
            geometry::expand(total, point, ExpandPointBoxStrategy());
        }
    };

    template <typename EnvelopeStrategy>
    struct expand_box_segment
    {
        explicit expand_box_segment(EnvelopeStrategy const& strategy)
            : m_strategy(strategy)
        {}

        template <typename Box, typename Segment>
        inline void apply(Box& total, Segment const& segment) const
        {
            geometry::expand(total,
                             geometry::return_envelope<Box>(segment, m_strategy),
                             typename EnvelopeStrategy::box_expand_strategy_type());
        }

        EnvelopeStrategy const& m_strategy;
    };

    template <typename DisjointPointBoxStrategy>
    struct overlaps_box_point
    {
        template <typename Box, typename Point>
        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 <typename DisjointStrategy>
    struct overlaps_box_segment
    {
        explicit overlaps_box_segment(DisjointStrategy const& strategy)
            : m_strategy(strategy)
        {}

        template <typename Box, typename Segment>
        inline bool apply(Box const& box, Segment const& segment) const
        {
            return ! dispatch::disjoint<Segment, Box>::apply(segment, box, m_strategy);
        }

        DisjointStrategy const& m_strategy;
    };

    template <typename PtSegStrategy>
    class item_visitor_type
    {
    public:
        item_visitor_type(PtSegStrategy const& strategy)
            : m_intersection_found(false)
            , m_strategy(strategy)
        {}

        template <typename Item1, typename Item2>
        inline bool apply(Item1 const& item1, Item2 const& item2)
        {
            if (! m_intersection_found
                && ! dispatch::disjoint<Item1, Item2>::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<Linear const> 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 <typename Strategy>
    static inline bool apply(MultiPoint const& multipoint, Linear const& linear, Strategy const& strategy)
    {
        item_visitor_type<Strategy> 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<typename point_type<MultiPoint>::type>
            >::apply(multipoint, segment_range(linear), visitor,
                     expand_box_point<expand_point_strategy_type>(),
                     overlaps_box_point<disjoint_pb_strategy_type>(),
                     expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()),
                     overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy()));

        return ! visitor.intersection_found();
    }

    template <typename Strategy>
    static inline bool apply(Linear const& linear, MultiPoint const& multipoint, Strategy const& strategy)
    {
        return apply(multipoint, linear, strategy);
    }
};


template <typename MultiPoint, typename SingleGeometry>
class multi_point_single_geometry
{
public:
    template <typename Strategy>
    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<MultiPoint>::type point1_type;
        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 )
        {
            // The default strategy is enough for Point/Box
            if (! detail::disjoint::disjoint_point_box(*it, box2, d_pb_strategy_type())
                && ! dispatch::disjoint<point1_type, SingleGeometry>::apply(*it, single_geometry, strategy))
            {
                return false;
            }
        }

        return true;
    }

    template <typename Strategy>
    static inline bool apply(SingleGeometry const& single_geometry, MultiPoint const& multi_point, Strategy const& strategy)
    {
        return apply(multi_point, single_geometry, strategy);
    }
};


template <typename MultiPoint, typename MultiGeometry>
class multi_point_multi_geometry
{
private:
    template <typename ExpandPointStrategy>
    struct expand_box_point
    {
        template <typename Box, typename Point>
        static inline void apply(Box& total, Point const& point)
        {
            geometry::expand(total, point, ExpandPointStrategy());
        }
    };

    template <typename ExpandBoxStrategy>
    struct expand_box_box_pair
    {
        template <typename Box, typename BoxPair>
        inline void apply(Box& total, BoxPair const& box_pair) const
        {
            geometry::expand(total, box_pair.first, ExpandBoxStrategy());
        }
    };

    template <typename DisjointPointBoxStrategy>
    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,
                                                          DisjointPointBoxStrategy());
        }
    };

    template <typename DisjointBoxBoxStrategy>
    struct overlaps_box_box_pair
    {
        template <typename Box, typename BoxPair>
        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 <typename PtSegStrategy>
    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 <typename Point, typename BoxPair>
        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<MultiGeometry>::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<Point, single_type>::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 <typename Strategy>
    static inline bool apply(MultiPoint const& multi_point, MultiGeometry const& multi_geometry, Strategy const& strategy)
    {
        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;

        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;
        }

        item_visitor_type<Strategy> 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 <typename Strategy>
    static inline bool apply(MultiGeometry const& multi_geometry, MultiPoint const& multi_point, Strategy const& strategy)
    {
        return apply(multi_point, multi_geometry, strategy);
    }
};


template <typename MultiPoint, typename Areal, typename Tag = typename tag<Areal>::type>
struct multipoint_areal
    : multi_point_single_geometry<MultiPoint, Areal>
{};

template <typename MultiPoint, typename Areal>
struct multipoint_areal<MultiPoint, Areal, multi_polygon_tag>
    : multi_point_multi_geometry<MultiPoint, Areal>
{};


}} // namespace detail::disjoint
#endif // DOXYGEN_NO_DETAIL


#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{


template <typename Point, typename MultiPoint, std::size_t DimensionCount>
struct disjoint
    <
        Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false
    > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Point>
{};


template <typename MultiPoint, typename Segment, std::size_t DimensionCount>
struct disjoint
    <
        MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false
    > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Segment>
{};


template <typename MultiPoint, typename Box, std::size_t DimensionCount>
struct disjoint
    <
        MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false
    > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Box>
{};


template
<
    typename MultiPoint1,
    typename MultiPoint2,
    std::size_t DimensionCount
>
struct disjoint
    <
        MultiPoint1, MultiPoint2, DimensionCount,
        multi_point_tag, multi_point_tag, false
    >
{
    template <typename Strategy>
    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 <typename Linear, typename MultiPoint, std::size_t DimensionCount>
struct disjoint
    <
        Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false
    > : detail::disjoint::multipoint_linear<MultiPoint, Linear>
{};


template <typename MultiPoint, typename Linear, std::size_t DimensionCount>
struct disjoint
    <
        MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false
    > : detail::disjoint::multipoint_linear<MultiPoint, Linear>
{};


template <typename Areal, typename MultiPoint, std::size_t DimensionCount>
struct disjoint
    <
        Areal, MultiPoint, DimensionCount, areal_tag, multi_point_tag, false
    > : detail::disjoint::multipoint_areal<MultiPoint, Areal>
{};


template <typename MultiPoint, typename Areal, std::size_t DimensionCount>
struct disjoint
    <
        MultiPoint, Areal, DimensionCount, multi_point_tag, areal_tag, false
    > : detail::disjoint::multipoint_areal<MultiPoint, Areal>
{};


} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH


}} // namespace boost::geometry


#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP
Commit	Line	Data
b32b8144 FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
b32b8144 FG	2
b32b8144 FG	3	// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
b32b8144 FG	4
92f5a8d4	5	// Copyright (c) 2014-2019, Oracle and/or its affiliates.
b32b8144 FG	6	// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
	7	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
	8
	9	// Licensed under the Boost Software License version 1.0.
	10	// http://www.boost.org/users/license.html
	11
	12	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP
	13	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP
	14
	15	#include <algorithm>
	16	#include <vector>
	17
	18	#include <boost/range.hpp>
	19	#include <boost/mpl/assert.hpp>
	20
	21	#include <boost/geometry/core/assert.hpp>
	22	#include <boost/geometry/core/tag.hpp>
	23	#include <boost/geometry/core/tags.hpp>
	24
	25	#include <boost/geometry/geometries/box.hpp>
	26
	27	#include <boost/geometry/iterators/segment_iterator.hpp>
	28
	29	#include <boost/geometry/algorithms/envelope.hpp>
	30	#include <boost/geometry/algorithms/expand.hpp>
	31
	32	#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
	33	#include <boost/geometry/algorithms/detail/partition.hpp>
	34	#include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
	35	#include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp>
	36	#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
	37	#include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
	38	#include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
	39
	40	#include <boost/geometry/algorithms/dispatch/disjoint.hpp>
	41
	42	#include <boost/geometry/policies/compare.hpp>
	43
	44
	45	namespace boost { namespace geometry
	46	{
	47
	48
	49	#ifndef DOXYGEN_NO_DETAIL
	50	namespace detail { namespace disjoint
	51	{
	52
	53
b32b8144 FG	54	class multipoint_multipoint
	55	{
	56	private:
92f5a8d4	57	template <typename Iterator, typename CSTag>
b32b8144	58	class unary_disjoint_predicate
92f5a8d4	59	: geometry::less<void, -1, CSTag>
b32b8144 FG	60	{
b32b8144 FG	61	private:
92f5a8d4	62	typedef geometry::less<void, -1, CSTag> base_type;
b32b8144 FG	63
	64	public:
	65	unary_disjoint_predicate(Iterator first, Iterator last)
	66	: base_type(), m_first(first), m_last(last)
	67	{}
	68
	69	template <typename Point>
	70	inline bool apply(Point const& point) const
	71	{
	72	return !std::binary_search(m_first,
	73	m_last,
	74	point,
	75	static_cast<base_type const&>(*this));
	76	}
	77
	78	private:
	79	Iterator m_first, m_last;
	80	};
	81
	82	public:
92f5a8d4	83	template <typename MultiPoint1, typename MultiPoint2, typename Strategy>
b32b8144	84	static inline bool apply(MultiPoint1 const& multipoint1,
92f5a8d4 TL	85	MultiPoint2 const& multipoint2,
92f5a8d4 TL	86	Strategy const&)
b32b8144	87	{
92f5a8d4 TL	88	typedef typename Strategy::cs_tag cs_tag;
	89	typedef geometry::less<void, -1, cs_tag> less_type;
	90
b32b8144 FG	91	BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) );
	92
	93	typedef typename boost::range_value<MultiPoint1>::type point1_type;
	94
	95	std::vector<point1_type> points1(boost::begin(multipoint1),
	96	boost::end(multipoint1));
	97
92f5a8d4	98	std::sort(points1.begin(), points1.end(), less_type());
b32b8144 FG	99
	100	typedef unary_disjoint_predicate
	101	<
92f5a8d4 TL	102	typename std::vector<point1_type>::const_iterator,
92f5a8d4 TL	103	cs_tag
b32b8144 FG	104	> predicate_type;
	105
	106	return check_iterator_range
	107	<
	108	predicate_type
	109	>::apply(boost::begin(multipoint2),
	110	boost::end(multipoint2),
	111	predicate_type(points1.begin(), points1.end()));
	112	}
	113	};
	114
	115
	116	template <typename MultiPoint, typename Linear>
	117	class multipoint_linear
	118	{
	119	private:
92f5a8d4	120	template <typename ExpandPointBoxStrategy>
b32b8144 FG	121	struct expand_box_point
	122	{
	123	template <typename Box, typename Point>
	124	static inline void apply(Box& total, Point const& point)
	125	{
92f5a8d4	126	geometry::expand(total, point, ExpandPointBoxStrategy());
b32b8144 FG	127	}
	128	};
	129
	130	template <typename EnvelopeStrategy>
	131	struct expand_box_segment
	132	{
	133	explicit expand_box_segment(EnvelopeStrategy const& strategy)
	134	: m_strategy(strategy)
	135	{}
	136
	137	template <typename Box, typename Segment>
	138	inline void apply(Box& total, Segment const& segment) const
	139	{
	140	geometry::expand(total,
92f5a8d4 TL	141	geometry::return_envelope<Box>(segment, m_strategy),
92f5a8d4 TL	142	typename EnvelopeStrategy::box_expand_strategy_type());
b32b8144 FG	143	}
	144
	145	EnvelopeStrategy const& m_strategy;
	146	};
	147
92f5a8d4	148	template <typename DisjointPointBoxStrategy>
b32b8144 FG	149	struct overlaps_box_point
	150	{
	151	template <typename Box, typename Point>
	152	static inline bool apply(Box const& box, Point const& point)
	153	{
	154	// The default strategy is enough in this case
92f5a8d4 TL	155	return ! detail::disjoint::disjoint_point_box(point, box,
92f5a8d4 TL	156	DisjointPointBoxStrategy());
b32b8144 FG	157	}
	158	};
	159
	160	template <typename DisjointStrategy>
	161	struct overlaps_box_segment
	162	{
	163	explicit overlaps_box_segment(DisjointStrategy const& strategy)
	164	: m_strategy(strategy)
	165	{}
	166
	167	template <typename Box, typename Segment>
	168	inline bool apply(Box const& box, Segment const& segment) const
	169	{
	170	return ! dispatch::disjoint<Segment, Box>::apply(segment, box, m_strategy);
	171	}
	172
	173	DisjointStrategy const& m_strategy;
	174	};
	175
	176	template <typename PtSegStrategy>
	177	class item_visitor_type
	178	{
	179	public:
	180	item_visitor_type(PtSegStrategy const& strategy)
	181	: m_intersection_found(false)
	182	, m_strategy(strategy)
	183	{}
	184
	185	template <typename Item1, typename Item2>
	186	inline bool apply(Item1 const& item1, Item2 const& item2)
	187	{
	188	if (! m_intersection_found
	189	&& ! dispatch::disjoint<Item1, Item2>::apply(item1, item2, m_strategy))
	190	{
	191	m_intersection_found = true;
	192	return false;
	193	}
	194	return true;
	195	}
	196
	197	inline bool intersection_found() const { return m_intersection_found; }
	198
	199	private:
	200	bool m_intersection_found;
	201	PtSegStrategy const& m_strategy;
	202	};
	203	// structs for partition -- end
	204
	205	class segment_range
	206	{
	207	public:
	208	typedef geometry::segment_iterator<Linear const> const_iterator;
	209	typedef const_iterator iterator;
	210
	211	segment_range(Linear const& linear)
	212	: m_linear(linear)
	213	{}
	214
	215	const_iterator begin() const
	216	{
	217	return geometry::segments_begin(m_linear);
	218	}
	219
	220	const_iterator end() const
221	{
222	return geometry::segments_end(m_linear);
223	}
224
225	private:
226	Linear const& m_linear;
227	};
228
229	public:
230	template <typename Strategy>
231	static inline bool apply(MultiPoint const& multipoint, Linear const& linear, Strategy const& strategy)
232	{
233	item_visitor_type<Strategy> visitor(strategy);
234
92f5a8d4	235	typedef typename Strategy::expand_point_strategy_type expand_point_strategy_type;
b32b8144 FG	236	typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
b32b8144 FG	237	typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type;
92f5a8d4	238	typedef typename Strategy::disjoint_point_box_strategy_type disjoint_pb_strategy_type;
b32b8144 FG	239
	240	// TODO: disjoint Segment/Box may be called in partition multiple times
	241	// possibly for non-cartesian segments which could be slow. We should consider
	242	// passing a range of bounding boxes of segments after calculating them once.
	243	// Alternatively instead of a range of segments a range of Segment/Envelope pairs
	244	// should be passed, where envelope would be lazily calculated when needed the first time
	245	geometry::partition
	246	<
	247	geometry::model::box<typename point_type<MultiPoint>::type>
	248	>::apply(multipoint, segment_range(linear), visitor,
92f5a8d4 TL	249	expand_box_point<expand_point_strategy_type>(),
92f5a8d4 TL	250	overlaps_box_point<disjoint_pb_strategy_type>(),
b32b8144 FG	251	expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()),
	252	overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy()));
	253
	254	return ! visitor.intersection_found();
	255	}
	256
	257	template <typename Strategy>
	258	static inline bool apply(Linear const& linear, MultiPoint const& multipoint, Strategy const& strategy)
	259	{
	260	return apply(multipoint, linear, strategy);
	261	}
	262	};
	263
	264
	265	template <typename MultiPoint, typename SingleGeometry>
	266	class multi_point_single_geometry
	267	{
	268	public:
	269	template <typename Strategy>
92f5a8d4 TL	270	static inline bool apply(MultiPoint const& multi_point,
	271	SingleGeometry const& single_geometry,
	272	Strategy const& strategy)
b32b8144	273	{
92f5a8d4 TL	274	typedef typename Strategy::disjoint_point_box_strategy_type d_pb_strategy_type;
92f5a8d4 TL	275
b32b8144 FG	276	typedef typename point_type<MultiPoint>::type point1_type;
	277	typedef typename point_type<SingleGeometry>::type point2_type;
	278	typedef model::box<point2_type> box2_type;
	279
	280	box2_type box2;
	281	geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy());
	282	geometry::detail::expand_by_epsilon(box2);
	283
	284	typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
	285	for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
	286	{
	287	// The default strategy is enough for Point/Box
92f5a8d4	288	if (! detail::disjoint::disjoint_point_box(*it, box2, d_pb_strategy_type())
b32b8144 FG	289	&& ! dispatch::disjoint<point1_type, SingleGeometry>::apply(*it, single_geometry, strategy))
	290	{
	291	return false;
	292	}
	293	}
	294
	295	return true;
	296	}
	297
	298	template <typename Strategy>
	299	static inline bool apply(SingleGeometry const& single_geometry, MultiPoint const& multi_point, Strategy const& strategy)
	300	{
	301	return apply(multi_point, single_geometry, strategy);
	302	}
	303	};
	304
	305
	306	template <typename MultiPoint, typename MultiGeometry>
	307	class multi_point_multi_geometry
	308	{
	309	private:
92f5a8d4	310	template <typename ExpandPointStrategy>
b32b8144 FG	311	struct expand_box_point
	312	{
	313	template <typename Box, typename Point>
	314	static inline void apply(Box& total, Point const& point)
	315	{
92f5a8d4	316	geometry::expand(total, point, ExpandPointStrategy());
b32b8144 FG	317	}
	318	};
	319
92f5a8d4	320	template <typename ExpandBoxStrategy>
b32b8144 FG	321	struct expand_box_box_pair
	322	{
	323	template <typename Box, typename BoxPair>
	324	inline void apply(Box& total, BoxPair const& box_pair) const
	325	{
92f5a8d4	326	geometry::expand(total, box_pair.first, ExpandBoxStrategy());
b32b8144 FG	327	}
	328	};
	329
92f5a8d4	330	template <typename DisjointPointBoxStrategy>
b32b8144 FG	331	struct overlaps_box_point
	332	{
	333	template <typename Box, typename Point>
	334	static inline bool apply(Box const& box, Point const& point)
	335	{
	336	// The default strategy is enough for Point/Box
92f5a8d4 TL	337	return ! detail::disjoint::disjoint_point_box(point, box,
92f5a8d4 TL	338	DisjointPointBoxStrategy());
b32b8144 FG	339	}
	340	};
	341
92f5a8d4	342	template <typename DisjointBoxBoxStrategy>
b32b8144 FG	343	struct overlaps_box_box_pair
	344	{
	345	template <typename Box, typename BoxPair>
	346	inline bool apply(Box const& box, BoxPair const& box_pair) const
	347	{
	348	// The default strategy is enough for Box/Box
92f5a8d4 TL	349	return ! detail::disjoint::disjoint_box_box(box_pair.first, box,
92f5a8d4 TL	350	DisjointBoxBoxStrategy());
b32b8144 FG	351	}
	352	};
	353
	354	template <typename PtSegStrategy>
	355	class item_visitor_type
	356	{
	357	public:
	358	item_visitor_type(MultiGeometry const& multi_geometry,
	359	PtSegStrategy const& strategy)
	360	: m_intersection_found(false)
	361	, m_multi_geometry(multi_geometry)
	362	, m_strategy(strategy)
	363	{}
	364
	365	template <typename Point, typename BoxPair>
	366	inline bool apply(Point const& point, BoxPair const& box_pair)
	367	{
92f5a8d4 TL	368	typedef typename PtSegStrategy::disjoint_point_box_strategy_type d_pb_strategy_type;
92f5a8d4 TL	369
b32b8144 FG	370	typedef typename boost::range_value<MultiGeometry>::type single_type;
	371
	372	// The default strategy is enough for Point/Box
	373	if (! m_intersection_found
92f5a8d4	374	&& ! detail::disjoint::disjoint_point_box(point, box_pair.first, d_pb_strategy_type())
b32b8144 FG	375	&& ! dispatch::disjoint<Point, single_type>::apply(point, range::at(m_multi_geometry, box_pair.second), m_strategy))
	376	{
	377	m_intersection_found = true;
	378	return false;
	379	}
	380	return true;
	381	}
	382
	383	inline bool intersection_found() const { return m_intersection_found; }
	384
	385	private:
	386	bool m_intersection_found;
	387	MultiGeometry const& m_multi_geometry;
	388	PtSegStrategy const& m_strategy;
	389	};
	390	// structs for partition -- end
	391
	392	public:
	393	template <typename Strategy>
	394	static inline bool apply(MultiPoint const& multi_point, MultiGeometry const& multi_geometry, Strategy const& strategy)
	395	{
	396	typedef typename point_type<MultiPoint>::type point1_type;
	397	typedef typename point_type<MultiGeometry>::type point2_type;
	398	typedef model::box<point1_type> box1_type;
	399	typedef model::box<point2_type> box2_type;
	400	typedef std::pair<box2_type, std::size_t> box_pair_type;
	401
	402	typename Strategy::envelope_strategy_type const
	403	envelope_strategy = strategy.get_envelope_strategy();
	404
	405	std::size_t count2 = boost::size(multi_geometry);
	406	std::vector<box_pair_type> boxes(count2);
	407	for (std::size_t i = 0 ; i < count2 ; ++i)
	408	{
	409	geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy);
	410	geometry::detail::expand_by_epsilon(boxes[i].first);
	411	boxes[i].second = i;
	412	}
	413
	414	item_visitor_type<Strategy> visitor(multi_geometry, strategy);
	415
92f5a8d4 TL	416	typedef expand_box_point
	417	<
	418	typename Strategy::expand_point_strategy_type
	419	> expand_box_point_type;
	420	typedef overlaps_box_point
	421	<
	422	typename Strategy::disjoint_point_box_strategy_type
	423	> overlaps_box_point_type;
	424	typedef expand_box_box_pair
	425	<
	426	typename Strategy::envelope_strategy_type::box_expand_strategy_type
	427	> expand_box_box_pair_type;
	428	typedef overlaps_box_box_pair
	429	<
	430	typename Strategy::disjoint_box_box_strategy_type
	431	> overlaps_box_box_pair_type;
	432
b32b8144 FG	433	geometry::partition
	434	<
	435	box1_type
	436	>::apply(multi_point, boxes, visitor,
92f5a8d4 TL	437	expand_box_point_type(),
	438	overlaps_box_point_type(),
	439	expand_box_box_pair_type(),
	440	overlaps_box_box_pair_type());
b32b8144 FG	441
	442	return ! visitor.intersection_found();
	443	}
	444
	445	template <typename Strategy>
	446	static inline bool apply(MultiGeometry const& multi_geometry, MultiPoint const& multi_point, Strategy const& strategy)
	447	{
	448	return apply(multi_point, multi_geometry, strategy);
	449	}
	450	};
	451
	452
	453	template <typename MultiPoint, typename Areal, typename Tag = typename tag<Areal>::type>
	454	struct multipoint_areal
	455	: multi_point_single_geometry<MultiPoint, Areal>
	456	{};
	457
	458	template <typename MultiPoint, typename Areal>
	459	struct multipoint_areal<MultiPoint, Areal, multi_polygon_tag>
	460	: multi_point_multi_geometry<MultiPoint, Areal>
	461	{};
	462
	463
	464	}} // namespace detail::disjoint
	465	#endif // DOXYGEN_NO_DETAIL
	466
	467
	468
	469
	470	#ifndef DOXYGEN_NO_DISPATCH
	471	namespace dispatch
	472	{
	473
	474
	475	template <typename Point, typename MultiPoint, std::size_t DimensionCount>
	476	struct disjoint
	477	<
	478	Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false
	479	> : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Point>
	480	{};
	481
	482
	483	template <typename MultiPoint, typename Segment, std::size_t DimensionCount>
	484	struct disjoint
	485	<
	486	MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false
	487	> : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Segment>
	488	{};
	489
	490
	491	template <typename MultiPoint, typename Box, std::size_t DimensionCount>
	492	struct disjoint
	493	<
	494	MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false
	495	> : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Box>
	496	{};
	497
	498
	499	template
	500	<
	501	typename MultiPoint1,
	502	typename MultiPoint2,
	503	std::size_t DimensionCount
	504	>
505	struct disjoint
506	<
507	MultiPoint1, MultiPoint2, DimensionCount,
508	multi_point_tag, multi_point_tag, false
509	>
510	{
511	template <typename Strategy>
512	static inline bool apply(MultiPoint1 const& multipoint1,
513	MultiPoint2 const& multipoint2,
92f5a8d4	514	Strategy const& strategy)
b32b8144 FG	515	{
	516	if ( boost::size(multipoint2) < boost::size(multipoint1) )
	517	{
	518	return detail::disjoint::multipoint_multipoint
92f5a8d4	519	::apply(multipoint2, multipoint1, strategy);
b32b8144 FG	520	}
	521
	522	return detail::disjoint::multipoint_multipoint
92f5a8d4	523	::apply(multipoint1, multipoint2, strategy);
b32b8144 FG	524	}
	525	};
	526
	527
	528	template <typename Linear, typename MultiPoint, std::size_t DimensionCount>
	529	struct disjoint
	530	<
	531	Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false
	532	> : detail::disjoint::multipoint_linear<MultiPoint, Linear>
	533	{};
	534
	535
	536	template <typename MultiPoint, typename Linear, std::size_t DimensionCount>
	537	struct disjoint
	538	<
	539	MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false
	540	> : detail::disjoint::multipoint_linear<MultiPoint, Linear>
	541	{};
	542
	543
	544	template <typename Areal, typename MultiPoint, std::size_t DimensionCount>
	545	struct disjoint
	546	<
	547	Areal, MultiPoint, DimensionCount, areal_tag, multi_point_tag, false
	548	> : detail::disjoint::multipoint_areal<MultiPoint, Areal>
	549	{};
	550
	551
	552	template <typename MultiPoint, typename Areal, std::size_t DimensionCount>
	553	struct disjoint
	554	<
	555	MultiPoint, Areal, DimensionCount, multi_point_tag, areal_tag, false
	556	> : detail::disjoint::multipoint_areal<MultiPoint, Areal>
	557	{};
	558
	559
	560	} // namespace dispatch
	561	#endif // DOXYGEN_NO_DISPATCH
	562
	563
	564	}} // namespace boost::geometry
	565
	566
	567
	568	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP