boost/geometry/algorithms/detail/equals/collect_vectors.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   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 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
   9 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  10
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
  17
  18
  19 #include <boost/numeric/conversion/cast.hpp>
  20 #include <boost/range.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  23
  24 #include <boost/geometry/core/cs.hpp>
  25 #include <boost/geometry/core/interior_rings.hpp>
  26 #include <boost/geometry/core/tags.hpp>
  27
  28 #include <boost/geometry/geometries/concepts/check.hpp>
  29
  30 #include <boost/geometry/util/math.hpp>
  31
  32
  33
  34 namespace boost { namespace geometry
  35 {
  36
  37 // TODO: if Boost.LA of Emil Dotchevski is accepted, adapt this
  38 template <typename T>
  39 struct collected_vector
  40 {
  41     typedef T type;
  42
  43     inline collected_vector()
  44     {}
  45
  46     inline collected_vector(T const& px, T const& py,
  47             T const& pdx, T const& pdy)
  48         : x(px)
  49         , y(py)
  50         , dx(pdx)
  51         , dy(pdy)
  52         , dx_0(T())
  53         , dy_0(T())
  54     {}
  55
  56     T x, y;
  57     T dx, dy;
  58     T dx_0, dy_0;
  59
  60     // For sorting
  61     inline bool operator<(collected_vector<T> const& other) const
  62     {
  63         if (math::equals(x, other.x))
  64         {
  65             if (math::equals(y, other.y))
  66             {
  67                 if (math::equals(dx, other.dx))
  68                 {
  69                     return dy < other.dy;
  70                 }
  71                 return dx < other.dx;
  72             }
  73             return y < other.y;
  74         }
  75         return x < other.x;
  76     }
  77
  78     inline bool same_direction(collected_vector<T> const& other) const
  79     {
  80         // For high precision arithmetic, we have to be
  81         // more relaxed then using ==
  82         // Because 2/sqrt( (0,0)<->(2,2) ) == 1/sqrt( (0,0)<->(1,1) )
  83         // is not always true (at least, it is not for ttmath)
  84         return math::equals_with_epsilon(dx, other.dx)
  85             && math::equals_with_epsilon(dy, other.dy);
  86     }
  87
  88     // For std::equals
  89     inline bool operator==(collected_vector<T> const& other) const
  90     {
  91         return math::equals(x, other.x)
  92             && math::equals(y, other.y)
  93             && same_direction(other);
  94     }
  95 };
  96
  97
  98 #ifndef DOXYGEN_NO_DETAIL
  99 namespace detail { namespace collect_vectors
 100 {
 101
 102
 103 template <typename Range, typename Collection>
 104 struct range_collect_vectors
 105 {
 106     typedef typename boost::range_value<Collection>::type item_type;
 107     typedef typename item_type::type calculation_type;
 108
 109     static inline void apply(Collection& collection, Range const& range)
 110     {
 111         if (boost::size(range) < 2)
 112         {
 113             return;
 114         }
 115
 116         typedef typename boost::range_size<Collection>::type collection_size_t;
 117         collection_size_t c_old_size = boost::size(collection);
 118
 119         typedef typename boost::range_iterator<Range const>::type iterator;
 120
 121         bool first = true;
 122         iterator it = boost::begin(range);
 123
 124         for (iterator prev = it++;
 125             it != boost::end(range);
 126             prev = it++)
 127         {
 128             typename boost::range_value<Collection>::type v;
 129
 130             v.x = get<0>(*prev);
 131             v.y = get<1>(*prev);
 132             v.dx = get<0>(*it) - v.x;
 133             v.dy = get<1>(*it) - v.y;
 134             v.dx_0 = v.dx;
 135             v.dy_0 = v.dy;
 136
 137             // Normalize the vector -> this results in points+direction
 138             // and is comparible between geometries
 139             calculation_type magnitude = math::sqrt(
 140                 boost::numeric_cast<calculation_type>(v.dx * v.dx + v.dy * v.dy));
 141
 142             // Avoid non-duplicate points (AND division by zero)
 143             if (magnitude > 0)
 144             {
 145                 v.dx /= magnitude;
 146                 v.dy /= magnitude;
 147
 148                 // Avoid non-direction changing points
 149                 if (first || ! v.same_direction(collection.back()))
 150                 {
 151                     collection.push_back(v);
 152                 }
 153                 first = false;
 154             }
 155         }
 156
 157         // If first one has same direction as last one, remove first one
 158         collection_size_t collected_count = boost::size(collection) - c_old_size;
 159         if ( collected_count > 1 )
 160         {
 161             typedef typename boost::range_iterator<Collection>::type c_iterator;
 162             c_iterator first = collection.begin() + c_old_size;
 163
 164             if ( first->same_direction(collection.back()) )
 165             {
 166                 //collection.erase(first);
 167                 // O(1) instead of O(N)
 168                 *first = collection.back();
 169                 collection.pop_back();
 170             }
 171         }
 172     }
 173 };
 174
 175
 176 template <typename Box, typename Collection>
 177 struct box_collect_vectors
 178 {
 179     // Calculate on coordinate type, but if it is integer,
 180     // then use double
 181     typedef typename boost::range_value<Collection>::type item_type;
 182     typedef typename item_type::type calculation_type;
 183
 184     static inline void apply(Collection& collection, Box const& box)
 185     {
 186         typename point_type<Box>::type lower_left, lower_right,
 187                 upper_left, upper_right;
 188         geometry::detail::assign_box_corners(box, lower_left, lower_right,
 189                 upper_left, upper_right);
 190
 191         typedef typename boost::range_value<Collection>::type item;
 192
 193         collection.push_back(item(get<0>(lower_left), get<1>(lower_left), 0, 1));
 194         collection.push_back(item(get<0>(upper_left), get<1>(upper_left), 1, 0));
 195         collection.push_back(item(get<0>(upper_right), get<1>(upper_right), 0, -1));
 196         collection.push_back(item(get<0>(lower_right), get<1>(lower_right), -1, 0));
 197     }
 198 };
 199
 200
 201 template <typename Polygon, typename Collection>
 202 struct polygon_collect_vectors
 203 {
 204     static inline void apply(Collection& collection, Polygon const& polygon)
 205     {
 206         typedef typename geometry::ring_type<Polygon>::type ring_type;
 207
 208         typedef range_collect_vectors<ring_type, Collection> per_range;
 209         per_range::apply(collection, exterior_ring(polygon));
 210
 211         typename interior_return_type<Polygon const>::type
 212             rings = interior_rings(polygon);
 213         for (typename detail::interior_iterator<Polygon const>::type
 214                 it = boost::begin(rings); it != boost::end(rings); ++it)
 215         {
 216             per_range::apply(collection, *it);
 217         }
 218     }
 219 };
 220
 221
 222 template <typename MultiGeometry, typename Collection, typename SinglePolicy>
 223 struct multi_collect_vectors
 224 {
 225     static inline void apply(Collection& collection, MultiGeometry const& multi)
 226     {
 227         for (typename boost::range_iterator<MultiGeometry const>::type
 228                 it = boost::begin(multi);
 229             it != boost::end(multi);
 230             ++it)
 231         {
 232             SinglePolicy::apply(collection, *it);
 233         }
 234     }
 235 };
 236
 237
 238 }} // namespace detail::collect_vectors
 239 #endif // DOXYGEN_NO_DETAIL
 240
 241
 242
 243 #ifndef DOXYGEN_NO_DISPATCH
 244 namespace dispatch
 245 {
 246
 247
 248 template
 249 <
 250     typename Tag,
 251     typename Collection,
 252     typename Geometry
 253 >
 254 struct collect_vectors
 255 {
 256     static inline void apply(Collection&, Geometry const&)
 257     {}
 258 };
 259
 260
 261 template <typename Collection, typename Box>
 262 struct collect_vectors<box_tag, Collection, Box>
 263     : detail::collect_vectors::box_collect_vectors<Box, Collection>
 264 {};
 265
 266
 267
 268 template <typename Collection, typename Ring>
 269 struct collect_vectors<ring_tag, Collection, Ring>
 270     : detail::collect_vectors::range_collect_vectors<Ring, Collection>
 271 {};
 272
 273
 274 template <typename Collection, typename LineString>
 275 struct collect_vectors<linestring_tag, Collection, LineString>
 276     : detail::collect_vectors::range_collect_vectors<LineString, Collection>
 277 {};
 278
 279
 280 template <typename Collection, typename Polygon>
 281 struct collect_vectors<polygon_tag, Collection, Polygon>
 282     : detail::collect_vectors::polygon_collect_vectors<Polygon, Collection>
 283 {};
 284
 285
 286 template <typename Collection, typename MultiPolygon>
 287 struct collect_vectors<multi_polygon_tag, Collection, MultiPolygon>
 288     : detail::collect_vectors::multi_collect_vectors
 289         <
 290             MultiPolygon,
 291             Collection,
 292             detail::collect_vectors::polygon_collect_vectors
 293             <
 294                 typename boost::range_value<MultiPolygon>::type,
 295                 Collection
 296             >
 297         >
 298 {};
 299
 300
 301
 302 } // namespace dispatch
 303 #endif
 304
 305
 306 /*!
 307     \ingroup collect_vectors
 308     \tparam Collection Collection type, should be e.g. std::vector<>
 309     \tparam Geometry geometry type
 310     \param collection the collection of vectors
 311     \param geometry the geometry to make collect_vectors
 312 */
 313 template <typename Collection, typename Geometry>
 314 inline void collect_vectors(Collection& collection, Geometry const& geometry)
 315 {
 316     concept::check<Geometry const>();
 317
 318     dispatch::collect_vectors
 319         <
 320             typename tag<Geometry>::type,
 321             Collection,
 322             Geometry
 323         >::apply(collection, geometry);
 324 }
 325
 326
 327 }} // namespace boost::geometry
 328
 329
 330 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP