]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. | |
6 | // Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland. | |
7 | ||
92f5a8d4 TL |
8 | // This file was modified by Oracle on 2014, 2015, 2016, 2017, 2018, 2019. |
9 | // Modifications copyright (c) 2014-2019 Oracle and/or its affiliates. | |
b32b8144 FG |
10 | |
11 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
12 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
13 | ||
14 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
15 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
16 | ||
17 | // Use, modification and distribution is subject to the Boost Software License, | |
18 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
19 | // http://www.boost.org/LICENSE_1_0.txt) | |
20 | ||
21 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP | |
22 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP | |
23 | ||
24 | ||
25 | #include <cstddef> | |
26 | #include <vector> | |
27 | ||
28 | #include <boost/range.hpp> | |
29 | #include <boost/type_traits/is_base_of.hpp> | |
30 | ||
31 | #include <boost/geometry/core/access.hpp> | |
32 | #include <boost/geometry/core/tags.hpp> | |
33 | ||
34 | #include <boost/geometry/algorithms/detail/equals/point_point.hpp> | |
35 | ||
36 | // For trivial checks | |
37 | #include <boost/geometry/algorithms/area.hpp> | |
38 | #include <boost/geometry/algorithms/length.hpp> | |
39 | #include <boost/geometry/util/math.hpp> | |
40 | #include <boost/geometry/util/select_coordinate_type.hpp> | |
41 | #include <boost/geometry/util/select_most_precise.hpp> | |
42 | ||
43 | #include <boost/geometry/algorithms/detail/equals/collect_vectors.hpp> | |
44 | #include <boost/geometry/algorithms/detail/equals/interface.hpp> | |
45 | #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp> | |
46 | #include <boost/geometry/algorithms/relate.hpp> | |
47 | ||
48 | #include <boost/geometry/views/detail/indexed_point_view.hpp> | |
49 | ||
50 | ||
51 | namespace boost { namespace geometry | |
52 | { | |
53 | ||
54 | #ifndef DOXYGEN_NO_DETAIL | |
55 | namespace detail { namespace equals | |
56 | { | |
57 | ||
58 | ||
59 | template | |
60 | < | |
61 | std::size_t Dimension, | |
62 | std::size_t DimensionCount | |
63 | > | |
64 | struct point_point | |
65 | { | |
66 | template <typename Point1, typename Point2, typename Strategy> | |
92f5a8d4 | 67 | static inline bool apply(Point1 const& point1, Point2 const& point2, Strategy const& ) |
b32b8144 | 68 | { |
92f5a8d4 | 69 | return Strategy::apply(point1, point2); |
b32b8144 FG |
70 | } |
71 | }; | |
72 | ||
73 | ||
74 | template | |
75 | < | |
76 | std::size_t Dimension, | |
77 | std::size_t DimensionCount | |
78 | > | |
79 | struct box_box | |
80 | { | |
81 | template <typename Box1, typename Box2, typename Strategy> | |
82 | static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy) | |
83 | { | |
84 | if (!geometry::math::equals(get<min_corner, Dimension>(box1), get<min_corner, Dimension>(box2)) | |
85 | || !geometry::math::equals(get<max_corner, Dimension>(box1), get<max_corner, Dimension>(box2))) | |
86 | { | |
87 | return false; | |
88 | } | |
89 | return box_box<Dimension + 1, DimensionCount>::apply(box1, box2, strategy); | |
90 | } | |
91 | }; | |
92 | ||
93 | template <std::size_t DimensionCount> | |
94 | struct box_box<DimensionCount, DimensionCount> | |
95 | { | |
96 | template <typename Box1, typename Box2, typename Strategy> | |
97 | static inline bool apply(Box1 const& , Box2 const& , Strategy const& ) | |
98 | { | |
99 | return true; | |
100 | } | |
101 | }; | |
102 | ||
103 | ||
104 | struct segment_segment | |
105 | { | |
106 | template <typename Segment1, typename Segment2, typename Strategy> | |
92f5a8d4 TL |
107 | static inline bool apply(Segment1 const& segment1, Segment2 const& segment2, |
108 | Strategy const& strategy) | |
b32b8144 | 109 | { |
92f5a8d4 TL |
110 | typename Strategy::point_in_point_strategy_type const& |
111 | pt_pt_strategy = strategy.get_point_in_point_strategy(); | |
112 | ||
b32b8144 FG |
113 | return equals::equals_point_point( |
114 | indexed_point_view<Segment1 const, 0>(segment1), | |
92f5a8d4 TL |
115 | indexed_point_view<Segment2 const, 0>(segment2), |
116 | pt_pt_strategy) | |
b32b8144 FG |
117 | ? equals::equals_point_point( |
118 | indexed_point_view<Segment1 const, 1>(segment1), | |
92f5a8d4 TL |
119 | indexed_point_view<Segment2 const, 1>(segment2), |
120 | pt_pt_strategy) | |
b32b8144 FG |
121 | : ( equals::equals_point_point( |
122 | indexed_point_view<Segment1 const, 0>(segment1), | |
92f5a8d4 TL |
123 | indexed_point_view<Segment2 const, 1>(segment2), |
124 | pt_pt_strategy) | |
b32b8144 FG |
125 | && equals::equals_point_point( |
126 | indexed_point_view<Segment1 const, 1>(segment1), | |
92f5a8d4 TL |
127 | indexed_point_view<Segment2 const, 0>(segment2), |
128 | pt_pt_strategy) | |
b32b8144 FG |
129 | ); |
130 | } | |
131 | }; | |
132 | ||
133 | ||
134 | struct area_check | |
135 | { | |
136 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
137 | static inline bool apply(Geometry1 const& geometry1, | |
138 | Geometry2 const& geometry2, | |
139 | Strategy const& strategy) | |
140 | { | |
141 | return geometry::math::equals( | |
142 | geometry::area(geometry1, | |
143 | strategy.template get_area_strategy<Geometry1>()), | |
144 | geometry::area(geometry2, | |
145 | strategy.template get_area_strategy<Geometry2>())); | |
146 | } | |
147 | }; | |
148 | ||
149 | ||
150 | struct length_check | |
151 | { | |
152 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
153 | static inline bool apply(Geometry1 const& geometry1, | |
154 | Geometry2 const& geometry2, | |
155 | Strategy const& strategy) | |
156 | { | |
157 | return geometry::math::equals( | |
158 | geometry::length(geometry1, | |
159 | strategy.template get_distance_strategy<Geometry1>()), | |
160 | geometry::length(geometry2, | |
161 | strategy.template get_distance_strategy<Geometry2>())); | |
162 | } | |
163 | }; | |
164 | ||
165 | ||
166 | template <typename Geometry1, typename Geometry2, typename IntersectionStrategy> | |
167 | struct collected_vector | |
168 | { | |
169 | typedef typename geometry::select_most_precise | |
170 | < | |
171 | typename select_coordinate_type | |
172 | < | |
173 | Geometry1, Geometry2 | |
174 | >::type, | |
175 | double | |
176 | >::type calculation_type; | |
177 | ||
178 | typedef geometry::collected_vector | |
179 | < | |
180 | calculation_type, | |
181 | Geometry1, | |
182 | typename IntersectionStrategy::side_strategy_type | |
183 | > type; | |
184 | }; | |
185 | ||
186 | template <typename TrivialCheck> | |
187 | struct equals_by_collection | |
188 | { | |
189 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
190 | static inline bool apply(Geometry1 const& geometry1, | |
191 | Geometry2 const& geometry2, | |
192 | Strategy const& strategy) | |
193 | { | |
194 | if (! TrivialCheck::apply(geometry1, geometry2, strategy)) | |
195 | { | |
196 | return false; | |
197 | } | |
198 | ||
199 | typedef typename collected_vector | |
200 | < | |
201 | Geometry1, Geometry2, Strategy | |
202 | >::type collected_vector_type; | |
203 | ||
204 | std::vector<collected_vector_type> c1, c2; | |
205 | ||
206 | geometry::collect_vectors(c1, geometry1); | |
207 | geometry::collect_vectors(c2, geometry2); | |
208 | ||
209 | if (boost::size(c1) != boost::size(c2)) | |
210 | { | |
211 | return false; | |
212 | } | |
213 | ||
214 | std::sort(c1.begin(), c1.end()); | |
215 | std::sort(c2.begin(), c2.end()); | |
216 | ||
217 | // Just check if these vectors are equal. | |
218 | return std::equal(c1.begin(), c1.end(), c2.begin()); | |
219 | } | |
220 | }; | |
221 | ||
222 | template<typename Geometry1, typename Geometry2> | |
223 | struct equals_by_relate | |
224 | : detail::relate::relate_impl | |
225 | < | |
226 | detail::de9im::static_mask_equals_type, | |
227 | Geometry1, | |
228 | Geometry2 | |
229 | > | |
230 | {}; | |
231 | ||
232 | // If collect_vectors which is a SideStrategy-dispatched optimization | |
233 | // is implemented in a way consistent with the Intersection/Side Strategy | |
234 | // then collect_vectors is used, otherwise relate is used. | |
235 | // NOTE: the result could be conceptually different for invalid | |
236 | // geometries in different coordinate systems because collect_vectors | |
237 | // and relate treat invalid geometries differently. | |
238 | template<typename TrivialCheck> | |
239 | struct equals_by_collection_or_relate | |
240 | { | |
241 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
242 | static inline bool apply(Geometry1 const& geometry1, | |
243 | Geometry2 const& geometry2, | |
244 | Strategy const& strategy) | |
245 | { | |
246 | typedef typename boost::is_base_of | |
247 | < | |
248 | nyi::not_implemented_tag, | |
249 | typename collected_vector | |
250 | < | |
251 | Geometry1, Geometry2, Strategy | |
252 | >::type | |
253 | >::type enable_relate_type; | |
254 | ||
255 | return apply(geometry1, geometry2, strategy, enable_relate_type()); | |
256 | } | |
257 | ||
258 | private: | |
259 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
260 | static inline bool apply(Geometry1 const& geometry1, | |
261 | Geometry2 const& geometry2, | |
262 | Strategy const& strategy, | |
263 | boost::false_type /*enable_relate*/) | |
264 | { | |
265 | return equals_by_collection<TrivialCheck>::apply(geometry1, geometry2, strategy); | |
266 | } | |
267 | ||
268 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
269 | static inline bool apply(Geometry1 const& geometry1, | |
270 | Geometry2 const& geometry2, | |
271 | Strategy const& strategy, | |
272 | boost::true_type /*enable_relate*/) | |
273 | { | |
274 | return equals_by_relate<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy); | |
275 | } | |
276 | }; | |
277 | ||
92f5a8d4 TL |
278 | struct equals_always_false |
279 | { | |
280 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
281 | static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const& ) | |
282 | { | |
283 | return false; | |
284 | } | |
285 | }; | |
286 | ||
b32b8144 FG |
287 | |
288 | }} // namespace detail::equals | |
289 | #endif // DOXYGEN_NO_DETAIL | |
290 | ||
291 | ||
292 | #ifndef DOXYGEN_NO_DISPATCH | |
293 | namespace dispatch | |
294 | { | |
295 | ||
296 | template <typename P1, typename P2, std::size_t DimensionCount, bool Reverse> | |
92f5a8d4 | 297 | struct equals<P1, P2, point_tag, point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse> |
b32b8144 FG |
298 | : detail::equals::point_point<0, DimensionCount> |
299 | {}; | |
300 | ||
301 | template <typename MultiPoint1, typename MultiPoint2, std::size_t DimensionCount, bool Reverse> | |
92f5a8d4 | 302 | struct equals<MultiPoint1, MultiPoint2, multi_point_tag, multi_point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse> |
b32b8144 FG |
303 | : detail::equals::equals_by_relate<MultiPoint1, MultiPoint2> |
304 | {}; | |
305 | ||
306 | template <typename MultiPoint, typename Point, std::size_t DimensionCount, bool Reverse> | |
92f5a8d4 | 307 | struct equals<Point, MultiPoint, point_tag, multi_point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse> |
b32b8144 FG |
308 | : detail::equals::equals_by_relate<Point, MultiPoint> |
309 | {}; | |
310 | ||
311 | template <typename Box1, typename Box2, std::size_t DimensionCount, bool Reverse> | |
92f5a8d4 | 312 | struct equals<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, DimensionCount, Reverse> |
b32b8144 FG |
313 | : detail::equals::box_box<0, DimensionCount> |
314 | {}; | |
315 | ||
316 | ||
317 | template <typename Ring1, typename Ring2, bool Reverse> | |
92f5a8d4 | 318 | struct equals<Ring1, Ring2, ring_tag, ring_tag, areal_tag, areal_tag, 2, Reverse> |
b32b8144 FG |
319 | : detail::equals::equals_by_collection_or_relate<detail::equals::area_check> |
320 | {}; | |
321 | ||
322 | ||
323 | template <typename Polygon1, typename Polygon2, bool Reverse> | |
92f5a8d4 | 324 | struct equals<Polygon1, Polygon2, polygon_tag, polygon_tag, areal_tag, areal_tag, 2, Reverse> |
b32b8144 FG |
325 | : detail::equals::equals_by_collection_or_relate<detail::equals::area_check> |
326 | {}; | |
327 | ||
328 | ||
329 | template <typename Polygon, typename Ring, bool Reverse> | |
92f5a8d4 | 330 | struct equals<Polygon, Ring, polygon_tag, ring_tag, areal_tag, areal_tag, 2, Reverse> |
b32b8144 FG |
331 | : detail::equals::equals_by_collection_or_relate<detail::equals::area_check> |
332 | {}; | |
333 | ||
334 | ||
335 | template <typename Ring, typename Box, bool Reverse> | |
92f5a8d4 | 336 | struct equals<Ring, Box, ring_tag, box_tag, areal_tag, areal_tag, 2, Reverse> |
b32b8144 FG |
337 | : detail::equals::equals_by_collection<detail::equals::area_check> |
338 | {}; | |
339 | ||
340 | ||
341 | template <typename Polygon, typename Box, bool Reverse> | |
92f5a8d4 | 342 | struct equals<Polygon, Box, polygon_tag, box_tag, areal_tag, areal_tag, 2, Reverse> |
b32b8144 FG |
343 | : detail::equals::equals_by_collection<detail::equals::area_check> |
344 | {}; | |
345 | ||
346 | template <typename Segment1, typename Segment2, std::size_t DimensionCount, bool Reverse> | |
92f5a8d4 | 347 | struct equals<Segment1, Segment2, segment_tag, segment_tag, linear_tag, linear_tag, DimensionCount, Reverse> |
b32b8144 FG |
348 | : detail::equals::segment_segment |
349 | {}; | |
350 | ||
351 | template <typename LineString1, typename LineString2, bool Reverse> | |
92f5a8d4 | 352 | struct equals<LineString1, LineString2, linestring_tag, linestring_tag, linear_tag, linear_tag, 2, Reverse> |
b32b8144 FG |
353 | : detail::equals::equals_by_relate<LineString1, LineString2> |
354 | {}; | |
355 | ||
356 | template <typename LineString, typename MultiLineString, bool Reverse> | |
92f5a8d4 | 357 | struct equals<LineString, MultiLineString, linestring_tag, multi_linestring_tag, linear_tag, linear_tag, 2, Reverse> |
b32b8144 FG |
358 | : detail::equals::equals_by_relate<LineString, MultiLineString> |
359 | {}; | |
360 | ||
361 | template <typename MultiLineString1, typename MultiLineString2, bool Reverse> | |
92f5a8d4 | 362 | struct equals<MultiLineString1, MultiLineString2, multi_linestring_tag, multi_linestring_tag, linear_tag, linear_tag, 2, Reverse> |
b32b8144 FG |
363 | : detail::equals::equals_by_relate<MultiLineString1, MultiLineString2> |
364 | {}; | |
365 | ||
92f5a8d4 TL |
366 | template <typename LineString, typename Segment, bool Reverse> |
367 | struct equals<LineString, Segment, linestring_tag, segment_tag, linear_tag, linear_tag, 2, Reverse> | |
368 | : detail::equals::equals_by_relate<LineString, Segment> | |
369 | {}; | |
370 | ||
371 | template <typename MultiLineString, typename Segment, bool Reverse> | |
372 | struct equals<MultiLineString, Segment, multi_linestring_tag, segment_tag, linear_tag, linear_tag, 2, Reverse> | |
373 | : detail::equals::equals_by_relate<MultiLineString, Segment> | |
374 | {}; | |
375 | ||
b32b8144 FG |
376 | |
377 | template <typename MultiPolygon1, typename MultiPolygon2, bool Reverse> | |
378 | struct equals | |
379 | < | |
380 | MultiPolygon1, MultiPolygon2, | |
381 | multi_polygon_tag, multi_polygon_tag, | |
92f5a8d4 | 382 | areal_tag, areal_tag, |
b32b8144 FG |
383 | 2, |
384 | Reverse | |
385 | > | |
386 | : detail::equals::equals_by_collection_or_relate<detail::equals::area_check> | |
387 | {}; | |
388 | ||
389 | ||
390 | template <typename Polygon, typename MultiPolygon, bool Reverse> | |
391 | struct equals | |
392 | < | |
393 | Polygon, MultiPolygon, | |
394 | polygon_tag, multi_polygon_tag, | |
92f5a8d4 | 395 | areal_tag, areal_tag, |
b32b8144 FG |
396 | 2, |
397 | Reverse | |
398 | > | |
399 | : detail::equals::equals_by_collection_or_relate<detail::equals::area_check> | |
400 | {}; | |
401 | ||
402 | template <typename MultiPolygon, typename Ring, bool Reverse> | |
403 | struct equals | |
404 | < | |
405 | MultiPolygon, Ring, | |
406 | multi_polygon_tag, ring_tag, | |
92f5a8d4 | 407 | areal_tag, areal_tag, |
b32b8144 FG |
408 | 2, |
409 | Reverse | |
410 | > | |
411 | : detail::equals::equals_by_collection_or_relate<detail::equals::area_check> | |
412 | {}; | |
413 | ||
414 | ||
92f5a8d4 TL |
415 | // NOTE: degenerated linear geometries, e.g. segment or linestring containing |
416 | // 2 equal points, are considered to be invalid. Though theoretically | |
417 | // degenerated segments and linestrings could be treated as points and | |
418 | // multi-linestrings as multi-points. | |
419 | // This reasoning could also be applied to boxes. | |
420 | ||
421 | template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount> | |
422 | struct equals<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, linear_tag, DimensionCount, false> | |
423 | : detail::equals::equals_always_false | |
424 | {}; | |
425 | ||
426 | template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount> | |
427 | struct equals<Geometry1, Geometry2, Tag1, Tag2, linear_tag, pointlike_tag, DimensionCount, false> | |
428 | : detail::equals::equals_always_false | |
429 | {}; | |
430 | ||
431 | template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount> | |
432 | struct equals<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, areal_tag, DimensionCount, false> | |
433 | : detail::equals::equals_always_false | |
434 | {}; | |
435 | ||
436 | template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount> | |
437 | struct equals<Geometry1, Geometry2, Tag1, Tag2, areal_tag, pointlike_tag, DimensionCount, false> | |
438 | : detail::equals::equals_always_false | |
439 | {}; | |
440 | ||
441 | template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount> | |
442 | struct equals<Geometry1, Geometry2, Tag1, Tag2, linear_tag, areal_tag, DimensionCount, false> | |
443 | : detail::equals::equals_always_false | |
444 | {}; | |
445 | ||
446 | template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount> | |
447 | struct equals<Geometry1, Geometry2, Tag1, Tag2, areal_tag, linear_tag, DimensionCount, false> | |
448 | : detail::equals::equals_always_false | |
449 | {}; | |
450 | ||
b32b8144 FG |
451 | } // namespace dispatch |
452 | #endif // DOXYGEN_NO_DISPATCH | |
453 | ||
454 | ||
455 | }} // namespace boost::geometry | |
456 | ||
457 | ||
458 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP | |
459 |