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