boost/geometry/algorithms/detail/calculate_point_order.hpp

   1 // Boost.Geometry
   2
   3 // Copyright (c) 2019, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   6
   7 // Licensed under the Boost Software License version 1.0.
   8 // http://www.boost.org/users/license.html
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CALCULATE_POINT_ORDER_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CALCULATE_POINT_ORDER_HPP
  12
  13
  14 #include <vector>
  15
  16 #include <boost/mpl/assert.hpp>
  17
  18 #include <boost/geometry/algorithms/area.hpp>
  19 #include <boost/geometry/core/point_order.hpp>
  20 #include <boost/geometry/core/radian_access.hpp>
  21 #include <boost/geometry/strategies/geographic/point_order.hpp>
  22 #include <boost/geometry/util/math.hpp>
  23 #include <boost/geometry/util/range.hpp>
  24
  25
  26 namespace boost { namespace geometry
  27 {
  28
  29 namespace detail
  30 {
  31
  32 template <typename Iter, typename CalcT>
  33 struct clean_point
  34 {
  35     explicit clean_point(Iter const& iter)
  36         : m_iter(iter), m_azi(0), m_razi(0), m_azi_diff(0)
  37         , m_is_azi_valid(false), m_is_azi_diff_valid(false)
  38     {}
  39
  40     typename boost::iterators::iterator_reference<Iter>::type ref() const
  41     {
  42         return *m_iter;
  43     }
  44
  45     CalcT const& azimuth() const
  46     {
  47         return m_azi;
  48     }
  49
  50     CalcT const& reverse_azimuth() const
  51     {
  52         return m_razi;
  53     }
  54
  55     CalcT const& azimuth_difference() const
  56     {
  57         return m_azi_diff;
  58     }
  59
  60     void set_azimuths(CalcT const& azi, CalcT const& razi)
  61     {
  62         m_azi = azi;
  63         m_razi = razi;
  64         m_is_azi_valid = true;
  65     }
  66
  67     void set_azimuth_invalid()
  68     {
  69         m_is_azi_valid = false;
  70     }
  71
  72     bool is_azimuth_valid() const
  73     {
  74         return m_is_azi_valid;
  75     }
  76
  77     void set_azimuth_difference(CalcT const& diff)
  78     {
  79         m_azi_diff = diff;
  80         m_is_azi_diff_valid = true;
  81     }
  82
  83     void set_azimuth_difference_invalid()
  84     {
  85         m_is_azi_diff_valid = false;
  86     }
  87
  88     bool is_azimuth_difference_valid() const
  89     {
  90         return m_is_azi_diff_valid;
  91     }
  92
  93 private:
  94     Iter m_iter;
  95     CalcT m_azi;
  96     CalcT m_razi;
  97     CalcT m_azi_diff;
  98     // NOTE: these flags could be removed and replaced with some magic number
  99     //       assigned to the above variables, e.g. CalcT(1000).
 100     bool m_is_azi_valid;
 101     bool m_is_azi_diff_valid;
 102 };
 103
 104 struct calculate_point_order_by_azimuth
 105 {
 106     template <typename Ring, typename Strategy>
 107     static geometry::order_selector apply(Ring const& ring, Strategy const& strategy)
 108     {
 109         typedef typename boost::range_iterator<Ring const>::type iter_t;
 110         typedef typename Strategy::template result_type<Ring>::type calc_t;
 111         typedef clean_point<iter_t, calc_t> clean_point_t;
 112         typedef std::vector<clean_point_t> cleaned_container_t;
 113         typedef typename cleaned_container_t::iterator cleaned_iter_t;
 114
 115         calc_t const zero = 0;
 116         calc_t const pi = math::pi<calc_t>();
 117
 118         std::size_t const count = boost::size(ring);
 119         if (count < 3)
 120         {
 121             return geometry::order_undetermined;
 122         }
 123
 124         // non-duplicated, non-spike points
 125         cleaned_container_t cleaned;
 126         cleaned.reserve(count);
 127
 128         for (iter_t it = boost::begin(ring); it != boost::end(ring); ++it)
 129         {
 130             // Add point
 131             cleaned.push_back(clean_point_t(it));
 132
 133             while (cleaned.size() >= 3)
 134             {
 135                 cleaned_iter_t it0 = cleaned.end() - 3;
 136                 cleaned_iter_t it1 = cleaned.end() - 2;
 137                 cleaned_iter_t it2 = cleaned.end() - 1;
 138
 139                 calc_t diff;
 140                 if (get_or_calculate_azimuths_difference(*it0, *it1, *it2, diff, strategy)
 141                     && ! math::equals(math::abs(diff), pi))
 142                 {
 143                     // neither duplicate nor a spike - difference already stored
 144                     break;
 145                 }
 146                 else
 147                 {
 148                     // spike detected
 149                     // TODO: angles have to be invalidated only if spike is detected
 150                     // for duplicates it'd be ok to leave them
 151                     it0->set_azimuth_invalid();
 152                     it0->set_azimuth_difference_invalid();
 153                     it2->set_azimuth_difference_invalid();
 154                     cleaned.erase(it1);
 155                 }
 156             }
 157         }
 158
 159         // filter-out duplicates and spikes at the front and back of cleaned
 160         cleaned_iter_t cleaned_b = cleaned.begin();
 161         cleaned_iter_t cleaned_e = cleaned.end();
 162         std::size_t cleaned_count = cleaned.size();
 163         bool found = false;
 164         do
 165         {
 166             found = false;
 167             while(cleaned_count >= 3)
 168             {
 169                 cleaned_iter_t it0 = cleaned_e - 2;
 170                 cleaned_iter_t it1 = cleaned_e - 1;
 171                 cleaned_iter_t it2 = cleaned_b;
 172                 cleaned_iter_t it3 = cleaned_b + 1;
 173
 174                 calc_t diff = 0;
 175                 if (! get_or_calculate_azimuths_difference(*it0, *it1, *it2, diff, strategy)
 176                     || math::equals(math::abs(diff), pi))
 177                 {
 178                     // spike at the back
 179                     // TODO: angles have to be invalidated only if spike is detected
 180                     // for duplicates it'd be ok to leave them
 181                     it0->set_azimuth_invalid();
 182                     it0->set_azimuth_difference_invalid();
 183                     it2->set_azimuth_difference_invalid();
 184                     --cleaned_e;
 185                     --cleaned_count;
 186                     found = true;
 187                 }
 188                 else if (! get_or_calculate_azimuths_difference(*it1, *it2, *it3, diff, strategy)
 189                          || math::equals(math::abs(diff), pi))
 190                 {
 191                     // spike at the front
 192                     // TODO: angles have to be invalidated only if spike is detected
 193                     // for duplicates it'd be ok to leave them
 194                     it1->set_azimuth_invalid();
 195                     it1->set_azimuth_difference_invalid();
 196                     it3->set_azimuth_difference_invalid();
 197                     ++cleaned_b;
 198                     --cleaned_count;
 199                     found = true;
 200                 }
 201                 else
 202                 {
 203                     break;
 204                 }
 205             }
 206         }
 207         while (found);
 208
 209         if (cleaned_count < 3)
 210         {
 211             return geometry::order_undetermined;
 212         }
 213
 214         // calculate the sum of external angles
 215         calc_t angles_sum = zero;
 216         for (cleaned_iter_t it = cleaned_b; it != cleaned_e; ++it)
 217         {
 218             cleaned_iter_t it0 = (it == cleaned_b ? cleaned_e - 1 : it - 1);
 219             cleaned_iter_t it2 = (it == cleaned_e - 1 ? cleaned_b : it + 1);
 220
 221             calc_t diff = 0;
 222             get_or_calculate_azimuths_difference(*it0, *it, *it2, diff, strategy);
 223
 224             angles_sum += diff;
 225         }
 226
 227 #ifdef BOOST_GEOMETRY_DEBUG_POINT_ORDER
 228         std::cout << angles_sum  << " for " << geometry::wkt(ring) << std::endl;
 229 #endif
 230
 231         return angles_sum == zero ? geometry::order_undetermined
 232              : angles_sum > zero  ? geometry::clockwise
 233                                   : geometry::counterclockwise;
 234     }
 235
 236 private:
 237     template <typename Iter, typename T, typename Strategy>
 238     static bool get_or_calculate_azimuths_difference(clean_point<Iter, T> & p0,
 239                                                      clean_point<Iter, T> & p1,
 240                                                      clean_point<Iter, T> const& p2,
 241                                                      T & diff,
 242                                                      Strategy const& strategy)
 243     {
 244         if (p1.is_azimuth_difference_valid())
 245         {
 246             diff = p1.azimuth_difference();
 247             return true;
 248         }
 249
 250         T azi1, razi1, azi2, razi2;
 251         if (get_or_calculate_azimuths(p0, p1, azi1, razi1, strategy)
 252             && get_or_calculate_azimuths(p1, p2, azi2, razi2, strategy))
 253         {
 254             diff = strategy.apply(p0.ref(), p1.ref(), p2.ref(), razi1, azi2);
 255             p1.set_azimuth_difference(diff);
 256             return true;
 257         }
 258         return false;
 259     }
 260
 261     template <typename Iter, typename T, typename Strategy>
 262     static bool get_or_calculate_azimuths(clean_point<Iter, T> & p0,
 263                                           clean_point<Iter, T> const& p1,
 264                                           T & azi, T & razi,
 265                                           Strategy const& strategy)
 266     {
 267         if (p0.is_azimuth_valid())
 268         {
 269             azi = p0.azimuth();
 270             razi = p0.reverse_azimuth();
 271             return true;
 272         }
 273
 274         if (strategy.apply(p0.ref(), p1.ref(), azi, razi))
 275         {
 276             p0.set_azimuths(azi, razi);
 277             return true;
 278         }
 279
 280         return false;
 281     }
 282 };
 283
 284 struct calculate_point_order_by_area
 285 {
 286     template <typename Ring, typename Strategy>
 287     static geometry::order_selector apply(Ring const& ring, Strategy const& strategy)
 288     {
 289         typedef detail::area::ring_area
 290             <
 291                 geometry::order_as_direction<geometry::point_order<Ring>::value>::value,
 292                 geometry::closure<Ring>::value
 293             > ring_area_type;
 294
 295         typedef typename area_result
 296             <
 297                 Ring, Strategy
 298             >::type result_type;
 299
 300         result_type const result = ring_area_type::apply(ring, strategy);
 301
 302         result_type const zero = 0;
 303         return result == zero ? geometry::order_undetermined
 304              : result > zero  ? geometry::clockwise
 305                               : geometry::counterclockwise;
 306     }
 307 };
 308
 309 } // namespace detail
 310
 311 namespace dispatch
 312 {
 313
 314 template
 315 <
 316     typename Strategy,
 317     typename VersionTag = typename Strategy::version_tag
 318 >
 319 struct calculate_point_order
 320 {
 321     BOOST_MPL_ASSERT_MSG
 322     (
 323         false, NOT_IMPLEMENTED_FOR_THIS_TAG, (types<VersionTag>)
 324     );
 325 };
 326
 327 template <typename Strategy>
 328 struct calculate_point_order<Strategy, strategy::point_order::area_tag>
 329     : geometry::detail::calculate_point_order_by_area
 330 {};
 331
 332 template <typename Strategy>
 333 struct calculate_point_order<Strategy, strategy::point_order::azimuth_tag>
 334     : geometry::detail::calculate_point_order_by_azimuth
 335 {};
 336
 337
 338 } // namespace dispatch
 339
 340 namespace detail
 341 {
 342
 343 template <typename Ring, typename Strategy>
 344 inline geometry::order_selector calculate_point_order(Ring const& ring, Strategy const& strategy)
 345 {
 346     concepts::check<Ring>();
 347
 348     return dispatch::calculate_point_order<Strategy>::apply(ring, strategy);
 349 }
 350
 351 template <typename Ring>
 352 inline geometry::order_selector calculate_point_order(Ring const& ring)
 353 {
 354     typedef typename strategy::point_order::services::default_strategy
 355         <
 356             typename geometry::cs_tag<Ring>::type
 357         >::type strategy_type;
 358
 359     concepts::check<Ring>();
 360
 361     return dispatch::calculate_point_order<strategy_type>::apply(ring, strategy_type());
 362 }
 363
 364
 365 } // namespace detail
 366
 367 }} // namespace boost::geometry
 368
 369
 370 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CALCULATE_POINT_ORDER_HPP