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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   5 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
   6 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
   7
   8 // This file was modified by Oracle on 2021-2022.
   9 // Modifications copyright (c) 2021-2022 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 <iterator>
  20
  21
  22 #include <algorithms/test_simplify.hpp>
  23 #include <boost/geometry/geometries/geometries.hpp>
  24 #include <boost/geometry/geometries/point_xy.hpp>
  25
  26 #include <test_geometries/wrapped_boost_array.hpp>
  27 #include <test_common/test_point.hpp>
  28
  29 // #define TEST_PULL89
  30 #ifdef TEST_PULL89
  31 #include <boost/geometry/strategies/cartesian/distance_projected_point_ax.hpp>
  32 #endif
  33
  34
  35 #ifdef TEST_PULL89
  36 template <typename Geometry, typename T>
  37 void test_with_ax(std::string const& wkt,
  38         std::string const& expected,
  39         T const& adt,
  40         T const& xdt)
  41 {
  42     typedef typename bg::point_type<Geometry>::type point_type;
  43     typedef bg::strategy::distance::detail::projected_point_ax<> ax_type;
  44     typedef typename bg::strategy::distance::services::return_type
  45     <
  46         bg::strategy::distance::detail::projected_point_ax<>,
  47         point_type,
  48         point_type
  49     >::type return_type;
  50
  51     typedef bg::strategy::distance::detail::projected_point_ax_less
  52     <
  53         return_type
  54     > comparator_type;
  55
  56     typedef bg::strategy::simplify::detail::douglas_peucker
  57     <
  58         point_type,
  59         bg::strategy::distance::detail::projected_point_ax<>,
  60         comparator_type
  61     > dp_ax;
  62
  63     return_type max_distance(adt, xdt);
  64     comparator_type comparator(max_distance);
  65     dp_ax strategy(comparator);
  66
  67     test_geometry<Geometry>(wkt, expected, max_distance, strategy);
  68 }
  69 #endif
  70
  71
  72 template <typename P>
  73 void test_all()
  74 {
  75     test_geometry<bg::model::linestring<P> >(
  76         "LINESTRING(0 0,5 5,10 10)",
  77         "LINESTRING(0 0,10 10)", 1.0);
  78
  79     test_geometry<bg::model::linestring<P> >(
  80         "LINESTRING(0 0, 5 5, 6 5, 10 10)",
  81         "LINESTRING(0 0,10 10)", 1.0);
  82
  83     test_geometry<bg::model::linestring<P> >(
  84         "LINESTRING(0 0,5 5,7 5,10 10)",
  85         "LINESTRING(0 0,5 5,7 5,10 10)", 1.0);
  86
  87     // Lightning-form which fails for Douglas-Peucker
  88     test_geometry<bg::model::linestring<P> >(
  89         "LINESTRING(0 0,120 6,80 10,200 0)",
  90         "LINESTRING(0 0,120 6,80 10,200 0)", 7);
  91
  92     // Same which reordered coordinates
  93     test_geometry<bg::model::linestring<P> >(
  94         "LINESTRING(0 0,80 10,120 6,200 0)",
  95         "LINESTRING(0 0,80 10,200 0)", 7);
  96
  97     // Duplicate point is removed
  98     test_geometry<bg::model::linestring<P> >(
  99         "LINESTRING(0 0,0 0)",
 100         "LINESTRING(0 0)", 1.0);
 101
 102     // Mail 2013-10-07, real-life test, piece of River Leine
 103     // PostGIS returns exactly the same result
 104     test_geometry<bg::model::linestring<P> >(
 105          "LINESTRING(4293586 3290439,4293568 3290340,4293566 3290332,4293570 3290244,4293576 3290192"
 106                    ",4293785 3289660,4293832 3289597,4293879 3289564,4293937 3289545,4294130 3289558"
 107                    ",4294204 3289553,4294240 3289539,4294301 3289479,4294317 3289420,4294311 3289353"
 108                    ",4294276 3289302,4293870 3289045,4293795 3288978,4293713 3288879,4293669 3288767"
 109                    ",4293654 3288652,4293657 3288563,4293690 3288452,4293761 3288360,4293914 3288215"
 110                    ",4293953 3288142,4293960 3288044,4293951 3287961,4293913 3287875,4293708 3287628"
 111                    ",4293658 3287542,4293633 3287459,4293630 3287383,4293651 3287323,4293697 3287271"
 112                    ",4293880 3287128,4293930 3287045,4293938 3286977,4293931 3286901,4293785 3286525"
 113                    ",4293775 3286426,4293786 3286358,4293821 3286294,4294072 3286076,4294134 3285986)",
 114           "LINESTRING(4293586 3290439,4293785 3289660,4294317 3289420,4293654 3288652,4293960 3288044"
 115                   ",4293633 3287459,4293786 3286358,4294134 3285986)", 250);
 116
 117     /* TODO fix this
 118     test_geometry<test::wrapped_boost_array<P, 10> >(
 119         "LINESTRING(0 0,5 5,7 5,10 10)",
 120         "LINESTRING(0 0,5 5,7 5,10 10)", 1.0);
 121     */
 122
 123     /*
 124
 125     Above can be checked in PostGIS by:
 126
 127     select astext(ST_Simplify(geomfromtext('LINESTRING(0 0, 5 5, 10 10)'),1.0)) as simplified
 128     union all select astext(ST_Simplify(geomfromtext('LINESTRING(0 0, 5 5, 6 5, 10 10)'),1.0))
 129     etc
 130     */
 131
 132
 133     test_geometry<bg::model::polygon<P> >(
 134         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0))",
 135         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0))", 1.0);
 136
 137     test_geometry<bg::model::polygon<P> >(
 138         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0),(7 3,7 6,1 6,1 3,4 3,7 3))",
 139         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0),(7 3,7 6,1 6,1 3,7 3))", 1.0);
 140
 141     // Closing point should be simplified away
 142     test_geometry<bg::model::polygon<P> >(
 143         "POLYGON((1 0,0 0,0 4,4 4,4 0,1 0))",
 144         "POLYGON((0 0,0 4,4 4,4 0,0 0))", 0.1);
 145
 146     // Section around closing point should be simplified away
 147     test_geometry<bg::model::polygon<P> >(
 148         "POLYGON((5 0,4 0,3 0,2 0,1 0,0 0,0 5,5 5,5 0))",
 149         "POLYGON((5 0,0 0,0 5,5 5,5 0))", 0.1);
 150
 151     // Manually rotate this WKT over all the 5 redundant points at closing area
 152     test_geometry<bg::model::polygon<P> >(
 153         "POLYGON((4 0,3 0,2 0,1 0,0 0,0 5,5 5,5 0,4 0))",
 154         "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1);
 155     test_geometry<bg::model::polygon<P> >(
 156         "POLYGON((3 0,2 0,1 0,0 0,0 5,5 5,5 0,4 0,3 0))",
 157         "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1);
 158     test_geometry<bg::model::polygon<P> >(
 159         "POLYGON((2 0,1 0,0 0,0 5,5 5,5 0,4 0,3 0,2 0))",
 160         "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1);
 161     test_geometry<bg::model::polygon<P> >(
 162         "POLYGON((1 0,0 0,0 5,5 5,5 0,4 0,3 0,2 0,1 0))",
 163         "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1);
 164     test_geometry<bg::model::polygon<P> >(
 165         "POLYGON((0 0,0 5,5 5,5 0,4 0,3 0,2 0,1 0,0 0))",
 166         "POLYGON((0 0,0 5,5 5,5 0,0 0))", 0.1);
 167
 168     // Test wither all collinear points in between are simplified away
 169     // First approach did select one of them because it was the end of the
 170     // "closing area". Now the opposite is taken, which is farthest and never
 171     // collinear
 172     test_geometry<bg::model::polygon<P> >(
 173             "POLYGON((2 0,1 0,0 0,0 1,0 2,0 3,0 4,1 4,2 4,3 4,4 4,4 3,4 2,4 1,4 0,3 0,2 0))",
 174             "POLYGON((0 0,0 4,4 4,4 0,0 0))", 1.0);
 175
 176     // Test simplifying away one of the sides (collinear), then closing point
 177     // and finally the whole polygon
 178     std::string const near_triangle = "POLYGON((0.55 0.55,1 0,0.5 0,0 0,0 1,0.55 0.55))";
 179     test_geometry<bg::model::polygon<P> >(near_triangle,
 180         "POLYGON((0.55 0.55,1 0,0 0,0 1,0.55 0.55))", 0.01);
 181     test_geometry<bg::model::polygon<P> >(near_triangle,
 182         "POLYGON((1 0,0 0,0 1,1 0))", 0.1);
 183     // 0.9 should still result in a simplified polygon
 184     test_geometry<bg::model::polygon<P> >(near_triangle,
 185         "POLYGON((1 0,0 0,0 1,1 0))", 0.9);
 186     test_geometry<bg::model::polygon<P> >(near_triangle,
 187         "POLYGON(())", 1.1);
 188
 189     // Test simplifying away the closing point, and closing it explicitly
 190     std::string const salamina = "POLYGON((2616131.59828 4579307.29099,2616687.86177 4579151.05325,2618172.52982 4578718.79836,2618728.79332 4578522.73574,2620336.91468 4577424.54293,2620522.48427 4576992.50129,2621264.76264 4569815.3917,2621140.75272 4569502.07546,2620491.53745 4568208.96982,2620151.34509 4567855.90928,2612606.55528 4562800.36094,2611833.3301 4562291.50023,2611369.5731 4562174.16117,2610225.54269 4562408.69959,2605896.21638 4564367.29512,2605494.13038 4564641.6634,2605277.94792 4566288.44857,2606019.89233 4569423.46562,2609050.12019 4577424.54293,2614337.90732 4579347.12775,2615296.7021 4579543.34723,2616131.59828 4579307.29099))";
 191     test_geometry<bg::model::polygon<P> >(salamina, 196318951.5097456, 100);
 192     test_geometry<bg::model::polygon<P> >(salamina, 194471472.35804176, 200);
 193     test_geometry<bg::model::polygon<P> >(salamina, 191735337.33374023, 500);
 194     test_geometry<bg::model::polygon<P> >(salamina, 186593693.18401337, 1000);
 195     test_geometry<bg::model::polygon<P> >(salamina, 181448561.04094696, 2000);
 196     test_geometry<bg::model::polygon<P> >(salamina, 141965392.92240524, 5000);
 197
 198     // Interior ring (sized ~ 1) should be simplified away (distance 5)
 199     test_geometry<bg::model::polygon<P> >(
 200         "POLYGON((0 0,0 10,10 10,10 0,0 0),(5 5,6 6,5 6,5 5))",
 201         "POLYGON((0 0,0 10,10 10,10 0,0 0))", 5.0);
 202
 203     // Non-closed version
 204     test_geometry<bg::model::polygon<P, true, false> >(
 205         "POLYGON((1 0,0 0,0 4,4 4,4 0))",
 206         "POLYGON((0 0,0 4,4 4,4 0))", 0.1);
 207     test_geometry<bg::model::polygon<P, true, false> >(
 208         "POLYGON((0 0,0 1,1 1,1 0))",
 209         "POLYGON((0 0,0 1,1 1,1 0))", 0.1);
 210
 211     // Non-closed, ccw version
 212     // https://github.com/boostorg/geometry/issues/956
 213     test_geometry<bg::model::polygon<P, false, false> >(
 214         "POLYGON((0 0,0.4 0,0.4 0.4))",
 215         "POLYGON((0 0,0.4 0,0.4 0.4))", 0);
 216
 217
 218     {
 219         // Test with explicit strategy
 220
 221         typedef bg::strategy::simplify::douglas_peucker
 222         <
 223             P,
 224             bg::strategy::distance::projected_point<double>
 225         > dp;
 226
 227         test_geometry<bg::model::linestring<P> >(
 228             "LINESTRING(0 0,5 5,10 10)",
 229             "LINESTRING(0 0,10 10)", 1.0, dp());
 230     }
 231
 232
 233     // POINT: check compilation
 234     test_geometry<P>(
 235         "POINT(0 0)",
 236         "POINT(0 0)", 1.0);
 237
 238     test_geometry<bg::model::segment<P> >(
 239         "SEGMENT(0 0, 1 1)",
 240         "SEGMENT(0 0, 1 1)", 1.0);
 241
 242     test_geometry<bg::model::box<P> >(
 243         "BOX(0 0, 1 1)",
 244         "BOX(0 0, 1 1)", 1.0);
 245
 246     test_geometry<bg::model::multi_point<P> >(
 247         "MULTIPOINT(0 0, 1 1, 2 2)",
 248         "MULTIPOINT(0 0, 1 1, 2 2)", 1.0);
 249
 250
 251     // RING: check compilation and behaviour
 252     test_geometry<bg::model::ring<P> >(
 253         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0))",
 254         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0))", 1.0);
 255
 256
 257 #ifdef TEST_PULL89
 258     test_with_ax<bg::model::linestring<P> >(
 259         "LINESTRING(0 0,120 6,80 10,200 0)",
 260         "LINESTRING(0 0,80 10,200 0)", 10, 7);
 261 #endif
 262 }
 263
 264 template <typename P>
 265 void test_zigzag()
 266 {
 267     static const std::string zigzag = "LINESTRING(0 10,1 7,1 9,2 6,2 7,3 4,3 5,5 3,4 5,6 2,6 3,9 1,7 3,10 1,9 2,12 1,10 2,13 1,11 2,14 1,12 2,16 1,14 2,17 3,15 3,18 4,16 4,19 5,17 5,20 6,18 6,21 8,19 7,21 9,19 8,21 10,19 9,21 11,19 10,20 13,19 11)";
 268
 269     static const std::string expected100 = "LINESTRING(0 10,3 4,5 3,4 5,6 2,9 1,7 3,10 1,9 2,16 1,14 2,17 3,15 3,18 4,16 4,19 5,17 5,21 8,19 7,21 9,19 8,21 10,19 9,21 11,19 10,20 13,19 11)";
 270     static const std::string expected150 = "LINESTRING(0 10,6 2,16 1,14 2,21 8,19 7,21 9,19 8,21 10,19 9,20 13,19 11)";
 271     static const std::string expected200 = "LINESTRING(0 10,6 2,16 1,14 2,21 8,19 7,20 13,19 11)";
 272     static const std::string expected225 = "LINESTRING(0 10,6 2,16 1,21 8,19 11)";
 273     test_geometry<bg::model::linestring<P> >(zigzag, expected100, 1.0001);
 274     test_geometry<bg::model::linestring<P> >(zigzag, expected150, 1.5001);
 275     test_geometry<bg::model::linestring<P> >(zigzag, expected200, 2.0001);
 276     test_geometry<bg::model::linestring<P> >(zigzag, expected225, 2.25); // should be larger than sqrt(5)=2.236
 277
 278 #ifdef TEST_PULL89
 279     // This should work (results might vary but should have LESS points then expected above
 280     // Small xtd, larger adt,
 281     test_with_ax<bg::model::linestring<P> >(zigzag, expected100, 1.0001, 1.0001);
 282     test_with_ax<bg::model::linestring<P> >(zigzag, expected150, 1.5001, 1.0001);
 283     test_with_ax<bg::model::linestring<P> >(zigzag, expected200, 2.0001, 1.0001);
 284     test_with_ax<bg::model::linestring<P> >(zigzag, expected225, 2.25, 1.0001);
 285 #endif
 286
 287 }
 288
 289
 290 template <typename P>
 291 void test_3d()
 292 {
 293     test_geometry<bg::model::linestring<P> >(
 294         "LINESTRING(0 0 0,1 1 1,2 2 0)",
 295         "LINESTRING(0 0 0,2 2 0)", 1.0001);
 296     test_geometry<bg::model::linestring<P> >(
 297         "LINESTRING(0 0 0,1 1 1,2 2 0)",
 298         "LINESTRING(0 0 0,1 1 1,2 2 0)", 0.9999);
 299 }
 300
 301
 302 template <typename P>
 303 void test_spherical()
 304 {
 305     test_geometry<bg::model::linestring<P> >(
 306         "LINESTRING(4.1 52.1,4.2 52.2,4.3 52.3)",
 307         "LINESTRING(4.1 52.1,4.3 52.3)", 0.01);
 308 }
 309
 310
 311 int test_main(int, char* [])
 312 {
 313     // Integer compiles, but simplify-process fails (due to distances)
 314     //test_all<bg::model::d2::point_xy<int> >();
 315
 316     test_all<bg::model::d2::point_xy<double> >();
 317
 318 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
 319
 320     test_all<bg::model::d2::point_xy<float> >();
 321
 322     test_3d<bg::model::point<double, 3, bg::cs::cartesian> >();
 323
 324     test_spherical<bg::model::point<double, 2, bg::cs::spherical_equatorial<bg::degree> > >();
 325
 326     test_zigzag<bg::model::d2::point_xy<double> >();
 327
 328 #endif
 329
 330
 331     return 0;
 332 }