1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
6 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
8 // This file was modified by Oracle on 2017.
9 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
20 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
21 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
24 #include <boost/numeric/conversion/cast.hpp>
26 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
27 #include <boost/geometry/algorithms/detail/normalize.hpp>
28 #include <boost/geometry/algorithms/not_implemented.hpp>
30 #include <boost/geometry/core/cs.hpp>
31 #include <boost/geometry/core/interior_rings.hpp>
32 #include <boost/geometry/core/tags.hpp>
34 #include <boost/geometry/formulas/spherical.hpp>
36 #include <boost/geometry/geometries/concepts/check.hpp>
38 #include <boost/geometry/util/math.hpp>
39 #include <boost/geometry/util/range.hpp>
41 #include <boost/geometry/views/detail/normalized_view.hpp>
43 #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp>
44 #include <boost/geometry/strategies/spherical/ssf.hpp>
47 namespace boost { namespace geometry
50 // TODO: dispatch only by SideStrategy instead of Geometry/CSTag?
52 // Since these vectors (though ray would be a better name) are used in the
53 // implementation of equals() for Areal geometries the internal representation
54 // should be consistent with the side strategy.
59 typename SideStrategy,
60 typename CSTag = typename cs_tag<Geometry>::type
62 struct collected_vector
63 : nyi::not_implemented_tag
66 // compatible with side_by_triangle cartesian strategy
67 template <typename T, typename Geometry, typename CT, typename CSTag>
68 struct collected_vector
70 T, Geometry, strategy::side::side_by_triangle<CT>, CSTag
75 inline collected_vector()
78 inline collected_vector(T const& px, T const& py,
79 T const& pdx, T const& pdy)
88 template <typename Point>
89 inline collected_vector(Point const& p1, Point const& p2)
100 T magnitude = math::sqrt(
101 boost::numeric_cast<T>(dx * dx + dy * dy));
103 // NOTE: shouldn't here math::equals() be called?
115 inline bool operator<(collected_vector const& other) const
117 if (math::equals(x, other.x))
119 if (math::equals(y, other.y))
121 if (math::equals(dx, other.dx))
123 return dy < other.dy;
125 return dx < other.dx;
132 inline bool next_is_collinear(collected_vector const& other) const
134 return same_direction(other);
138 inline bool operator==(collected_vector const& other) const
140 return math::equals(x, other.x)
141 && math::equals(y, other.y)
142 && same_direction(other);
146 inline bool same_direction(collected_vector const& other) const
148 // For high precision arithmetic, we have to be
149 // more relaxed then using ==
150 // Because 2/sqrt( (0,0)<->(2,2) ) == 1/sqrt( (0,0)<->(1,1) )
151 // is not always true (at least, it is not for ttmath)
152 return math::equals_with_epsilon(dx, other.dx)
153 && math::equals_with_epsilon(dy, other.dy);
161 // Compatible with spherical_side_formula which currently
162 // is the default spherical and geographical strategy
163 template <typename T, typename Geometry, typename CT, typename CSTag>
164 struct collected_vector
166 T, Geometry, strategy::side::spherical_side_formula<CT>, CSTag
171 typedef typename coordinate_system<Geometry>::type cs_type;
172 typedef model::point<T, 2, cs_type> point_type;
173 typedef model::point<T, 3, cs::cartesian> vector_type;
178 template <typename Point>
179 collected_vector(Point const& p1, Point const& p2)
180 : origin(get<0>(p1), get<1>(p1))
182 origin = detail::return_normalized<point_type>(origin);
184 using namespace geometry::formula;
185 prev = sph_to_cart3d<vector_type>(p1);
186 next = sph_to_cart3d<vector_type>(p2);
187 direction = cross_product(prev, next);
192 T magnitude_sqr = dot_product(direction, direction);
194 // NOTE: shouldn't here math::equals() be called?
195 if (magnitude_sqr > 0)
197 divide_value(direction, math::sqrt(magnitude_sqr));
204 bool operator<(collected_vector const& other) const
206 if (math::equals(get<0>(origin), get<0>(other.origin)))
208 if (math::equals(get<1>(origin), get<1>(other.origin)))
210 if (math::equals(get<0>(direction), get<0>(other.direction)))
212 if (math::equals(get<1>(direction), get<1>(other.direction)))
214 return get<2>(direction) < get<2>(other.direction);
216 return get<1>(direction) < get<1>(other.direction);
218 return get<0>(direction) < get<0>(other.direction);
220 return get<1>(origin) < get<1>(other.origin);
222 return get<0>(origin) < get<0>(other.origin);
225 // For consistency with side and intersection strategies used by relops
226 // IMPORTANT: this method should be called for previous vector
227 // and next vector should be passed as parameter
228 bool next_is_collinear(collected_vector const& other) const
230 return formula::sph_side_value(direction, other.next) == 0;
234 bool operator==(collected_vector const& other) const
236 return math::equals(get<0>(origin), get<0>(other.origin))
237 && math::equals(get<1>(origin), get<1>(other.origin))
238 && is_collinear(other);
242 // For consistency with side and intersection strategies used by relops
243 bool is_collinear(collected_vector const& other) const
245 return formula::sph_side_value(direction, other.prev) == 0
246 && formula::sph_side_value(direction, other.next) == 0;
249 /*bool same_direction(collected_vector const& other) const
251 return math::equals_with_epsilon(get<0>(direction), get<0>(other.direction))
252 && math::equals_with_epsilon(get<1>(direction), get<1>(other.direction))
253 && math::equals_with_epsilon(get<2>(direction), get<2>(other.direction));
256 point_type origin; // used for sorting and equality check
257 vector_type direction; // used for sorting, only in operator<
258 vector_type prev; // used for collinearity check, only in operator==
259 vector_type next; // used for collinearity check
262 // Specialization for spherical polar
263 template <typename T, typename Geometry, typename CT>
264 struct collected_vector
267 strategy::side::spherical_side_formula<CT>,
270 : public collected_vector
273 strategy::side::spherical_side_formula<CT>,
274 spherical_equatorial_tag
277 typedef collected_vector
280 strategy::side::spherical_side_formula<CT>,
281 spherical_equatorial_tag
284 collected_vector() {}
286 template <typename Point>
287 collected_vector(Point const& p1, Point const& p2)
288 : base_type(to_equatorial(p1), to_equatorial(p2))
292 template <typename Point>
293 Point polar_to_equatorial(Point const& p)
295 typedef typename coordinate_type<Point>::type coord_type;
297 typedef math::detail::constants_on_spheroid
300 typename coordinate_system<Point>::type::units
303 coord_type const pi_2 = constants::half_period() / 2;
306 set<1>(res, pi_2 - get<1>(p));
312 #ifndef DOXYGEN_NO_DETAIL
313 namespace detail { namespace collect_vectors
317 template <typename Range, typename Collection>
318 struct range_collect_vectors
320 typedef typename boost::range_value<Collection>::type item_type;
321 typedef typename item_type::type calculation_type;
323 static inline void apply(Collection& collection, Range const& range)
325 typedef geometry::detail::normalized_view
328 > normalized_range_type;
330 apply_impl(collection, normalized_range_type(range));
334 template <typename NormalizedRange>
335 static inline void apply_impl(Collection& collection, NormalizedRange const& range)
337 if (boost::size(range) < 2)
342 typedef typename boost::range_size<Collection>::type collection_size_t;
343 collection_size_t c_old_size = boost::size(collection);
345 typedef typename boost::range_iterator<NormalizedRange const>::type iterator;
347 bool is_first = true;
348 iterator it = boost::begin(range);
350 for (iterator prev = it++;
351 it != boost::end(range);
354 typename boost::range_value<Collection>::type v(*prev, *it);
356 // Normalize the vector -> this results in points+direction
357 // and is comparible between geometries
358 // Avoid non-duplicate points (AND division by zero)
361 // Avoid non-direction changing points
362 if (is_first || ! collection.back().next_is_collinear(v))
364 collection.push_back(v);
370 // If first one has same direction as last one, remove first one
371 collection_size_t collected_count = boost::size(collection) - c_old_size;
372 if ( collected_count > 1 )
374 typedef typename boost::range_iterator<Collection>::type c_iterator;
375 c_iterator first = range::pos(collection, c_old_size);
377 if (collection.back().next_is_collinear(*first) )
379 //collection.erase(first);
380 // O(1) instead of O(N)
381 *first = collection.back();
382 collection.pop_back();
389 // Default version (cartesian)
390 template <typename Box, typename Collection, typename CSTag = typename cs_tag<Box>::type>
391 struct box_collect_vectors
393 // Calculate on coordinate type, but if it is integer,
395 typedef typename boost::range_value<Collection>::type item_type;
396 typedef typename item_type::type calculation_type;
398 static inline void apply(Collection& collection, Box const& box)
400 typename point_type<Box>::type lower_left, lower_right,
401 upper_left, upper_right;
402 geometry::detail::assign_box_corners(box, lower_left, lower_right,
403 upper_left, upper_right);
405 typedef typename boost::range_value<Collection>::type item;
407 collection.push_back(item(get<0>(lower_left), get<1>(lower_left), 0, 1));
408 collection.push_back(item(get<0>(upper_left), get<1>(upper_left), 1, 0));
409 collection.push_back(item(get<0>(upper_right), get<1>(upper_right), 0, -1));
410 collection.push_back(item(get<0>(lower_right), get<1>(lower_right), -1, 0));
414 // NOTE: This is not fully correct because Box in spherical and geographic
415 // cordinate systems cannot be seen as Polygon
416 template <typename Box, typename Collection>
417 struct box_collect_vectors<Box, Collection, spherical_equatorial_tag>
419 static inline void apply(Collection& collection, Box const& box)
421 typename point_type<Box>::type lower_left, lower_right,
422 upper_left, upper_right;
423 geometry::detail::assign_box_corners(box, lower_left, lower_right,
424 upper_left, upper_right);
426 typedef typename boost::range_value<Collection>::type item;
428 collection.push_back(item(lower_left, upper_left));
429 collection.push_back(item(upper_left, upper_right));
430 collection.push_back(item(upper_right, lower_right));
431 collection.push_back(item(lower_right, lower_left));
435 template <typename Box, typename Collection>
436 struct box_collect_vectors<Box, Collection, spherical_polar_tag>
437 : box_collect_vectors<Box, Collection, spherical_equatorial_tag>
440 template <typename Box, typename Collection>
441 struct box_collect_vectors<Box, Collection, geographic_tag>
442 : box_collect_vectors<Box, Collection, spherical_equatorial_tag>
446 template <typename Polygon, typename Collection>
447 struct polygon_collect_vectors
449 static inline void apply(Collection& collection, Polygon const& polygon)
451 typedef typename geometry::ring_type<Polygon>::type ring_type;
453 typedef range_collect_vectors<ring_type, Collection> per_range;
454 per_range::apply(collection, exterior_ring(polygon));
456 typename interior_return_type<Polygon const>::type
457 rings = interior_rings(polygon);
458 for (typename detail::interior_iterator<Polygon const>::type
459 it = boost::begin(rings); it != boost::end(rings); ++it)
461 per_range::apply(collection, *it);
467 template <typename MultiGeometry, typename Collection, typename SinglePolicy>
468 struct multi_collect_vectors
470 static inline void apply(Collection& collection, MultiGeometry const& multi)
472 for (typename boost::range_iterator<MultiGeometry const>::type
473 it = boost::begin(multi);
474 it != boost::end(multi);
477 SinglePolicy::apply(collection, *it);
483 }} // namespace detail::collect_vectors
484 #endif // DOXYGEN_NO_DETAIL
488 #ifndef DOXYGEN_NO_DISPATCH
499 struct collect_vectors
501 static inline void apply(Collection&, Geometry const&)
506 template <typename Collection, typename Box>
507 struct collect_vectors<box_tag, Collection, Box>
508 : detail::collect_vectors::box_collect_vectors<Box, Collection>
513 template <typename Collection, typename Ring>
514 struct collect_vectors<ring_tag, Collection, Ring>
515 : detail::collect_vectors::range_collect_vectors<Ring, Collection>
519 template <typename Collection, typename LineString>
520 struct collect_vectors<linestring_tag, Collection, LineString>
521 : detail::collect_vectors::range_collect_vectors<LineString, Collection>
525 template <typename Collection, typename Polygon>
526 struct collect_vectors<polygon_tag, Collection, Polygon>
527 : detail::collect_vectors::polygon_collect_vectors<Polygon, Collection>
531 template <typename Collection, typename MultiPolygon>
532 struct collect_vectors<multi_polygon_tag, Collection, MultiPolygon>
533 : detail::collect_vectors::multi_collect_vectors
537 detail::collect_vectors::polygon_collect_vectors
539 typename boost::range_value<MultiPolygon>::type,
547 } // namespace dispatch
552 \ingroup collect_vectors
553 \tparam Collection Collection type, should be e.g. std::vector<>
554 \tparam Geometry geometry type
555 \param collection the collection of vectors
556 \param geometry the geometry to make collect_vectors
558 template <typename Collection, typename Geometry>
559 inline void collect_vectors(Collection& collection, Geometry const& geometry)
561 concepts::check<Geometry const>();
563 dispatch::collect_vectors
565 typename tag<Geometry>::type,
568 >::apply(collection, geometry);
572 }} // namespace boost::geometry
575 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP