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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   5 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
   6 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
   7
   8 // This file was modified by Oracle on 2014-2021.
   9 // Modifications copyright (c) 2014-2021 Oracle and/or its affiliates.
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11
  12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  14
  15 // Use, modification and distribution is subject to the Boost Software License,
  16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  17 // http://www.boost.org/LICENSE_1_0.txt)
  18
  19 #include <algorithms/test_centroid.hpp>
  20
  21 #include <boost/geometry/geometries/geometries.hpp>
  22 #include <boost/geometry/geometries/point_xy.hpp>
  23 #include <boost/geometry/geometries/adapted/c_array.hpp>
  24 #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
  25
  26 #include <test_geometries/all_custom_polygon.hpp>
  27
  28 BOOST_GEOMETRY_REGISTER_C_ARRAY_CS(cs::cartesian)
  29 BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
  30
  31 template <typename Polygon>
  32 void test_polygon()
  33 {
  34     test_centroid<Polygon>(
  35         "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2"
  36         ",3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3))",
  37         4.06923363095238, 1.65055803571429);
  38
  39     // with holes
  40     test_centroid<Polygon>(
  41         "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2"
  42         ",3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3)"
  43         ",(4 2,4.2 1.4,4.8 1.9,4.4 2.2,4 2))",
  44         4.0466264962959677, 1.6348996057331333);
  45
  46     test_centroid<Polygon>("POLYGON((0 0,0 10,10 10,10 0,0 0))", 5.0, 5.0);
  47     test_centroid<Polygon>("POLYGON((-10 0,0 0,0 -10,-10 -10,-10 0))", -5.0, -5.0);
  48
  49     // invalid, self-intersecting polygon (area = 0)
  50     test_centroid<Polygon>("POLYGON((1 1,4 -2,4 2,10 0,1 0,10 1,1 1))", 1.0, 1.0);
  51     // invalid, degenerated
  52     test_centroid<Polygon>("POLYGON((1 1,1 1,1 1,1 1))", 1.0, 1.0);
  53     test_centroid<Polygon>("POLYGON((1 1))", 1.0, 1.0);
  54
  55     // should (1.5 1) be returned?
  56     // if yes, then all other Polygons degenerated to Linestrings should be handled
  57     test_centroid<Polygon>("POLYGON((1 1,2 1,1 1,1 1))", 1.0, 1.0);
  58
  59     // reported 2015.04.24
  60     // input INT, result FP
  61     test_centroid
  62         <
  63             bg::model::polygon<bg::model::d2::point_xy<int> >,
  64             typename bg::point_type<Polygon>::type,
  65             typename bg::coordinate_type<Polygon>::type
  66         >("POLYGON((1 1, 1 2, 2 2, 2 1, 1 1))", 1.5, 1.5);
  67 }
  68
  69
  70 template <typename P>
  71 void test_2d()
  72 {
  73     test_centroid<bg::model::linestring<P> >("LINESTRING(1 1, 2 2, 3 3)", 2.0, 2.0);
  74     test_centroid<bg::model::linestring<P> >("LINESTRING(0 0,0 4, 4 4)", 1.0, 3.0);
  75     test_centroid<bg::model::linestring<P> >("LINESTRING(0 0,3 3,0 6,3 9,0 12)", 1.5, 6.0);
  76
  77     test_centroid<bg::model::linestring<P> >("LINESTRING(1 1,10 1,1 0,10 0,4 -2,1 1)",
  78                                              5.41385255923004, 0.13507358481085);
  79
  80     // degenerated linestring (length = 0)
  81     test_centroid<bg::model::linestring<P> >("LINESTRING(1 1, 1 1)", 1.0, 1.0);
  82     test_centroid<bg::model::linestring<P> >("LINESTRING(1 1)", 1.0, 1.0);
  83
  84     {
  85         bg::model::linestring<P> ls;
  86         // LINESTRING(1 -1,1e308 -1e308,0.0001 0.000)
  87         bg::append(ls, P(1, -1));
  88         typedef typename bg::coordinate_type<P>::type coord_type;
  89         //double m = 1.0e308;
  90         coord_type m = (std::numeric_limits<coord_type>::max)();
  91         bg::append(ls, P(coord_type(m), coord_type(-m)));
  92         bg::append(ls, P(coord_type(0.0001), coord_type(0.000)));
  93         if (BOOST_GEOMETRY_CONDITION((std::is_same<typename bg::coordinate_type<P>::type, double>::value)))
  94         {
  95             // for doubles the INF is detected and the calculation stopped
  96             // currently for Geometries for which the centroid can't be calculated
  97             // the first Point is returned
  98             test_centroid<bg::model::linestring<P> >(ls, 1.0, -1.0);
  99         }
 100         else
 101         {
 102             // for floats internally the double is used to store intermediate results
 103             // this type is capable to store MAX_FLT and "correctly" calculate the centroid
 104             // test_centroid<bg::model::linestring<P> >(ls, m/3, -m/3);
 105             // the result is around (1.7e38 -1.7e38)
 106         }
 107     }
 108
 109     test_centroid<bg::model::segment<P> >("LINESTRING(1 1, 3 3)", 2.0, 2.0);
 110
 111     test_centroid<bg::model::ring<P> >(
 112         "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2"
 113         ",3.7 1.6,3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3))",
 114         4.06923363095238, 1.65055803571429);
 115
 116     test_polygon<bg::model::polygon<P> >();
 117     test_polygon<all_custom_polygon<P> >();
 118
 119     // ccw
 120     test_centroid<bg::model::ring<P, false> >(
 121         "POLYGON((2 1.3,2.9 0.7,4.9 0.8,5.4 1.2,5.3 2.6,4.1 3,3.4 2"
 122             ",3.7 1.6,3.4 1.2,2.8 1.8,2.4 1.7,2 1.3))",
 123         4.06923363095238, 1.65055803571429);
 124
 125     // open / closed
 126     test_centroid<bg::model::ring<P, true, true> >(
 127             "POLYGON((1 1,2 2,3 1,2 0,1 1))", 2.0, 1.0);
 128     test_centroid<bg::model::ring<P, true, false> >(
 129             "POLYGON((1 1,2 2,3 1,2 0))", 2.0, 1.0);
 130
 131     test_centroid<bg::model::box<P> >("POLYGON((1 2,3 4))", 2, 3);
 132     test_centroid<P>("POINT(3 3)", 3, 3);
 133
 134     // INT -> FP
 135     test_centroid
 136         <
 137             bg::model::ring<bg::model::d2::point_xy<int> >,
 138             P, typename bg::coordinate_type<P>::type
 139         >("POLYGON((1 1, 1 2, 2 2, 2 1, 1 1))", 1.5, 1.5);
 140     test_centroid
 141         <
 142             bg::model::linestring<bg::model::d2::point_xy<int> >,
 143             P, typename bg::coordinate_type<P>::type
 144         >("LINESTRING(1 1, 2 2)", 1.5, 1.5);
 145     test_centroid
 146         <
 147             bg::model::box<bg::model::d2::point_xy<int> >,
 148             P, typename bg::coordinate_type<P>::type
 149         >("BOX(1 1, 2 2)", 1.5, 1.5);
 150 }
 151
 152
 153 template <typename P>
 154 void test_3d()
 155 {
 156     test_centroid<bg::model::linestring<P> >("LINESTRING(1 2 3,4 5 -6,7 -8 9,-10 11 12,13 -14 -15, 16 17 18)",
 157                                              5.6748865168734692, 0.31974938587214002, 1.9915270387763671);
 158     test_centroid<bg::model::box<P> >("POLYGON((1 2 3,5 6 7))", 3, 4, 5);
 159     test_centroid<bg::model::segment<P> >("LINESTRING(1 1 1,3 3 3)", 2, 2, 2);
 160     test_centroid<P>("POINT(1 2 3)", 1, 2, 3);
 161 }
 162
 163
 164 template <typename P>
 165 void test_5d()
 166 {
 167     test_centroid<bg::model::linestring<P> >("LINESTRING(1 2 3 4 95,4 5 -6 24 40,7 -8 9 -5 -7,-10 11 12 -5 5,13 -14 -15 4 3, 16 17 18 5 12)",
 168                                              4.9202312983547678, 0.69590937869808345, 1.2632138719797417, 6.0468332057401986, 23.082402715244868);
 169 }
 170
 171 template <typename P>
 172 void test_exceptions()
 173 {
 174     test_centroid_exception<bg::model::linestring<P> >();
 175     test_centroid_exception<bg::model::polygon<P> >();
 176     test_centroid_exception<bg::model::ring<P> >();
 177
 178     // Empty exterior ring
 179     test_centroid_exception<bg::model::polygon<P> >(
 180         "POLYGON((), ())");
 181     test_centroid_exception<bg::model::polygon<P> >(
 182         "POLYGON((), (0 0, 1 0, 1 1, 0 1, 0 0))");
 183 }
 184
 185 template <typename P>
 186 void test_empty()
 187 {
 188     // Empty interior ring
 189     test_centroid<bg::model::polygon<P> >(
 190         "POLYGON((0 0, 1 0, 1 1, 0 1, 0 0), ())",
 191         0.5, 0.5);
 192 }
 193
 194 void test_large_integers()
 195 {
 196     typedef bg::model::point<int, 2, bg::cs::cartesian> int_point_type;
 197     typedef bg::model::point<double, 2, bg::cs::cartesian> double_point_type;
 198
 199     bg::model::polygon<int_point_type> int_poly;
 200     bg::model::polygon<double_point_type> double_poly;
 201
 202     std::string const polygon_li = "POLYGON((1872000 528000,1872000 192000,1536119 192000,1536000 528000,1200000 528000,1200000 863880,1536000 863880,1872000 863880,1872000 528000))";
 203     bg::read_wkt(polygon_li, int_poly);
 204     bg::read_wkt(polygon_li, double_poly);
 205
 206     int_point_type int_centroid;
 207     double_point_type double_centroid;
 208
 209     bg::centroid(int_poly, int_centroid);
 210     bg::centroid(double_poly, double_centroid);
 211
 212     int_point_type double_centroid_as_int;
 213     bg::assign_zero(double_centroid_as_int);
 214     bg::assign(int_centroid, double_centroid_as_int);
 215
 216     BOOST_CHECK_EQUAL(bg::get<0>(int_centroid), bg::get<0>(double_centroid_as_int));
 217     BOOST_CHECK_EQUAL(bg::get<1>(int_centroid), bg::get<1>(double_centroid_as_int));
 218 }
 219
 220 void test_large_doubles()
 221 {
 222     typedef bg::model::point<double, 2, bg::cs::cartesian> point;
 223     point pt_far, pt_near;
 224     bg::model::polygon<point> poly_far, poly_near;
 225
 226     // related to ticket #10643
 227     bg::read_wkt("POLYGON((1074699.93 703064.65, 1074703.90 703064.58, 1074704.53 703061.40, 1074702.10 703054.62, 1074699.93 703064.65))", poly_far);
 228     bg::read_wkt("POLYGON((699.93 64.65, 703.90 64.58, 704.53 61.40, 702.10 54.62, 699.93 64.65))", poly_near);
 229
 230     bg::centroid(poly_far, pt_far);
 231     bg::centroid(poly_near, pt_near);
 232
 233     BOOST_CHECK(bg::within(pt_far, poly_far));
 234     BOOST_CHECK(bg::within(pt_near, poly_near));
 235
 236     point pt_near_moved;
 237     bg::set<0>(pt_near_moved, bg::get<0>(pt_near) + 1074000.0);
 238     bg::set<1>(pt_near_moved, bg::get<1>(pt_near) + 703000.0);
 239
 240     double d = bg::distance(pt_far, pt_near_moved);
 241     BOOST_CHECK(d < 0.1);
 242 }
 243
 244 int test_main(int, char* [])
 245 {
 246     test_2d<bg::model::d2::point_xy<double> >();
 247     test_2d<boost::tuple<float, float> >();
 248     test_2d<bg::model::d2::point_xy<float> >();
 249
 250     test_3d<boost::tuple<double, double, double> >();
 251
 252     test_5d<boost::tuple<double, double, double, double, double> >();
 253
 254 #ifndef NDEBUG
 255     // The test currently fails in release mode. TODO: fix this
 256     test_large_integers();
 257 #endif
 258
 259     test_large_doubles();
 260
 261     test_exceptions<bg::model::d2::point_xy<double> >();
 262     test_empty<bg::model::d2::point_xy<double> >();
 263
 264     return 0;
 265 }