1 // Boost.Geometry
2
3 // Copyright (c) 2017 Oracle and/or its affiliates.
4 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
5
6 // Use, modification and distribution is subject to the Boost Software License,
7 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9
10
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RANGE_IN_GEOMETRY_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RANGE_IN_GEOMETRY_HPP
13
14
15 #include <boost/geometry/algorithms/covered_by.hpp>
16 #include <boost/geometry/core/access.hpp>
17 #include <boost/geometry/core/tags.hpp>
18 #include <boost/geometry/iterators/point_iterator.hpp>
19
20 #include <boost/range.hpp>
21
22
23 namespace boost { namespace geometry
24 {
25
26
27 #ifndef DOXYGEN_NO_DETAIL
28 namespace detail { namespace overlay
29 {
30
31
32 template
33 <
34 typename Geometry,
35 typename Tag = typename geometry::tag<Geometry>::type
36 >
37 struct points_range
38 {
39 typedef geometry::point_iterator<Geometry const> iterator_type;
40
points_rangeboost::geometry::detail::overlay::points_range41 explicit points_range(Geometry const& geometry)
42 : m_geometry(geometry)
43 {}
44
beginboost::geometry::detail::overlay::points_range45 iterator_type begin() const
46 {
47 return geometry::points_begin(m_geometry);
48 }
49
endboost::geometry::detail::overlay::points_range50 iterator_type end() const
51 {
52 return geometry::points_end(m_geometry);
53 }
54
55 Geometry const& m_geometry;
56 };
57 // Specialized because point_iterator doesn't support boxes
58 template <typename Box>
59 struct points_range<Box, box_tag>
60 {
61 typedef typename geometry::point_type<Box>::type point_type;
62 typedef const point_type * iterator_type;
63
points_rangeboost::geometry::detail::overlay::points_range64 explicit points_range(Box const& box)
65 {
66 detail::assign_box_corners(box,
67 m_corners[0], m_corners[1], m_corners[2], m_corners[3]);
68 }
69
beginboost::geometry::detail::overlay::points_range70 iterator_type begin() const
71 {
72 return m_corners;
73 }
74
endboost::geometry::detail::overlay::points_range75 iterator_type end() const
76 {
77 return m_corners + 4;
78 }
79
80 point_type m_corners[4];
81 };
82
83 template
84 <
85 typename Geometry,
86 typename Tag = typename geometry::tag<Geometry>::type
87 >
88 struct point_in_geometry_helper
89 {
90 template <typename Point, typename Strategy>
applyboost::geometry::detail::overlay::point_in_geometry_helper91 static inline int apply(Point const& point, Geometry const& geometry,
92 Strategy const& strategy)
93 {
94 return detail::within::point_in_geometry(point, geometry, strategy);
95 }
96 };
97 // Specialized because point_in_geometry doesn't support Boxes
98 template <typename Box>
99 struct point_in_geometry_helper<Box, box_tag>
100 {
101 template <typename Point, typename Strategy>
applyboost::geometry::detail::overlay::point_in_geometry_helper102 static inline int apply(Point const& point, Box const& box,
103 Strategy const&)
104 {
105 return geometry::covered_by(point, box) ? 1 : -1;
106 }
107 };
108
109 // This function returns
110 // when it finds a point of geometry1 inside or outside geometry2
111 template <typename Geometry1, typename Geometry2, typename Strategy>
range_in_geometry(Geometry1 const & geometry1,Geometry2 const & geometry2,Strategy const & strategy,bool skip_first=false)112 static inline int range_in_geometry(Geometry1 const& geometry1,
113 Geometry2 const& geometry2,
114 Strategy const& strategy,
115 bool skip_first = false)
116 {
117 int result = 0;
118 points_range<Geometry1> points(geometry1);
119 typedef typename points_range<Geometry1>::iterator_type iterator_type;
120 iterator_type const end = points.end();
121 iterator_type it = points.begin();
122 if (it == end)
123 {
124 return result;
125 }
126 else if (skip_first)
127 {
128 ++it;
129 }
130
131 typename Strategy::template point_in_geometry_strategy
132 <
133 Geometry1, Geometry2
134 >::type const in_strategy
135 = strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>();
136
137 for ( ; it != end; ++it)
138 {
139 result = point_in_geometry_helper<Geometry2>::apply(*it, geometry2, in_strategy);
140 if (result != 0)
141 {
142 return result;
143 }
144 }
145 // all points contained entirely by the boundary
146 return result;
147 }
148
149 // This function returns if first_point1 is inside or outside geometry2 or
150 // when it finds a point of geometry1 inside or outside geometry2
151 template <typename Point1, typename Geometry1, typename Geometry2, typename Strategy>
range_in_geometry(Point1 const & first_point1,Geometry1 const & geometry1,Geometry2 const & geometry2,Strategy const & strategy)152 inline int range_in_geometry(Point1 const& first_point1,
153 Geometry1 const& geometry1,
154 Geometry2 const& geometry2,
155 Strategy const& strategy)
156 {
157 // check a point on border of geometry1 first
158 int result = point_in_geometry_helper<Geometry2>::apply(first_point1, geometry2,
159 strategy.template get_point_in_geometry_strategy<Point1, Geometry2>());
160 if (result == 0)
161 {
162 // if a point is on boundary of geometry2
163 // check points of geometry1 until point inside/outside is found
164 // NOTE: skip first point because it should be already tested above
165 result = range_in_geometry(geometry1, geometry2, strategy, true);
166 }
167 return result;
168 }
169
170
171 }} // namespace detail::overlay
172 #endif // DOXYGEN_NO_DETAIL
173
174
175 }} // namespace boost::geometry
176
177
178 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_RANGE_IN_GEOMETRY_HPP
179