[ceph.git] / ceph / src / boost / 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, 2017, 2018, 2019.
// Modifications copyright (c) 2013-2019, Oracle and/or its affiliates.

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

// 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)

#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/relate.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 {

template <typename Point1, typename Point2, typename Strategy>
inline bool equals_point_point(Point1 const& p1, Point2 const& p2, Strategy const& strategy)
{
    return equals::equals_point_point(p1, p2, strategy.get_equals_point_point_strategy());
}

// 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 strategy::point_in_geometry::services::default_strategy
        <
            Point, Geometry
        >::type strategy_type;

    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::within::equals_point_point(point, p0, strategy)
          || detail::within::equals_point_point(point, p1, strategy) )
            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::within::equals_point_point(range::front(linestring), range::back(linestring), strategy))
                return 1; // interior
            // else if the point is equal to the one of the terminal points
            else if (detail::within::equals_point_point(point, range::front(linestring), strategy)
                || detail::within::equals_point_point(point, range::back(linestring), strategy))
                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::within::equals_point_point(front, back, strategy) )
                continue;

            // is point on boundary
            if ( detail::within::equals_point_point(point, front, strategy)
              || detail::within::equals_point_point(point, back, strategy) )
            {
                ++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<Point, Geometry, 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 strategy::point_in_geometry::services::default_strategy
        <
            Point, Geometry
        >::type strategy_type;

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

template <typename Point, typename Geometry, typename Strategy>
inline bool within_point_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
{
    return point_in_geometry(point, geometry, strategy) > 0;
}

template <typename Point, typename Geometry>
inline bool within_point_geometry(Point const& point, Geometry const& geometry)
{
    return point_in_geometry(point, geometry) > 0;
}

template <typename Point, typename Geometry, typename Strategy>
inline bool covered_by_point_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
{
    return point_in_geometry(point, geometry, strategy) >= 0;
}

template <typename Point, typename Geometry>
inline bool covered_by_point_geometry(Point const& point, Geometry const& geometry)
{
    return point_in_geometry(point, geometry) >= 0;
}

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