libs/geometry/test/strategies/douglas_peucker.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2015, Oracle and/or its affiliates.
   5
   6 // Contributed and/or modified by Menelaos Karavelas, 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 #ifndef BOOST_TEST_MODULE
  12 #define BOOST_TEST_MODULE test_douglas_peucker
  13 #endif
  14
  15 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  16 #ifndef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
  17 #define BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
  18 #endif
  19 #endif
  20
  21 #include <iostream>
  22 #include <iterator>
  23 #include <sstream>
  24 #include <string>
  25
  26 #include <boost/test/included/unit_test.hpp>
  27
  28 #include <boost/geometry/core/point_type.hpp>
  29 #include <boost/geometry/core/tags.hpp>
  30
  31 #include <boost/geometry/strategies/distance.hpp>
  32 #include <boost/geometry/strategies/strategies.hpp>
  33
  34 #include <boost/geometry/geometries/geometries.hpp>
  35 #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
  36 #include <boost/geometry/geometries/register/multi_point.hpp>
  37
  38 #include <boost/geometry/algorithms/comparable_distance.hpp>
  39 #include <boost/geometry/algorithms/equals.hpp>
  40
  41 #include <boost/geometry/io/wkt/wkt.hpp>
  42 #include <boost/geometry/io/dsv/write.hpp>
  43
  44 #include <boost/assign/list_of.hpp>
  45 #include <boost/core/ignore_unused.hpp>
  46 #include <boost/type_traits/is_same.hpp>
  47 #include <boost/tuple/tuple.hpp>
  48
  49
  50 namespace bg = ::boost::geometry;
  51 namespace ba = ::boost::assign;
  52 namespace services = bg::strategy::distance::services;
  53
  54 typedef boost::tuple<double, double> tuple_point_type;
  55 typedef std::vector<tuple_point_type> tuple_multi_point_type;
  56
  57 BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
  58 BOOST_GEOMETRY_REGISTER_MULTI_POINT(tuple_multi_point_type)
  59 BOOST_GEOMETRY_REGISTER_MULTI_POINT_TEMPLATED(std::vector)
  60
  61 typedef bg::strategy::distance::projected_point<> distance_strategy_type;
  62 typedef bg::strategy::distance::projected_point
  63     <
  64         void, bg::strategy::distance::comparable::pythagoras<>
  65     > comparable_distance_strategy_type;
  66
  67
  68 template <typename CoordinateType>
  69 struct default_simplify_strategy
  70 {
  71     typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
  72     typedef typename bg::strategy::distance::services::default_strategy
  73         <
  74             bg::point_tag, bg::segment_tag, point_type
  75         >::type default_distance_strategy_type;
  76
  77     typedef bg::strategy::simplify::douglas_peucker
  78         <
  79             point_type, default_distance_strategy_type
  80         > type;
  81 };
  82
  83
  84 template <typename CoordinateType>
  85 struct simplify_regular_distance_strategy
  86 {
  87     typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
  88     typedef bg::strategy::simplify::douglas_peucker
  89         <
  90             point_type, distance_strategy_type
  91         > type;
  92 };
  93
  94 template <typename CoordinateType>
  95 struct simplify_comparable_distance_strategy
  96 {
  97     typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
  98     typedef bg::strategy::simplify::douglas_peucker
  99         <
 100             point_type, comparable_distance_strategy_type
 101         > type;
 102 };
 103
 104
 105
 106 template <typename Geometry>
 107 inline Geometry from_wkt(std::string const& wkt)
 108 {
 109     Geometry geometry;
 110     boost::geometry::read_wkt(wkt, geometry);
 111     return geometry;
 112 }
 113
 114 template <typename Iterator>
 115 inline std::ostream& print_point_range(std::ostream& os,
 116                                        Iterator first,
 117                                        Iterator beyond,
 118                                        std::string const& header)
 119 {
 120     os << header << "(";
 121     for (Iterator it = first; it != beyond; ++it)
 122     {
 123         os << " " << bg::dsv(*it);
 124     }
 125     os << " )";
 126     return os;
 127 }
 128
 129
 130 struct equals
 131 {
 132     template <typename Iterator1, typename Iterator2>
 133     static inline bool apply(Iterator1 begin1, Iterator1 end1,
 134                              Iterator2 begin2, Iterator2 end2)
 135     {
 136         std::size_t num_points1 = std::distance(begin1, end1);
 137         std::size_t num_points2 = std::distance(begin2, end2);
 138
 139         if ( num_points1 != num_points2 )
 140         {
 141             return false;
 142         }
 143
 144         Iterator1 it1 = begin1;
 145         Iterator2 it2 = begin2;
 146         for (; it1 != end1; ++it1, ++it2)
 147         {
 148             if ( !bg::equals(*it1, *it2) )
 149             {
 150                 return false;
 151             }
 152         }
 153         return true;
 154     }
 155
 156     template <typename Range1, typename Range2>
 157     static inline bool apply(Range1 const& range1, Range2 const& range2)
 158     {
 159         return apply(boost::begin(range1), boost::end(range1),
 160                      boost::begin(range2), boost::end(range2));
 161     }
 162 };
 163
 164
 165
 166
 167 template <typename Geometry>
 168 struct test_one_case
 169 {
 170     template <typename Strategy, typename Range>
 171     static inline void apply(std::string const& case_id,
 172                              std::string const& wkt,
 173                              double max_distance,
 174                              Strategy const& strategy,
 175                              Range const& expected_result)
 176     {
 177         typedef typename bg::point_type<Geometry>::type point_type;
 178         std::vector<point_type> result;
 179
 180         Geometry geometry = from_wkt<Geometry>(wkt);
 181
 182         std::string typeid_name
 183             = typeid(typename bg::coordinate_type<point_type>::type).name();
 184
 185 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 186         std::cout << case_id << " - " << typeid_name
 187                   << std::endl;
 188         std::cout << wkt << std::endl;
 189 #endif
 190
 191         strategy.apply(geometry, std::back_inserter(result), max_distance);
 192
 193         boost::ignore_unused(strategy);
 194
 195 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 196         print_point_range(std::cout, boost::begin(result), boost::end(result),
 197                           "output: ");
 198         std::cout << std::endl << std::endl;
 199 #endif
 200         std::stringstream stream_expected;
 201         print_point_range(stream_expected, boost::begin(expected_result),
 202                           boost::end(expected_result),
 203                           "");
 204         std::stringstream stream_detected;
 205         print_point_range(stream_detected, boost::begin(result),
 206                           boost::end(result),
 207                           "");
 208
 209         BOOST_CHECK_MESSAGE(equals::apply(result, expected_result),
 210                             "case id: " << case_id << " - " << typeid_name
 211                             << ", geometry: " << wkt
 212                             << ", Expected: " << stream_expected.str()
 213                             << " - Detected: " << stream_detected.str());
 214
 215 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 216         std::cout << "---------------" << std::endl;
 217         std::cout << "---------------" << std::endl;
 218         std::cout << std::endl << std::endl;
 219 #endif
 220     }
 221 };
 222
 223
 224 template <typename CoordinateType, typename Strategy>
 225 inline void test_with_strategy(std::string label)
 226 {
 227     std::cout.precision(20);
 228     Strategy strategy;
 229
 230     typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
 231     typedef bg::model::linestring<point_type> linestring_type;
 232     typedef bg::model::segment<point_type> segment_type;
 233     typedef test_one_case<linestring_type> tester;
 234
 235     label = " (" + label + ")";
 236
 237     {
 238         point_type const p1(-6,-13), p2(0,-15);
 239         segment_type const s(point_type(12,-3), point_type(-12,5));
 240
 241         if (bg::comparable_distance(p1, s) >= bg::comparable_distance(p2, s))
 242         {
 243             tester::apply("l01c1" + label,
 244                           "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -15,-12 5)",
 245                           10,
 246                           strategy,
 247                           ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-12,5)
 248                           );
 249         }
 250         else
 251         {
 252             tester::apply("l01c2" + label,
 253                           "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -15,-12 5)",
 254                           10,
 255                           strategy,
 256                           ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-9,4)(0,-15)(-12,5)
 257                           );
 258         }
 259     }
 260
 261     tester::apply("l02" + label,
 262                   "LINESTRING(-6 -13,-9 4,0 -15,-12 5)",
 263                   10,
 264                   strategy,
 265                   ba::tuple_list_of(-6,-13)(-12,5)
 266                   );
 267
 268     tester::apply("l03" + label,
 269                   "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -14,-12 5)",
 270                   10,
 271                   strategy,
 272                   ba::tuple_list_of(12,-3)(4,8)(-6,-13)(-12,5)
 273                   );
 274
 275     tester::apply("l04" + label,
 276                   "LINESTRING(12 -3, 4 8,-6 -13,-9 4,0 -14,-12 5)",
 277                   14,
 278                   strategy,
 279                   ba::tuple_list_of(12,-3)(-6,-13)(-12,5)
 280                   );
 281
 282     {
 283         segment_type const s(point_type(0,-1), point_type(5,-4));
 284         point_type const p1(5,-1), p2(0,-4);
 285
 286 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 287         bool d_larger_first = (bg::distance(p1, s) > bg::distance(p2, s));
 288         bool d_larger_second = (bg::distance(p1, s) < bg::distance(p2, s));
 289         bool cd_larger_first
 290             = (bg::comparable_distance(p1, s) > bg::comparable_distance(p2, s));
 291         bool cd_larger_second
 292             = (bg::comparable_distance(p1, s) < bg::comparable_distance(p2, s));
 293
 294         std::cout << "segment: " << bg::dsv(s) << std::endl;
 295         std::cout << "distance from " << bg::dsv(p1) << ": "
 296                   << bg::distance(p1, s) << std::endl;
 297         std::cout << "comp. distance from " << bg::dsv(p1) << ": "
 298                   << bg::comparable_distance(p1, s) << std::endl;
 299         std::cout << "distance from " << bg::dsv(p2) << ": "
 300                   << bg::distance(p2, s) << std::endl;
 301         std::cout << "comp. distance from " << bg::dsv(p2) << ": "
 302                   << bg::comparable_distance(p2, s) << std::endl;
 303         std::cout << "larger distance from "
 304                   << (d_larger_first ? "first" : (d_larger_second ? "second" : "equal"))
 305                   << std::endl;
 306         std::cout << "larger comp. distance from "
 307                   << (cd_larger_first ? "first" : (cd_larger_second ? "second" : "equal"))
 308                   << std::endl;
 309         std::cout << "difference of distances: "
 310                   << (bg::distance(p1, s) - bg::distance(p2, s))
 311                   << std::endl;
 312         std::cout << "difference of comp. distances: "
 313                   << (bg::comparable_distance(p1, s) - bg::comparable_distance(p2, s))
 314                   << std::endl;
 315 #endif
 316
 317         std::string wkt =
 318             "LINESTRING(0 0,5 0,0 -1,5 -1,0 -2,5 -2,0 -3,5 -3,0 -4,5 -4,0 0)";
 319
 320         if (bg::comparable_distance(p1, s) >= bg::comparable_distance(p2, s))
 321         {
 322             tester::apply("l05c1" + label,
 323                           wkt,
 324                           1,
 325                           strategy,
 326                           ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-2)(0,-3)(5,-4)(0,0)
 327                           );
 328             tester::apply("l05c1a" + label,
 329                           wkt,
 330                           2,
 331                           strategy,
 332                           ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-4)(0,0)
 333                           );
 334         }
 335         else
 336         {
 337             tester::apply("l05c2" + label,
 338                           wkt,
 339                           1,
 340                           strategy,
 341                           ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-2)(5,-2)(0,-4)(5,-4)(0,0)
 342                           );
 343             tester::apply("l05c2a" + label,
 344                           wkt,
 345                           2,
 346                           strategy,
 347                           ba::tuple_list_of(0,0)(5,0)(0,-1)(5,-1)(0,-4)(5,-4)(0,0)
 348                           );
 349         }
 350     }
 351
 352 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 353     std::cout << std::endl;
 354     std::cout << std::endl;
 355     std::cout << "*************************************************";
 356     std::cout << std::endl;
 357     std::cout << std::endl;
 358 #endif
 359 }
 360
 361
 362 BOOST_AUTO_TEST_CASE( test_default_strategy )
 363 {
 364     test_with_strategy<int, default_simplify_strategy<int>::type>("i");
 365     test_with_strategy<float, default_simplify_strategy<float>::type>("f");
 366     test_with_strategy<double, default_simplify_strategy<double>::type>("d");
 367     test_with_strategy
 368         <
 369             long double,
 370             default_simplify_strategy<long double>::type
 371         >("ld");
 372 }
 373
 374 BOOST_AUTO_TEST_CASE( test_with_regular_distance_strategy )
 375 {
 376     test_with_strategy
 377         <
 378             int,
 379             simplify_regular_distance_strategy<int>::type
 380         >("i");
 381
 382     test_with_strategy
 383         <
 384             float,
 385             simplify_regular_distance_strategy<float>::type
 386         >("f");
 387
 388     test_with_strategy
 389         <
 390             double,
 391             simplify_regular_distance_strategy<double>::type
 392         >("d");
 393     test_with_strategy
 394         <
 395             long double,
 396             simplify_regular_distance_strategy<long double>::type
 397         >("ld");
 398 }
 399
 400 BOOST_AUTO_TEST_CASE( test_with_comparable_distance_strategy )
 401 {
 402     test_with_strategy
 403         <
 404             int,
 405             simplify_comparable_distance_strategy<int>::type
 406         >("i");
 407     test_with_strategy
 408         <
 409             float,
 410             simplify_comparable_distance_strategy<float>::type
 411         >("f");
 412     test_with_strategy
 413         <
 414             double,
 415             simplify_comparable_distance_strategy<double>::type
 416         >("d");
 417     test_with_strategy
 418         <
 419             long double,
 420             simplify_comparable_distance_strategy<long double>::type
 421         >("ld");
 422 }