ceph/src/boost/libs/geometry/test/algorithms/densify.cpp

   1 // Boost.Geometry
   2 // Unit Test
   3
   4 // Copyright (c) 2017-2018, Oracle and/or its affiliates.
   5
   6 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   7
   8 // Licensed under the Boost Software License version 1.0.
   9 // http://www.boost.org/users/license.html
  10
  11
  12 #include <geometry_test_common.hpp>
  13
  14 #include <boost/geometry/geometries/geometries.hpp>
  15
  16 #include <boost/geometry/algorithms/densify.hpp>
  17 #include <boost/geometry/algorithms/length.hpp>
  18 #include <boost/geometry/algorithms/num_points.hpp>
  19 #include <boost/geometry/algorithms/perimeter.hpp>
  20
  21 #include <boost/geometry/iterators/segment_iterator.hpp>
  22
  23 #include <boost/geometry/strategies/cartesian/densify.hpp>
  24 #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
  25 #include <boost/geometry/strategies/geographic/densify.hpp>
  26 #include <boost/geometry/strategies/geographic/distance.hpp>
  27 #include <boost/geometry/strategies/spherical/densify.hpp>
  28 #include <boost/geometry/strategies/spherical/distance_haversine.hpp>
  29
  30 #include <boost/geometry/io/wkt/wkt.hpp>
  31
  32
  33 struct check_lengths
  34 {
  35     template <typename G, typename S>
  36     void operator()(G const& g, G const& o, S const& s) const
  37     {
  38         double d1 = bg::length(g, s);
  39         double d2 = bg::length(o, s);
  40
  41         BOOST_CHECK_CLOSE(d1, d2, 0.0001);
  42     }
  43 };
  44
  45 struct check_perimeters
  46 {
  47     template <typename G, typename S>
  48     void operator()(G const& g, G const& o, S const& s) const
  49     {
  50         double d1 = bg::perimeter(g, s);
  51         double d2 = bg::perimeter(o, s);
  52
  53         BOOST_CHECK_CLOSE(d1, d2, 0.0001);
  54     }
  55 };
  56
  57 template <typename G, typename DistS>
  58 double inline shortest_length(G const& g, DistS const& dist_s)
  59 {
  60     double min_len = (std::numeric_limits<double>::max)();
  61     for (bg::segment_iterator<G const> it = bg::segments_begin(g);
  62             it != bg::segments_end(g); ++it)
  63     {
  64         double len = bg::length(*it, dist_s);
  65         min_len = (std::min)(min_len, len);
  66     }
  67     return min_len;
  68 }
  69
  70 template <typename G, typename DistS>
  71 double inline greatest_length(G const& o, DistS const& dist_s)
  72 {
  73     double max_len = 0.0;
  74     for (bg::segment_iterator<G const> it = bg::segments_begin(o);
  75             it != bg::segments_end(o); ++it)
  76     {
  77         double len = bg::length(*it, dist_s);
  78         max_len = (std::max)(max_len, len);
  79     }
  80     return max_len;
  81 }
  82
  83 template <typename G, typename CSTag = typename bg::cs_tag<G>::type>
  84 struct cs_data
  85 {};
  86
  87 template <typename G>
  88 struct cs_data<G, bg::cartesian_tag>
  89 {
  90     bg::strategy::densify::cartesian<> compl_s;
  91     bg::strategy::distance::pythagoras<> dist_s;
  92 };
  93
  94 template <typename G>
  95 struct cs_data<G, bg::spherical_equatorial_tag>
  96 {
  97     cs_data()
  98         : model(6378137.0)
  99         , compl_s(model)
 100         , dist_s(6378137.0)
 101     {}
 102
 103     bg::srs::sphere<double> model;
 104     bg::strategy::densify::spherical<> compl_s;
 105     bg::strategy::distance::haversine<double> dist_s;
 106 };
 107
 108 template <typename G>
 109 struct cs_data<G, bg::geographic_tag>
 110 {
 111     cs_data()
 112         : model(6378137.0, 6356752.3142451793)
 113         , compl_s(model)
 114         , dist_s(model)
 115     {}
 116
 117     bg::srs::spheroid<double> model;
 118     bg::strategy::densify::geographic<> compl_s;
 119     bg::strategy::distance::geographic<> dist_s;
 120 };
 121
 122 template <typename G, typename DistS, typename Check>
 123 inline void check_result(G const& g, G const& o, double max_distance,
 124                          DistS const& dist_s, Check const& check)
 125 {
 126     // geometry was indeed densified
 127     std::size_t g_count = bg::num_points(g);
 128     std::size_t o_count = bg::num_points(o);
 129     BOOST_CHECK(g_count < o_count);
 130
 131     // all segments have lengths smaller or equal to max_distance
 132     double gr_len = greatest_length(o, dist_s);
 133     // NOTE: Currently geographic strategies can generate segments that have
 134     //       lengths slightly greater than max_distance. In order to change
 135     //       this the generation of new points should e.g. be recursive with
 136     //       stop condition comparing the current distance calculated by
 137     //       inverse strategy.
 138     // NOTE: Closeness value tweaked for Andoyer
 139     bool is_close = (gr_len - max_distance) / (std::max)(gr_len, max_distance) < 0.0001;
 140     BOOST_CHECK(gr_len <= max_distance || is_close);
 141
 142     // the overall length or perimeter didn't change
 143     check(g, o, dist_s);
 144 }
 145
 146 template <typename G, typename Check>
 147 inline void test_geometry(std::string const& wkt, Check const& check)
 148 {
 149     cs_data<G> d;
 150
 151     G g;
 152     bg::read_wkt(wkt, g);
 153
 154     {
 155         bg::default_strategy def_s;
 156         double max_distance = shortest_length(g, def_s) / 3.0;
 157
 158         G o;
 159         bg::densify(g, o, max_distance);
 160
 161         check_result(g, o, max_distance, def_s, check);
 162     }
 163
 164     {
 165         double max_distance = shortest_length(g, d.dist_s) / 3.0;
 166
 167         G o;
 168         bg::densify(g, o, max_distance, d.compl_s);
 169
 170         check_result(g, o, max_distance, d.dist_s, check);
 171     }
 172 }
 173
 174 template <typename G>
 175 inline void test_linear(std::string const& wkt)
 176 {
 177     test_geometry<G>(wkt, check_lengths());
 178 }
 179
 180 template <typename G>
 181 inline void test_areal(std::string const& wkt)
 182 {
 183     test_geometry<G>(wkt, check_perimeters());
 184 }
 185
 186 template <typename P>
 187 void test_all()
 188 {
 189     typedef bg::model::linestring<P> ls_t;
 190     typedef bg::model::multi_linestring<ls_t> mls_t;
 191
 192     typedef bg::model::ring<P> ring_t;
 193     typedef bg::model::polygon<P> poly_t;
 194     typedef bg::model::multi_polygon<poly_t> mpoly_t;
 195
 196     typedef bg::model::ring<P, true, false> oring_t;
 197     typedef bg::model::polygon<P, true, false> opoly_t;
 198     typedef bg::model::multi_polygon<opoly_t> ompoly_t;
 199
 200     test_linear<ls_t>("LINESTRING(4 -4, 4 -1)");
 201     test_linear<ls_t>("LINESTRING(4 4, 4 1)");
 202     test_linear<ls_t>("LINESTRING(0 0, 180 0)");
 203     test_linear<ls_t>("LINESTRING(1 1, -179 -1)");
 204
 205     test_linear<ls_t>("LINESTRING(1 1, 2 2, 4 2)");
 206     test_linear<mls_t>("MULTILINESTRING((1 1, 2 2),(2 2, 4 2))");
 207
 208     test_areal<ring_t>("POLYGON((1 1, 1 2, 2 2, 1 1))");
 209     test_areal<poly_t>("POLYGON((1 1, 1 4, 4 4, 4 1, 1 1),(1 1, 2 2, 2 3, 1 1))");
 210     test_areal<mpoly_t>("MULTIPOLYGON(((1 1, 1 4, 4 4, 4 1, 1 1),(1 1, 2 2, 2 3, 1 1)),((4 4, 5 5, 5 4, 4 4)))");
 211
 212     test_areal<oring_t>("POLYGON((1 1, 1 2, 2 2))");
 213     test_areal<opoly_t>("POLYGON((1 1, 1 4, 4 4, 4 1),(1 1, 2 2, 2 3))");
 214     test_areal<ompoly_t>("MULTIPOLYGON(((1 1, 1 4, 4 4, 4 1),(1 1, 2 2, 2 3)),((4 4, 5 5, 5 4)))");
 215
 216     test_areal<ring_t>("POLYGON((0 0,0 40,40 40,40 0,0 0))");
 217     test_areal<oring_t>("POLYGON((0 0,0 40,40 40,40 0))");
 218 }
 219
 220 int test_main(int, char* [])
 221 {
 222     test_all< bg::model::point<double, 2, bg::cs::cartesian> >();
 223     test_all< bg::model::point<double, 2, bg::cs::spherical_equatorial<bg::degree> > >();
 224     test_all< bg::model::point<double, 2, bg::cs::geographic<bg::degree> > >();
 225
 226     return 0;
 227 }