ceph/src/boost/libs/geometry/test/algorithms/set_operations/difference/test_difference.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   5
   6 // This file was modified by Oracle on 2016.
   7 // Modifications copyright (c) 2016, Oracle and/or its affiliates.
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_TEST_DIFFERENCE_HPP
  15 #define BOOST_GEOMETRY_TEST_DIFFERENCE_HPP
  16
  17 #include <fstream>
  18 #include <iomanip>
  19
  20 #include <geometry_test_common.hpp>
  21 #include "../setop_output_type.hpp"
  22
  23 #include <boost/core/ignore_unused.hpp>
  24 #include <boost/foreach.hpp>
  25
  26 #include <boost/range/algorithm/copy.hpp>
  27
  28 #include <boost/geometry/algorithms/correct.hpp>
  29 #include <boost/geometry/algorithms/difference.hpp>
  30 #include <boost/geometry/algorithms/sym_difference.hpp>
  31
  32 #include <boost/geometry/algorithms/area.hpp>
  33 #include <boost/geometry/algorithms/is_valid.hpp>
  34 #include <boost/geometry/algorithms/length.hpp>
  35 #include <boost/geometry/algorithms/num_points.hpp>
  36 #include <boost/geometry/algorithms/num_interior_rings.hpp>
  37 #include <boost/geometry/algorithms/remove_spikes.hpp>
  38
  39 #include <boost/geometry/geometries/geometries.hpp>
  40
  41
  42 #include <boost/geometry/geometries/multi_point.hpp>
  43 #include <boost/geometry/geometries/multi_linestring.hpp>
  44 #include <boost/geometry/geometries/multi_polygon.hpp>
  45
  46 #include <boost/geometry/strategies/strategies.hpp>
  47
  48 #include <boost/geometry/io/wkt/wkt.hpp>
  49
  50
  51 #if defined(TEST_WITH_SVG)
  52 #  define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER
  53 #  define BOOST_GEOMETRY_DEBUG_IDENTIFIER
  54 #  include <boost/geometry/io/svg/svg_mapper.hpp>
  55 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  56 #endif
  57
  58
  59 struct ut_settings
  60 {
  61     double percentage;
  62     bool sym_difference;
  63     bool remove_spikes;
  64
  65     bool test_validity;
  66
  67     ut_settings()
  68         : percentage(0.0001)
  69         , sym_difference(true)
  70         , remove_spikes(false)
  71         , test_validity(true)
  72     {}
  73
  74 };
  75
  76 inline ut_settings tolerance(double percentage)
  77 {
  78     ut_settings result;
  79     result.percentage = percentage;
  80     return result;
  81 }
  82
  83
  84 template <typename Output, typename G1, typename G2>
  85 void difference_output(std::string const& caseid, G1 const& g1, G2 const& g2, Output const& output)
  86 {
  87     boost::ignore_unused(caseid, g1, g2, output);
  88
  89 #if defined(TEST_WITH_SVG)
  90     {
  91         typedef typename bg::coordinate_type<G1>::type coordinate_type;
  92         typedef typename bg::point_type<G1>::type point_type;
  93
  94         std::ostringstream filename;
  95         filename << "difference_"
  96             << caseid << "_"
  97             << string_from_type<coordinate_type>::name()
  98 #if defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
  99             << "_no_rob"
 100 #endif
 101             << ".svg";
 102
 103         std::ofstream svg(filename.str().c_str());
 104
 105         bg::svg_mapper<point_type> mapper(svg, 500, 500);
 106
 107         mapper.add(g1);
 108         mapper.add(g2);
 109
 110         mapper.map(g1, "fill-opacity:0.3;fill:rgb(51,51,153);stroke:rgb(51,51,153);stroke-width:3");
 111         mapper.map(g2, "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:3");
 112
 113
 114         for (typename Output::const_iterator it = output.begin(); it != output.end(); ++it)
 115         {
 116             mapper.map(*it,
 117                 //sym ? "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,255,0);stroke:rgb(255,0,255);stroke-width:8" :
 118                 "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);stroke:rgb(255,0,255);stroke-width:8");
 119         }
 120     }
 121 #endif
 122 }
 123
 124 template <typename OutputType, typename G1, typename G2>
 125 std::string test_difference(std::string const& caseid, G1 const& g1, G2 const& g2,
 126         int expected_count, int expected_rings_count, int expected_point_count,
 127         double expected_area,
 128         bool sym,
 129         ut_settings const& settings)
 130 {
 131     typedef typename bg::coordinate_type<G1>::type coordinate_type;
 132     boost::ignore_unused<coordinate_type>();
 133
 134     bg::model::multi_polygon<OutputType> result;
 135
 136     if (sym)
 137     {
 138         bg::sym_difference(g1, g2, result);
 139     }
 140     else
 141     {
 142         bg::difference(g1, g2, result);
 143     }
 144
 145     if (settings.remove_spikes)
 146     {
 147         bg::remove_spikes(result);
 148     }
 149
 150     std::ostringstream return_string;
 151     return_string << bg::wkt(result);
 152
 153     typename bg::default_area_result<G1>::type const area = bg::area(result);
 154     std::size_t const n = expected_point_count >= 0
 155                           ? bg::num_points(result) : 0;
 156
 157 #if ! defined(BOOST_GEOMETRY_NO_BOOST_TEST)
 158     if (settings.test_validity)
 159     {
 160         // std::cout << bg::dsv(result) << std::endl;
 161         std::string message;
 162         bool const valid = bg::is_valid(result, message);
 163         BOOST_CHECK_MESSAGE(valid,
 164             "difference: " << caseid << " not valid " << message);
 165     }
 166 #endif
 167
 168     difference_output(caseid, g1, g2, result);
 169
 170 #ifndef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 171     {
 172         // Test inserter functionality
 173         // Test if inserter returns output-iterator (using Boost.Range copy)
 174         typedef typename bg::point_type<G1>::type point_type;
 175         typedef typename bg::rescale_policy_type<point_type>::type
 176             rescale_policy_type;
 177
 178         rescale_policy_type rescale_policy
 179                 = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
 180
 181         typename setop_output_type<OutputType>::type
 182             inserted, array_with_one_empty_geometry;
 183         array_with_one_empty_geometry.push_back(OutputType());
 184         if (sym)
 185         {
 186             boost::copy(array_with_one_empty_geometry,
 187                 bg::detail::sym_difference::sym_difference_insert<OutputType>
 188                     (g1, g2, rescale_policy, std::back_inserter(inserted)));
 189         }
 190         else
 191         {
 192             boost::copy(array_with_one_empty_geometry,
 193                 bg::detail::difference::difference_insert<OutputType>(
 194                     g1, g2, rescale_policy, std::back_inserter(inserted)));
 195         }
 196
 197         BOOST_CHECK_EQUAL(boost::size(result), boost::size(inserted) - 1);
 198     }
 199 #endif
 200
 201
 202
 203 #if ! defined(BOOST_GEOMETRY_NO_BOOST_TEST)
 204     if (expected_point_count >= 0)
 205     {
 206         BOOST_CHECK_MESSAGE(bg::math::abs(int(n) - expected_point_count) < 3,
 207                 "difference: " << caseid
 208                 << " #points expected: " << expected_point_count
 209                 << " detected: " << n
 210                 << " type: " << (type_for_assert_message<G1, G2>())
 211                 );
 212     }
 213
 214     if (expected_count >= 0)
 215     {
 216         BOOST_CHECK_MESSAGE(int(result.size()) == expected_count,
 217                 "difference: " << caseid
 218                 << " #outputs expected: " << expected_count
 219                 << " detected: " << result.size()
 220                 << " type: " << (type_for_assert_message<G1, G2>())
 221                 );
 222     }
 223
 224     if (expected_rings_count >= 0)
 225     {
 226         int nrings = expected_count + bg::num_interior_rings(result);
 227         BOOST_CHECK_MESSAGE(nrings == expected_rings_count,
 228                 "difference: " << caseid
 229                 << " #rings expected: " << expected_rings_count
 230                 << " detected: " << nrings
 231                 << " type: " << (type_for_assert_message<G1, G2>())
 232                 );
 233     }
 234
 235     BOOST_CHECK_CLOSE(area, expected_area, settings.percentage);
 236 #endif
 237
 238
 239     return return_string.str();
 240 }
 241
 242 template <typename OutputType, typename G1, typename G2>
 243 std::string test_difference(std::string const& caseid, G1 const& g1, G2 const& g2,
 244         int expected_count, int expected_point_count,
 245         double expected_area,
 246         bool sym,
 247         ut_settings const& settings)
 248 {
 249     return test_difference<OutputType>(caseid, g1, g2,
 250         expected_count, -1, expected_point_count, expected_area,
 251         sym, settings);
 252 }
 253
 254 #ifdef BOOST_GEOMETRY_CHECK_WITH_POSTGIS
 255 static int counter = 0;
 256 #endif
 257
 258
 259 template <typename OutputType, typename G1, typename G2>
 260 std::string test_one(std::string const& caseid,
 261         std::string const& wkt1, std::string const& wkt2,
 262         int expected_count1,
 263         int expected_rings_count1,
 264         int expected_point_count1,
 265         double expected_area1,
 266         int expected_count2,
 267         int expected_rings_count2,
 268         int expected_point_count2,
 269         double expected_area2,
 270         int expected_count_s,
 271         int expected_rings_count_s,
 272         int expected_point_count_s,
 273         double expected_area_s,
 274         ut_settings const& settings = ut_settings())
 275 {
 276     G1 g1;
 277     bg::read_wkt(wkt1, g1);
 278
 279     G2 g2;
 280     bg::read_wkt(wkt2, g2);
 281
 282     bg::correct(g1);
 283     bg::correct(g2);
 284
 285     std::string result = test_difference<OutputType>(caseid + "_a", g1, g2,
 286         expected_count1, expected_rings_count1, expected_point_count1,
 287         expected_area1, false, settings);
 288
 289 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 290     return result;
 291 #endif
 292
 293     test_difference<OutputType>(caseid + "_b", g2, g1,
 294         expected_count2, expected_rings_count2, expected_point_count2,
 295         expected_area2, false, settings);
 296
 297     if (settings.sym_difference)
 298     {
 299         test_difference<OutputType>(caseid + "_s", g1, g2,
 300             expected_count_s,
 301             expected_rings_count_s,
 302             expected_point_count_s,
 303             expected_area_s,
 304             true, settings);
 305     }
 306     return result;
 307 }
 308
 309 template <typename OutputType, typename G1, typename G2>
 310 std::string test_one(std::string const& caseid,
 311         std::string const& wkt1, std::string const& wkt2,
 312         int expected_count1,
 313         int expected_rings_count1,
 314         int expected_point_count1,
 315         double expected_area1,
 316         int expected_count2,
 317         int expected_rings_count2,
 318         int expected_point_count2,
 319         double expected_area2,
 320         ut_settings const& settings = ut_settings())
 321 {
 322     return test_one<OutputType, G1, G2>(caseid, wkt1, wkt2,
 323         expected_count1, expected_rings_count1, expected_point_count1, expected_area1,
 324         expected_count2, expected_rings_count2, expected_point_count2, expected_area2,
 325         expected_count1 + expected_count2,
 326         expected_rings_count1 + expected_rings_count2,
 327         expected_point_count1 >= 0 && expected_point_count2 >= 0
 328             ? (expected_point_count1 + expected_point_count2) : -1,
 329         expected_area1 + expected_area2,
 330         settings);
 331 }
 332
 333 template <typename OutputType, typename G1, typename G2>
 334 std::string test_one(std::string const& caseid,
 335         std::string const& wkt1, std::string const& wkt2,
 336         int expected_count1,
 337         int expected_point_count1,
 338         double expected_area1,
 339         int expected_count2,
 340         int expected_point_count2,
 341         double expected_area2,
 342         int expected_count_s,
 343         int expected_point_count_s,
 344         double expected_area_s,
 345         ut_settings const& settings = ut_settings())
 346 {
 347     return test_one<OutputType, G1, G2>(caseid, wkt1, wkt2,
 348         expected_count1, -1, expected_point_count1, expected_area1,
 349         expected_count2, -1, expected_point_count2, expected_area2,
 350         expected_count_s, -1, expected_point_count_s, expected_area_s,
 351         settings);
 352 }
 353
 354 template <typename OutputType, typename G1, typename G2>
 355 std::string test_one(std::string const& caseid,
 356         std::string const& wkt1, std::string const& wkt2,
 357         int expected_count1,
 358         int expected_point_count1,
 359         double expected_area1,
 360         int expected_count2,
 361         int expected_point_count2,
 362         double expected_area2,
 363         ut_settings const& settings = ut_settings())
 364 {
 365     return test_one<OutputType, G1, G2>(caseid, wkt1, wkt2,
 366         expected_count1, expected_point_count1, expected_area1,
 367         expected_count2, expected_point_count2, expected_area2,
 368         expected_count1 + expected_count2,
 369         expected_point_count1 >= 0 && expected_point_count2 >= 0
 370             ? (expected_point_count1 + expected_point_count2) : -1,
 371         expected_area1 + expected_area2,
 372         settings);
 373 }
 374
 375 template <typename OutputType, typename G1, typename G2>
 376 void test_one_lp(std::string const& caseid,
 377         std::string const& wkt1, std::string const& wkt2,
 378         std::size_t expected_count,
 379         int expected_point_count,
 380         double expected_length)
 381 {
 382     G1 g1;
 383     bg::read_wkt(wkt1, g1);
 384
 385     G2 g2;
 386     bg::read_wkt(wkt2, g2);
 387
 388     bg::correct(g1);
 389
 390     typedef typename setop_output_type<OutputType>::type result_type;
 391     result_type pieces;
 392     bg::difference(g1, g2, pieces);
 393
 394     typename bg::default_length_result<G1>::type length = 0;
 395     std::size_t n = 0;
 396     std::size_t piece_count = 0;
 397     for (typename result_type::iterator it = pieces.begin();
 398             it != pieces.end();
 399             ++it)
 400     {
 401         if (expected_point_count >= 0)
 402         {
 403             n += bg::num_points(*it);
 404         }
 405         piece_count++;
 406         length += bg::length(*it);
 407     }
 408
 409     BOOST_CHECK_MESSAGE(piece_count == expected_count,
 410             "difference: " << caseid
 411             << " #outputs expected: " << expected_count
 412             << " detected: " << pieces.size()
 413             );
 414
 415     if (expected_point_count >= 0)
 416     {
 417         BOOST_CHECK_MESSAGE(n == std::size_t(expected_point_count),
 418                 "difference: " << caseid
 419                 << " #points expected: " << std::size_t(expected_point_count)
 420                 << " detected: " << n
 421                 << " type: " << (type_for_assert_message<G1, G2>())
 422                 );
 423     }
 424
 425     BOOST_CHECK_CLOSE(length, expected_length, 0.001);
 426
 427     std::string lp = "lp_";
 428     difference_output(lp + caseid, g1, g2, pieces);
 429 }
 430
 431
 432 #endif