[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-2020, 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/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/size.hpp>
#include <boost/range/value_type.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>


// TEMP
#include <boost/geometry/strategies/envelope/cartesian.hpp>
#include <boost/geometry/strategies/envelope/geographic.hpp>
#include <boost/geometry/strategies/envelope/spherical.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),
                             // TEMP - envelope umbrella strategy also contains
                             //        expand strategies
                             strategies::envelope::services::strategy_converter
                                <
                                    EnvelopeStrategy
                                >::get(m_strategy));
        }

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