libs/geometry/test/algorithms/set_operations/intersection/test_intersection.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, 2017.
   7 // Modifications copyright (c) 2016-2017, 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_INTERSECTION_HPP
  15 #define BOOST_GEOMETRY_TEST_INTERSECTION_HPP
  16
  17 #include <fstream>
  18 #include <iomanip>
  19
  20 #include <boost/foreach.hpp>
  21 #include <boost/variant/variant.hpp>
  22
  23 #include <boost/geometry/algorithms/intersection.hpp>
  24 #include <boost/geometry/algorithms/area.hpp>
  25 #include <boost/geometry/algorithms/correct.hpp>
  26 #include <boost/geometry/algorithms/is_valid.hpp>
  27 #include <boost/geometry/algorithms/length.hpp>
  28 #include <boost/geometry/algorithms/num_points.hpp>
  29 #include <boost/geometry/algorithms/num_interior_rings.hpp>
  30
  31 #include <boost/geometry/geometries/geometries.hpp>
  32
  33 #include <boost/geometry/strategies/strategies.hpp>
  34
  35 #include <boost/geometry/io/wkt/wkt.hpp>
  36
  37
  38 #if defined(TEST_WITH_SVG)
  39 #  include <boost/geometry/io/svg/svg_mapper.hpp>
  40 #endif
  41
  42 #include <geometry_test_common.hpp>
  43 #include <algorithms/check_validity.hpp>
  44 #include "../setop_output_type.hpp"
  45
  46 struct ut_settings
  47 {
  48     double percentage;
  49     bool test_validity;
  50     bool debug;
  51
  52     explicit ut_settings(double p = 0.0001, bool tv = true)
  53         : percentage(p)
  54         , test_validity(tv)
  55         , debug(false)
  56     {}
  57
  58 };
  59
  60 template<typename IntersectionOutput, typename G1, typename G2>
  61 void check_result(IntersectionOutput const& intersection_output,
  62     std::string const& caseid,
  63     G1 const& g1, G2 const& g2,
  64     std::size_t expected_count, std::size_t expected_holes_count,
  65     int expected_point_count, double expected_length_or_area,
  66     ut_settings const& settings)
  67 {
  68     typedef typename boost::range_value<IntersectionOutput>::type OutputType;
  69     bool const is_line = bg::geometry_id<OutputType>::type::value == 2;
  70
  71     typename bg::default_area_result<G1>::type length_or_area = 0;
  72     int n = 0;
  73     std::size_t nholes = 0;
  74     for (typename IntersectionOutput::const_iterator it = intersection_output.begin();
  75             it != intersection_output.end();
  76             ++it)
  77     {
  78         if (expected_point_count > 0)
  79         {
  80             // here n should rather be of type std::size_t, but expected_point_count
  81             // is set to -1 in some test cases so type int was left for now
  82             n += static_cast<int>(bg::num_points(*it, true));
  83         }
  84
  85         if (expected_holes_count > 0)
  86         {
  87             nholes += bg::num_interior_rings(*it);
  88         }
  89
  90         // instead of specialization we check it run-time here
  91         length_or_area += is_line
  92             ? bg::length(*it)
  93             : bg::area(*it);
  94
  95         if (settings.debug)
  96         {
  97             std::cout << std::setprecision(20) << bg::wkt(*it) << std::endl;
  98         }
  99     }
 100
 101 #if ! defined(BOOST_GEOMETRY_TEST_ALWAYS_CHECK_VALIDITY)
 102     if (settings.test_validity)
 103 #endif
 104     {
 105         std::string message;
 106         bool const valid = check_validity<IntersectionOutput>
 107                 ::apply(intersection_output, caseid, g1, g2, message);
 108
 109         BOOST_CHECK_MESSAGE(valid,
 110             "intersection: " << caseid << " not valid: " << message
 111             << " type: " << (type_for_assert_message<G1, G2>()));
 112     }
 113
 114 #if ! defined(BOOST_GEOMETRY_NO_BOOST_TEST)
 115 #if defined(BOOST_GEOMETRY_USE_RESCALING)
 116     // Without rescaling, point count might easily differ (which is no problem)
 117     if (expected_point_count > 0)
 118     {
 119         BOOST_CHECK_MESSAGE(bg::math::abs(n - expected_point_count) < 3,
 120                 "intersection: " << caseid
 121                 << " #points expected: " << expected_point_count
 122                 << " detected: " << n
 123                 << " type: " << (type_for_assert_message<G1, G2>())
 124                 );
 125     }
 126 #endif
 127
 128     if (expected_count > 0)
 129     {
 130         BOOST_CHECK_MESSAGE(intersection_output.size() == expected_count,
 131                 "intersection: " << caseid
 132                 << " #outputs expected: " << expected_count
 133                 << " detected: " << intersection_output.size()
 134                 << " type: " << (type_for_assert_message<G1, G2>())
 135                 );
 136     }
 137
 138     if (expected_holes_count > 0)
 139     {
 140
 141         BOOST_CHECK_MESSAGE(nholes == expected_holes_count,
 142             "intersection: " << caseid
 143             << " #holes expected: " << expected_holes_count
 144             << " detected: " << nholes
 145             << " type: " << (type_for_assert_message<G1, G2>())
 146         );
 147     }
 148
 149     double const detected_length_or_area = boost::numeric_cast<double>(length_or_area);
 150     if (settings.percentage > 0.0)
 151     {
 152         if (expected_length_or_area > 0)
 153         {
 154             BOOST_CHECK_CLOSE(detected_length_or_area, expected_length_or_area, settings.percentage);
 155         }
 156         else
 157         {
 158             // Compare 0 with 0 or a very small detected area
 159             BOOST_CHECK_LE(detected_length_or_area, settings.percentage);
 160         }
 161     }
 162     else
 163     {
 164         // In some cases (geos_2) the intersection is either 0, or a tiny rectangle,
 165         // depending on compiler/settings. That cannot be tested by CLOSE
 166         BOOST_CHECK_LE(detected_length_or_area, expected_length_or_area);
 167     }
 168 #endif
 169
 170 }
 171
 172
 173 template <typename OutputType, typename CalculationType, typename G1, typename G2>
 174 typename bg::default_area_result<G1>::type test_intersection(std::string const& caseid,
 175         G1 const& g1, G2 const& g2,
 176         std::size_t expected_count = 0, std::size_t expected_holes_count = 0,
 177         int expected_point_count = 0, double expected_length_or_area = 0,
 178         ut_settings const& settings = ut_settings())
 179 {
 180     if (settings.debug)
 181     {
 182         std::cout << std::endl << "case " << caseid << std::endl;
 183     }
 184
 185     typedef typename setop_output_type<OutputType>::type result_type;
 186
 187     typedef typename bg::point_type<G1>::type point_type;
 188     boost::ignore_unused<point_type>();
 189
 190 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
 191     if (! settings.debug)
 192     {
 193         // Check _inserter behaviour with stratey
 194         typedef typename bg::strategy::intersection::services::default_strategy
 195             <
 196                 typename bg::cs_tag<point_type>::type
 197             >::type strategy_type;
 198         result_type clip;
 199         bg::detail::intersection::intersection_insert<OutputType>(g1, g2, std::back_inserter(clip), strategy_type());
 200     }
 201 #endif
 202
 203     typename bg::default_area_result<G1>::type length_or_area = 0;
 204
 205     // Check normal behaviour
 206     result_type intersection_output;
 207     bg::intersection(g1, g2, intersection_output);
 208
 209     check_result(intersection_output, caseid, g1, g2, expected_count,
 210         expected_holes_count, expected_point_count, expected_length_or_area,
 211         settings);
 212
 213 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
 214     // Check variant behaviour
 215     intersection_output.clear();
 216     bg::intersection(boost::variant<G1>(g1), g2, intersection_output);
 217
 218     check_result(intersection_output, caseid, g1, g2, expected_count,
 219         expected_holes_count, expected_point_count, expected_length_or_area,
 220         settings);
 221
 222     intersection_output.clear();
 223     bg::intersection(g1, boost::variant<G2>(g2), intersection_output);
 224
 225     check_result(intersection_output, caseid, g1, g2, expected_count,
 226         expected_holes_count, expected_point_count, expected_length_or_area,
 227         settings);
 228
 229     intersection_output.clear();
 230     bg::intersection(boost::variant<G1>(g1), boost::variant<G2>(g2), intersection_output);
 231
 232     check_result(intersection_output, caseid, g1, g2, expected_count,
 233         expected_holes_count, expected_point_count, expected_length_or_area,
 234         settings);
 235 #endif
 236
 237 #if defined(TEST_WITH_SVG)
 238     {
 239         bool const is_line = bg::geometry_id<OutputType>::type::value == 2;
 240         typedef typename bg::coordinate_type<G1>::type coordinate_type;
 241
 242         bool const ccw =
 243             bg::point_order<G1>::value == bg::counterclockwise
 244             || bg::point_order<G2>::value == bg::counterclockwise;
 245         bool const open =
 246             bg::closure<G1>::value == bg::open
 247             || bg::closure<G2>::value == bg::open;
 248
 249         std::ostringstream filename;
 250         filename << "intersection_"
 251             << caseid << "_"
 252             << string_from_type<coordinate_type>::name()
 253             << string_from_type<CalculationType>::name()
 254             << (ccw ? "_ccw" : "")
 255             << (open ? "_open" : "")
 256 #if defined(BOOST_GEOMETRY_USE_RESCALING)
 257             << "_rescaled"
 258 #endif
 259             << ".svg";
 260
 261         std::ofstream svg(filename.str().c_str());
 262
 263         bg::svg_mapper<point_type> mapper(svg, 500, 500);
 264
 265         mapper.add(g1);
 266         mapper.add(g2);
 267
 268         mapper.map(g1, is_line
 269             ? "opacity:0.6;stroke:rgb(0,255,0);stroke-width:5"
 270             : "fill-opacity:0.5;fill:rgb(153,204,0);"
 271                     "stroke:rgb(153,204,0);stroke-width:3");
 272         mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
 273                     "stroke:rgb(51,51,153);stroke-width:3");
 274
 275         for (typename result_type::const_iterator it = intersection_output.begin();
 276                 it != intersection_output.end(); ++it)
 277         {
 278             mapper.map(*it, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
 279                         "stroke:rgb(255,0,255);stroke-width:8");
 280         }
 281     }
 282 #endif
 283
 284
 285     if (settings.debug)
 286     {
 287         std::cout << "end case " << caseid << std::endl;
 288     }
 289
 290     return length_or_area;
 291 }
 292
 293 template <typename OutputType, typename CalculationType, typename G1, typename G2>
 294 typename bg::default_area_result<G1>::type test_intersection(std::string const& caseid,
 295         G1 const& g1, G2 const& g2,
 296         std::size_t expected_count = 0, int expected_point_count = 0,
 297         double expected_length_or_area = 0,
 298         ut_settings const& settings = ut_settings())
 299 {
 300     return test_intersection<OutputType, CalculationType>(
 301         caseid, g1, g2, expected_count, 0, expected_point_count,
 302         expected_length_or_area, settings
 303     );
 304 }
 305
 306 template <typename OutputType, typename G1, typename G2>
 307 typename bg::default_area_result<G1>::type test_one(std::string const& caseid,
 308         std::string const& wkt1, std::string const& wkt2,
 309         std::size_t expected_count = 0, std::size_t expected_holes_count = 0,
 310         int expected_point_count = 0, double expected_length_or_area = 0,
 311         ut_settings const& settings = ut_settings())
 312 {
 313     G1 g1;
 314     bg::read_wkt(wkt1, g1);
 315
 316     G2 g2;
 317     bg::read_wkt(wkt2, g2);
 318
 319     // Reverse if necessary
 320     bg::correct(g1);
 321     bg::correct(g2);
 322
 323     return test_intersection<OutputType, void>(caseid, g1, g2,
 324         expected_count, expected_holes_count, expected_point_count,
 325         expected_length_or_area, settings);
 326 }
 327
 328 template <typename OutputType, typename G1, typename G2>
 329 typename bg::default_area_result<G1>::type test_one(std::string const& caseid,
 330     std::string const& wkt1, std::string const& wkt2,
 331     std::size_t expected_count = 0, int expected_point_count = 0,
 332     double expected_length_or_area = 0,
 333     ut_settings const& settings = ut_settings())
 334 {
 335     return test_one<OutputType, G1, G2>(caseid, wkt1, wkt2,
 336         expected_count, 0, expected_point_count,
 337         expected_length_or_area,
 338         settings);
 339 }
 340
 341 template <typename OutputType, typename Areal, typename Linear>
 342 void test_one_lp(std::string const& caseid,
 343         std::string const& wkt_areal, std::string const& wkt_linear,
 344         std::size_t expected_count = 0, int expected_point_count = 0,
 345         double expected_length = 0,
 346         ut_settings const& settings = ut_settings())
 347 {
 348 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 349     std::cout << caseid << " -- start" << std::endl;
 350 #endif
 351     Areal areal;
 352     bg::read_wkt(wkt_areal, areal);
 353     bg::correct(areal);
 354
 355     Linear linear;
 356     bg::read_wkt(wkt_linear, linear);
 357
 358     test_intersection<OutputType, void>(caseid, areal, linear,
 359         expected_count, expected_point_count,
 360         expected_length, settings);
 361
 362     // A linestring reversed should deliver exactly the same.
 363     bg::reverse(linear);
 364
 365     test_intersection<OutputType, void>(caseid + "_rev", areal, linear,
 366         expected_count, expected_point_count,
 367         expected_length, settings);
 368 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 369     std::cout << caseid << " -- end" << std::endl;
 370 #endif
 371 }
 372
 373 template <typename Geometry1, typename Geometry2>
 374 void test_point_output(std::string const& wkt1, std::string const& wkt2, unsigned int expected_count)
 375 {
 376     Geometry1 g1;
 377     bg::read_wkt(wkt1, g1);
 378     bg::correct(g1);
 379
 380     Geometry2 g2;
 381     bg::read_wkt(wkt2, g2);
 382     bg::correct(g2);
 383
 384     bg::model::multi_point<typename bg::point_type<Geometry1>::type> points;
 385     bg::intersection(g1, g2, points);
 386     BOOST_CHECK_EQUAL(points.size(), expected_count);
 387 }
 388
 389
 390 #endif