[ceph.git] / ceph / src / boost / libs / geometry / include / boost / geometry / algorithms / detail / within / point_in_geometry.hpp

// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.

// This file was modified by Oracle on 2013, 2014, 2015.
// Modifications copyright (c) 2013-2015, Oracle and/or its affiliates.

// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.

// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle

#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP


#include <boost/core/ignore_unused.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/range.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/remove_reference.hpp>

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

#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
#include <boost/geometry/algorithms/detail/interior_iterator.hpp>

#include <boost/geometry/geometries/concepts/check.hpp>
#include <boost/geometry/strategies/concepts/within_concept.hpp>
#include <boost/geometry/strategies/default_strategy.hpp>
#include <boost/geometry/strategies/within.hpp>
#include <boost/geometry/strategies/covered_by.hpp>

#include <boost/geometry/util/range.hpp>
#include <boost/geometry/views/detail/normalized_view.hpp>

namespace boost { namespace geometry {

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace within {

// TODO: is this needed?
inline int check_result_type(int result)
{
    return result;
}

template <typename T>
inline T check_result_type(T result)
{
    BOOST_GEOMETRY_ASSERT(false);
    return result;
}

template <typename Point, typename Range, typename Strategy> inline
int point_in_range(Point const& point, Range const& range, Strategy const& strategy)
{
    boost::ignore_unused(strategy);

    typedef typename boost::range_iterator<Range const>::type iterator_type;
    typename Strategy::state_type state;
    iterator_type it = boost::begin(range);
    iterator_type end = boost::end(range);

    for ( iterator_type previous = it++ ; it != end ; ++previous, ++it )
    {
        if ( ! strategy.apply(point, *previous, *it, state) )
        {
            break;
        }
    }

    return check_result_type(strategy.result(state));
}

template <typename Geometry, typename Point, typename Range>
inline int point_in_range(Point const& point, Range const& range)
{
    typedef typename point_type<Point>::type point_type1;
    typedef typename point_type<Geometry>::type point_type2;

    typedef typename strategy::within::services::default_strategy
        <
            typename tag<Point>::type,
            typename tag<Geometry>::type,
            typename tag<Point>::type,
            typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
            typename tag_cast
                <
                    typename cs_tag<point_type1>::type, spherical_tag
                >::type,
            typename tag_cast
                <
                    typename cs_tag<point_type2>::type, spherical_tag
                >::type,
            Point,
            Geometry
        >::type strategy_type;

    typedef typename strategy::covered_by::services::default_strategy
        <
            typename tag<Point>::type,
            typename tag<Geometry>::type,
            typename tag<Point>::type,
            typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
            typename tag_cast
                <
                    typename cs_tag<point_type1>::type, spherical_tag
                >::type,
            typename tag_cast
                <
                    typename cs_tag<point_type2>::type, spherical_tag
                >::type,
            Point,
            Geometry
        >::type strategy_type2;

    static const bool same_strategies = boost::is_same<strategy_type, strategy_type2>::value;
    BOOST_MPL_ASSERT_MSG((same_strategies),
                         DEFAULT_WITHIN_AND_COVERED_BY_STRATEGIES_NOT_COMPATIBLE,
                         (strategy_type, strategy_type2));

    return point_in_range(point, range, strategy_type());
}

}} // namespace detail::within

namespace detail_dispatch { namespace within {

// checks the relation between a point P and geometry G
// returns 1 if P is in the interior of G
// returns 0 if P is on the boundry of G
// returns -1 if P is in the exterior of G

template <typename Geometry,
          typename Tag = typename geometry::tag<Geometry>::type>
struct point_in_geometry
    : not_implemented<Tag>
{};

template <typename Point2>
struct point_in_geometry<Point2, point_tag>
{
    template <typename Point1, typename Strategy> static inline
    int apply(Point1 const& point1, Point2 const& point2, Strategy const& strategy)
    {
        boost::ignore_unused(strategy);
        return strategy.apply(point1, point2) ? 1 : -1;
    }
};

template <typename Segment>
struct point_in_geometry<Segment, segment_tag>
{
    template <typename Point, typename Strategy> static inline
    int apply(Point const& point, Segment const& segment, Strategy const& strategy)
    {
        boost::ignore_unused(strategy);

        typedef typename geometry::point_type<Segment>::type point_type;
        point_type p0, p1;
// TODO: don't copy points
        detail::assign_point_from_index<0>(segment, p0);
        detail::assign_point_from_index<1>(segment, p1);

        typename Strategy::state_type state;
        strategy.apply(point, p0, p1, state);
        int r = detail::within::check_result_type(strategy.result(state));

        if ( r != 0 )
            return -1; // exterior

        // if the point is equal to the one of the terminal points
        if ( detail::equals::equals_point_point(point, p0)
          || detail::equals::equals_point_point(point, p1) )
            return 0; // boundary
        else
            return 1; // interior
    }
};


template <typename Linestring>
struct point_in_geometry<Linestring, linestring_tag>
{
    template <typename Point, typename Strategy> static inline
    int apply(Point const& point, Linestring const& linestring, Strategy const& strategy)
    {
        std::size_t count = boost::size(linestring);
        if ( count > 1 )
        {
            if ( detail::within::point_in_range(point, linestring, strategy) != 0 )
                return -1; // exterior

            // if the linestring doesn't have a boundary
            if (detail::equals::equals_point_point(range::front(linestring), range::back(linestring)))
                return 1; // interior
            // else if the point is equal to the one of the terminal points
            else if (detail::equals::equals_point_point(point, range::front(linestring))
                || detail::equals::equals_point_point(point, range::back(linestring)))
                return 0; // boundary
            else
                return 1; // interior
        }
// TODO: for now degenerated linestrings are ignored
//       throw an exception here?
        /*else if ( count == 1 )
        {
            if ( detail::equals::equals_point_point(point, range::front(linestring)) )
                return 1;
        }*/

        return -1; // exterior
    }
};

template <typename Ring>
struct point_in_geometry<Ring, ring_tag>
{
    template <typename Point, typename Strategy> static inline
    int apply(Point const& point, Ring const& ring, Strategy const& strategy)
    {
        if ( boost::size(ring) < core_detail::closure::minimum_ring_size
                                    <
                                        geometry::closure<Ring>::value
                                    >::value )
        {
            return -1;
        }

        detail::normalized_view<Ring const> view(ring);
        return detail::within::point_in_range(point, view, strategy);
    }
};

// Polygon: in exterior ring, and if so, not within interior ring(s)
template <typename Polygon>
struct point_in_geometry<Polygon, polygon_tag>
{
    template <typename Point, typename Strategy>
    static inline int apply(Point const& point, Polygon const& polygon,
                            Strategy const& strategy)
    {
        int const code = point_in_geometry
            <
                typename ring_type<Polygon>::type
            >::apply(point, exterior_ring(polygon), strategy);

        if (code == 1)
        {
            typename interior_return_type<Polygon const>::type
                rings = interior_rings(polygon);
            
            for (typename detail::interior_iterator<Polygon const>::type
                 it = boost::begin(rings);
                 it != boost::end(rings);
                 ++it)
            {
                int const interior_code = point_in_geometry
                    <
                        typename ring_type<Polygon>::type
                    >::apply(point, *it, strategy);

                if (interior_code != -1)
                {
                    // If 0, return 0 (touch)
                    // If 1 (inside hole) return -1 (outside polygon)
                    // If -1 (outside hole) check other holes if any
                    return -interior_code;
                }
            }
        }
        return code;
    }
};

template <typename Geometry>
struct point_in_geometry<Geometry, multi_point_tag>
{
    template <typename Point, typename Strategy> static inline
    int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
    {
        typedef typename boost::range_value<Geometry>::type point_type;
        typedef typename boost::range_const_iterator<Geometry>::type iterator;
        for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
        {
            int pip = point_in_geometry<point_type>::apply(point, *it, strategy);

            //BOOST_GEOMETRY_ASSERT(pip != 0);
            if ( pip > 0 ) // inside
                return 1;
        }

        return -1; // outside
    }
};

template <typename Geometry>
struct point_in_geometry<Geometry, multi_linestring_tag>
{
    template <typename Point, typename Strategy> static inline
    int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
    {
        int pip = -1; // outside

        typedef typename boost::range_value<Geometry>::type linestring_type;
        typedef typename boost::range_value<linestring_type>::type point_type;
        typedef typename boost::range_iterator<Geometry const>::type iterator;
        iterator it = boost::begin(geometry);
        for ( ; it != boost::end(geometry) ; ++it )
        {
            pip = point_in_geometry<linestring_type>::apply(point, *it, strategy);

            // inside or on the boundary
            if ( pip >= 0 )
            {
                ++it;
                break;
            }
        }

        // outside
        if ( pip < 0 )
            return -1;

        // TODO: the following isn't needed for covered_by()

        unsigned boundaries = pip == 0 ? 1 : 0;

        for ( ; it != boost::end(geometry) ; ++it )
        {
            if ( boost::size(*it) < 2 )
                continue;

            point_type const& front = range::front(*it);
            point_type const& back = range::back(*it);

            // is closed_ring - no boundary
            if ( detail::equals::equals_point_point(front, back) )
                continue;

            // is point on boundary
            if ( detail::equals::equals_point_point(point, front)
              || detail::equals::equals_point_point(point, back) )
            {
                ++boundaries;
            }
        }

        // if the number of boundaries is odd, the point is on the boundary
        return boundaries % 2 ? 0 : 1;
    }
};

template <typename Geometry>
struct point_in_geometry<Geometry, multi_polygon_tag>
{
    template <typename Point, typename Strategy> static inline
    int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
    {
        // For invalid multipolygons
        //int res = -1; // outside

        typedef typename boost::range_value<Geometry>::type polygon_type;
        typedef typename boost::range_const_iterator<Geometry>::type iterator;
        for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
        {
            int pip = point_in_geometry<polygon_type>::apply(point, *it, strategy);

            // inside or on the boundary
            if ( pip >= 0 )
                return pip;

            // For invalid multi-polygons
            //if ( 1 == pip ) // inside polygon
            //    return 1;
            //else if ( res < pip ) // point must be inside at least one polygon
            //    res = pip;
        }

        return -1; // for valid multipolygons
        //return res; // for invalid multipolygons
    }
};

}} // namespace detail_dispatch::within

namespace detail { namespace within {

// 1 - in the interior
// 0 - in the boundry
// -1 - in the exterior
template <typename Point, typename Geometry, typename Strategy>
inline int point_in_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
{
    concepts::within::check
        <
            typename tag<Point>::type,
            typename tag<Geometry>::type,
            typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
            Strategy
        >();

    return detail_dispatch::within::point_in_geometry<Geometry>::apply(point, geometry, strategy);
}

template <typename Point, typename Geometry>
inline int point_in_geometry(Point const& point, Geometry const& geometry)
{
    typedef typename point_type<Point>::type point_type1;
    typedef typename point_type<Geometry>::type point_type2;

    typedef typename strategy::within::services::default_strategy
        <
            typename tag<Point>::type,
            typename tag<Geometry>::type,
            typename tag<Point>::type,
            typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
            typename tag_cast
                <
                    typename cs_tag<point_type1>::type, spherical_tag
                >::type,
            typename tag_cast
                <
                    typename cs_tag<point_type2>::type, spherical_tag
                >::type,
            Point,
            Geometry
        >::type strategy_type;

    typedef typename strategy::covered_by::services::default_strategy
        <
            typename tag<Point>::type,
            typename tag<Geometry>::type,
            typename tag<Point>::type,
            typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
            typename tag_cast
                <
                    typename cs_tag<point_type1>::type, spherical_tag
                >::type,
            typename tag_cast
                <
                    typename cs_tag<point_type2>::type, spherical_tag
                >::type,
            Point,
            Geometry
        >::type strategy_type2;

    static const bool same_strategies = boost::is_same<strategy_type, strategy_type2>::value;
    BOOST_MPL_ASSERT_MSG((same_strategies),
                         DEFAULT_WITHIN_AND_COVERED_BY_STRATEGIES_NOT_COMPATIBLE,
                         (strategy_type, strategy_type2));

    return point_in_geometry(point, geometry, strategy_type());
}

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

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2
	3	// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
	4	// Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
	5	// Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
	6	// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
	7
	8	// This file was modified by Oracle on 2013, 2014, 2015.
	9	// Modifications copyright (c) 2013-2015, Oracle and/or its affiliates.
	10
	11	// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
	12	// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
	13
	14	// Use, modification and distribution is subject to the Boost Software License,
	15	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	16	// http://www.boost.org/LICENSE_1_0.txt)
	17
	18	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
	19
	20	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
	21	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
	22
	23
	24	#include <boost/core/ignore_unused.hpp>
	25	#include <boost/mpl/assert.hpp>
	26	#include <boost/range.hpp>
	27	#include <boost/type_traits/is_same.hpp>
	28	#include <boost/type_traits/remove_reference.hpp>
	29
	30	#include <boost/geometry/core/assert.hpp>
	31
	32	#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
	33	#include <boost/geometry/algorithms/detail/interior_iterator.hpp>
	34
	35	#include <boost/geometry/geometries/concepts/check.hpp>
	36	#include <boost/geometry/strategies/concepts/within_concept.hpp>
	37	#include <boost/geometry/strategies/default_strategy.hpp>
	38	#include <boost/geometry/strategies/within.hpp>
	39	#include <boost/geometry/strategies/covered_by.hpp>
	40
	41	#include <boost/geometry/util/range.hpp>
	42	#include <boost/geometry/views/detail/normalized_view.hpp>
	43
	44	namespace boost { namespace geometry {
	45
	46	#ifndef DOXYGEN_NO_DETAIL
	47	namespace detail { namespace within {
	48
	49	// TODO: is this needed?
	50	inline int check_result_type(int result)
	51	{
	52	return result;
	53	}
	54
	55	template <typename T>
	56	inline T check_result_type(T result)
	57	{
	58	BOOST_GEOMETRY_ASSERT(false);
	59	return result;
	60	}
	61
	62	template <typename Point, typename Range, typename Strategy> inline
	63	int point_in_range(Point const& point, Range const& range, Strategy const& strategy)
	64	{
65	boost::ignore_unused(strategy);
66
67	typedef typename boost::range_iterator<Range const>::type iterator_type;
68	typename Strategy::state_type state;
69	iterator_type it = boost::begin(range);
70	iterator_type end = boost::end(range);
71
72	for ( iterator_type previous = it++ ; it != end ; ++previous, ++it )
73	{
74	if ( ! strategy.apply(point, previous, it, state) )
75	{
76	break;
77	}
78	}
79
80	return check_result_type(strategy.result(state));
81	}
82
83	template <typename Geometry, typename Point, typename Range>
84	inline int point_in_range(Point const& point, Range const& range)
85	{
86	typedef typename point_type<Point>::type point_type1;
87	typedef typename point_type<Geometry>::type point_type2;
88
89	typedef typename strategy::within::services::default_strategy
90	<
91	typename tag<Point>::type,
92	typename tag<Geometry>::type,
93	typename tag<Point>::type,
94	typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
95	typename tag_cast
96	<
97	typename cs_tag<point_type1>::type, spherical_tag
98	>::type,
99	typename tag_cast
100	<
101	typename cs_tag<point_type2>::type, spherical_tag
102	>::type,
103	Point,
104	Geometry
105	>::type strategy_type;
106
107	typedef typename strategy::covered_by::services::default_strategy
108	<
109	typename tag<Point>::type,
110	typename tag<Geometry>::type,
111	typename tag<Point>::type,
112	typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
113	typename tag_cast
114	<
115	typename cs_tag<point_type1>::type, spherical_tag
116	>::type,
117	typename tag_cast
118	<
119	typename cs_tag<point_type2>::type, spherical_tag
120	>::type,
121	Point,
122	Geometry
123	>::type strategy_type2;
124
125	static const bool same_strategies = boost::is_same<strategy_type, strategy_type2>::value;
126	BOOST_MPL_ASSERT_MSG((same_strategies),
127	DEFAULT_WITHIN_AND_COVERED_BY_STRATEGIES_NOT_COMPATIBLE,
128	(strategy_type, strategy_type2));
129
130	return point_in_range(point, range, strategy_type());
131	}
132
133	}} // namespace detail::within
134
135	namespace detail_dispatch { namespace within {
136
137	// checks the relation between a point P and geometry G
138	// returns 1 if P is in the interior of G
139	// returns 0 if P is on the boundry of G
140	// returns -1 if P is in the exterior of G
141
142	template <typename Geometry,
143	typename Tag = typename geometry::tag<Geometry>::type>
144	struct point_in_geometry
145	: not_implemented<Tag>
146	{};
147
148	template <typename Point2>
149	struct point_in_geometry<Point2, point_tag>
150	{
151	template <typename Point1, typename Strategy> static inline
152	int apply(Point1 const& point1, Point2 const& point2, Strategy const& strategy)
153	{
154	boost::ignore_unused(strategy);
155	return strategy.apply(point1, point2) ? 1 : -1;
156	}
157	};
158
159	template <typename Segment>
160	struct point_in_geometry<Segment, segment_tag>
161	{
162	template <typename Point, typename Strategy> static inline
163	int apply(Point const& point, Segment const& segment, Strategy const& strategy)
164	{
165	boost::ignore_unused(strategy);
166
167	typedef typename geometry::point_type<Segment>::type point_type;
168	point_type p0, p1;
169	// TODO: don't copy points
170	detail::assign_point_from_index<0>(segment, p0);
171	detail::assign_point_from_index<1>(segment, p1);
172
173	typename Strategy::state_type state;
174	strategy.apply(point, p0, p1, state);
175	int r = detail::within::check_result_type(strategy.result(state));
176
177	if ( r != 0 )
178	return -1; // exterior
179
180	// if the point is equal to the one of the terminal points
181	if ( detail::equals::equals_point_point(point, p0)
182	\|\| detail::equals::equals_point_point(point, p1) )
183	return 0; // boundary
184	else
185	return 1; // interior
186	}
187	};
188
189
190	template <typename Linestring>
191	struct point_in_geometry<Linestring, linestring_tag>
192	{
193	template <typename Point, typename Strategy> static inline
194	int apply(Point const& point, Linestring const& linestring, Strategy const& strategy)
195	{
196	std::size_t count = boost::size(linestring);
197	if ( count > 1 )
198	{
199	if ( detail::within::point_in_range(point, linestring, strategy) != 0 )
200	return -1; // exterior
201
202	// if the linestring doesn't have a boundary
203	if (detail::equals::equals_point_point(range::front(linestring), range::back(linestring)))
204	return 1; // interior
205	// else if the point is equal to the one of the terminal points
206	else if (detail::equals::equals_point_point(point, range::front(linestring))
207	\|\| detail::equals::equals_point_point(point, range::back(linestring)))
208	return 0; // boundary
209	else
210	return 1; // interior
211	}
212	// TODO: for now degenerated linestrings are ignored
213	// throw an exception here?
214	/*else if ( count == 1 )
215	{
216	if ( detail::equals::equals_point_point(point, range::front(linestring)) )
217	return 1;
218	}*/
219
220	return -1; // exterior
221	}
222	};
223
224	template <typename Ring>
225	struct point_in_geometry<Ring, ring_tag>
226	{
227	template <typename Point, typename Strategy> static inline
228	int apply(Point const& point, Ring const& ring, Strategy const& strategy)
229	{
230	if ( boost::size(ring) < core_detail::closure::minimum_ring_size
231	<
232	geometry::closure<Ring>::value
233	>::value )
234	{
235	return -1;
236	}
237
238	detail::normalized_view<Ring const> view(ring);
239	return detail::within::point_in_range(point, view, strategy);
240	}
241	};
242
243	// Polygon: in exterior ring, and if so, not within interior ring(s)
244	template <typename Polygon>
245	struct point_in_geometry<Polygon, polygon_tag>
246	{
247	template <typename Point, typename Strategy>
248	static inline int apply(Point const& point, Polygon const& polygon,
249	Strategy const& strategy)
250	{
251	int const code = point_in_geometry
252	<
253	typename ring_type<Polygon>::type
254	>::apply(point, exterior_ring(polygon), strategy);
255
256	if (code == 1)
257	{
258	typename interior_return_type<Polygon const>::type
259	rings = interior_rings(polygon);
260
261	for (typename detail::interior_iterator<Polygon const>::type
262	it = boost::begin(rings);
263	it != boost::end(rings);
264	++it)
265	{
266	int const interior_code = point_in_geometry
267	<
268	typename ring_type<Polygon>::type
269	>::apply(point, *it, strategy);
270
271	if (interior_code != -1)
272	{
273	// If 0, return 0 (touch)
274	// If 1 (inside hole) return -1 (outside polygon)
275	// If -1 (outside hole) check other holes if any
276	return -interior_code;
277	}
278	}
279	}
280	return code;
281	}
282	};
283
284	template <typename Geometry>
285	struct point_in_geometry<Geometry, multi_point_tag>
286	{
287	template <typename Point, typename Strategy> static inline
288	int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
289	{
290	typedef typename boost::range_value<Geometry>::type point_type;
291	typedef typename boost::range_const_iterator<Geometry>::type iterator;
292	for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
293	{
294	int pip = point_in_geometry<point_type>::apply(point, *it, strategy);
295
296	//BOOST_GEOMETRY_ASSERT(pip != 0);
297	if ( pip > 0 ) // inside
298	return 1;
299	}
300
301	return -1; // outside
302	}
303	};
304
305	template <typename Geometry>
306	struct point_in_geometry<Geometry, multi_linestring_tag>
307	{
308	template <typename Point, typename Strategy> static inline
309	int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
310	{
311	int pip = -1; // outside
312
313	typedef typename boost::range_value<Geometry>::type linestring_type;
314	typedef typename boost::range_value<linestring_type>::type point_type;
315	typedef typename boost::range_iterator<Geometry const>::type iterator;
316	iterator it = boost::begin(geometry);
317	for ( ; it != boost::end(geometry) ; ++it )
318	{
319	pip = point_in_geometry<linestring_type>::apply(point, *it, strategy);
320
321	// inside or on the boundary
322	if ( pip >= 0 )
323	{
324	++it;
325	break;
326	}
327	}
328
329	// outside
330	if ( pip < 0 )
331	return -1;
332
333	// TODO: the following isn't needed for covered_by()
334
335	unsigned boundaries = pip == 0 ? 1 : 0;
336
337	for ( ; it != boost::end(geometry) ; ++it )
338	{
339	if ( boost::size(*it) < 2 )
340	continue;
341
342	point_type const& front = range::front(*it);
343	point_type const& back = range::back(*it);
344
345	// is closed_ring - no boundary
346	if ( detail::equals::equals_point_point(front, back) )
347	continue;
348
349	// is point on boundary
350	if ( detail::equals::equals_point_point(point, front)
351	\|\| detail::equals::equals_point_point(point, back) )
352	{
353	++boundaries;
354	}
355	}
356
357	// if the number of boundaries is odd, the point is on the boundary
358	return boundaries % 2 ? 0 : 1;
359	}
360	};
361
362	template <typename Geometry>
363	struct point_in_geometry<Geometry, multi_polygon_tag>
364	{
365	template <typename Point, typename Strategy> static inline
366	int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
367	{
368	// For invalid multipolygons
369	//int res = -1; // outside
370
371	typedef typename boost::range_value<Geometry>::type polygon_type;
372	typedef typename boost::range_const_iterator<Geometry>::type iterator;
373	for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it )
374	{
375	int pip = point_in_geometry<polygon_type>::apply(point, *it, strategy);
376
377	// inside or on the boundary
378	if ( pip >= 0 )
379	return pip;
380
381	// For invalid multi-polygons
382	//if ( 1 == pip ) // inside polygon
383	// return 1;
384	//else if ( res < pip ) // point must be inside at least one polygon
385	// res = pip;
386	}
387
388	return -1; // for valid multipolygons
389	//return res; // for invalid multipolygons
390	}
391	};
392
393	}} // namespace detail_dispatch::within
394
395	namespace detail { namespace within {
396
397	// 1 - in the interior
398	// 0 - in the boundry
399	// -1 - in the exterior
400	template <typename Point, typename Geometry, typename Strategy>
401	inline int point_in_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
402	{
403	concepts::within::check
404	<
405	typename tag<Point>::type,
406	typename tag<Geometry>::type,
407	typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
408	Strategy
409	>();
410
411	return detail_dispatch::within::point_in_geometry<Geometry>::apply(point, geometry, strategy);
412	}
413
414	template <typename Point, typename Geometry>
415	inline int point_in_geometry(Point const& point, Geometry const& geometry)
416	{
417	typedef typename point_type<Point>::type point_type1;
418	typedef typename point_type<Geometry>::type point_type2;
419
420	typedef typename strategy::within::services::default_strategy
421	<
422	typename tag<Point>::type,
423	typename tag<Geometry>::type,
424	typename tag<Point>::type,
425	typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
426	typename tag_cast
427	<
428	typename cs_tag<point_type1>::type, spherical_tag
429	>::type,
430	typename tag_cast
431	<
432	typename cs_tag<point_type2>::type, spherical_tag
433	>::type,
434	Point,
435	Geometry
436	>::type strategy_type;
437
438	typedef typename strategy::covered_by::services::default_strategy
439	<
440	typename tag<Point>::type,
441	typename tag<Geometry>::type,
442	typename tag<Point>::type,
443	typename tag_cast<typename tag<Geometry>::type, areal_tag>::type,
444	typename tag_cast
445	<
446	typename cs_tag<point_type1>::type, spherical_tag
447	>::type,
448	typename tag_cast
449	<
450	typename cs_tag<point_type2>::type, spherical_tag
451	>::type,
452	Point,
453	Geometry
454	>::type strategy_type2;
455
456	static const bool same_strategies = boost::is_same<strategy_type, strategy_type2>::value;
457	BOOST_MPL_ASSERT_MSG((same_strategies),
458	DEFAULT_WITHIN_AND_COVERED_BY_STRATEGIES_NOT_COMPATIBLE,
459	(strategy_type, strategy_type2));
460
461	return point_in_geometry(point, geometry, strategy_type());
462	}
463
464	}} // namespace detail::within
465	#endif // DOXYGEN_NO_DETAIL
466
467	}} // namespace boost::geometry
468
469	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP