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     // Same which reordered coordinates
  88     test_geometry<bg::model::linestring<P> >(
  89         "LINESTRING(0 0,80 10,120 6,200 0)",
  90         "LINESTRING(0 0,80 10,200 0)", 7);
  91
  92     // Mail 2013-10-07, real-life test, piece of River Leine
  93     // PostGIS returns exactly the same result
  94     test_geometry<bg::model::linestring<P> >(
  95          "LINESTRING(4293586 3290439,4293568 3290340,4293566 3290332,4293570 3290244,4293576 3290192"
  96                    ",4293785 3289660,4293832 3289597,4293879 3289564,4293937 3289545,4294130 3289558"
  97                    ",4294204 3289553,4294240 3289539,4294301 3289479,4294317 3289420,4294311 3289353"
  98                    ",4294276 3289302,4293870 3289045,4293795 3288978,4293713 3288879,4293669 3288767"
  99                    ",4293654 3288652,4293657 3288563,4293690 3288452,4293761 3288360,4293914 3288215"
 100                    ",4293953 3288142,4293960 3288044,4293951 3287961,4293913 3287875,4293708 3287628"
 101                    ",4293658 3287542,4293633 3287459,4293630 3287383,4293651 3287323,4293697 3287271"
 102                    ",4293880 3287128,4293930 3287045,4293938 3286977,4293931 3286901,4293785 3286525"
 103                    ",4293775 3286426,4293786 3286358,4293821 3286294,4294072 3286076,4294134 3285986)",
 104           "LINESTRING(4293586 3290439,4293785 3289660,4294317 3289420,4293654 3288652,4293960 3288044"
 105                   ",4293633 3287459,4293786 3286358,4294134 3285986)", 250);
 106
 107     /* TODO fix this
 108     test_geometry<test::wrapped_boost_array<P, 10> >(
 109         "LINESTRING(0 0,5 5,7 5,10 10)",
 110         "LINESTRING(0 0,5 5,7 5,10 10)", 1.0);
 111     */
 112
 113     test_geometry<bg::model::ring<P> >(
 114         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0))",
 115         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0))", 1.0);
 116
 117     test_geometry<bg::model::polygon<P> >(
 118         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0))",
 119         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0))", 1.0);
 120
 121     test_geometry<bg::model::polygon<P> >(
 122         "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))",
 123         "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);
 124
 125 /*
 126
 127 Above can be checked in PostGIS by:
 128
 129 select astext(ST_Simplify(geomfromtext('LINESTRING(0 0, 5 5, 10 10)'),1.0)) as simplified
 130 union all select astext(ST_Simplify(geomfromtext('LINESTRING(0 0, 5 5, 6 5, 10 10)'),1.0))
 131 etc
 132 */
 133
 134     {
 135         // Test with explicit strategy
 136
 137         typedef bg::strategy::simplify::douglas_peucker
 138         <
 139             P,
 140             bg::strategy::distance::projected_point<double>
 141         > dp;
 142
 143         test_geometry<bg::model::linestring<P> >(
 144             "LINESTRING(0 0,5 5,10 10)",
 145             "LINESTRING(0 0,10 10)", 1.0, dp());
 146     }
 147
 148
 149     // POINT: check compilation
 150     test_geometry<P>(
 151         "POINT(0 0)",
 152         "POINT(0 0)", 1.0);
 153
 154
 155     // RING: check compilation and behaviour
 156     test_geometry<bg::model::ring<P> >(
 157         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,2 1,4 0))",
 158         "POLYGON((4 0,8 2,8 7,4 9,0 7,0 2,4 0))", 1.0);
 159
 160
 161 #ifdef TEST_PULL89
 162     test_with_ax<bg::model::linestring<P> >(
 163         "LINESTRING(0 0,120 6,80 10,200 0)",
 164         "LINESTRING(0 0,80 10,200 0)", 10, 7);
 165 #endif
 166 }
 167
 168 template <typename P>
 169 void test_zigzag()
 170 {
 171     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)";
 172
 173     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)";
 174     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)";
 175     static const std::string expected200 = "LINESTRING(0 10,6 2,16 1,14 2,21 8,19 7,20 13,19 11)";
 176     static const std::string expected225 = "LINESTRING(0 10,6 2,16 1,21 8,19 11)";
 177     test_geometry<bg::model::linestring<P> >(zigzag, expected100, 1.0001);
 178     test_geometry<bg::model::linestring<P> >(zigzag, expected150, 1.5001);
 179     test_geometry<bg::model::linestring<P> >(zigzag, expected200, 2.0001);
 180     test_geometry<bg::model::linestring<P> >(zigzag, expected225, 2.25); // should be larger than sqrt(5)=2.236
 181
 182 #ifdef TEST_PULL89
 183     // This should work (results might vary but should have LESS points then expected above
 184     // Small xtd, larger adt,
 185     test_with_ax<bg::model::linestring<P> >(zigzag, expected100, 1.0001, 1.0001);
 186     test_with_ax<bg::model::linestring<P> >(zigzag, expected150, 1.5001, 1.0001);
 187     test_with_ax<bg::model::linestring<P> >(zigzag, expected200, 2.0001, 1.0001);
 188     test_with_ax<bg::model::linestring<P> >(zigzag, expected225, 2.25, 1.0001);
 189 #endif
 190
 191 }
 192
 193
 194 template <typename P>
 195 void test_spherical()
 196 {
 197     test_geometry<bg::model::linestring<P> >(
 198         "LINESTRING(4.1 52.1,4.2 52.2,4.3 52.3)",
 199         "LINESTRING(4.1 52.1,4.3 52.3)", 0.01);
 200 }
 201
 202
 203 int test_main(int, char* [])
 204 {
 205     // Integer compiles, but simplify-process fails (due to distances)
 206     //test_all<bg::model::d2::point_xy<int> >();
 207
 208     test_all<bg::model::d2::point_xy<float> >();
 209     test_all<bg::model::d2::point_xy<double> >();
 210
 211     test_spherical<bg::model::point<double, 2, bg::cs::spherical_equatorial<bg::degree> > >();
 212
 213     test_zigzag<bg::model::d2::point_xy<double> >();
 214
 215 #if defined(HAVE_TTMATH)
 216     test_all<bg::model::d2::point_xy<ttmath_big> >();
 217     test_spherical<bg::model::point<ttmath_big, 2, bg::cs::spherical_equatorial<bg::degree> > >();
 218 #endif
 219
 220
 221
 222     return 0;
 223 }