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