ceph/src/boost/libs/geometry/test/algorithms/set_operations/difference/difference_areal_linear.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2010-2015 Barend Gehrels, Amsterdam, the Netherlands.
   5
   6 // This file was modified by Oracle on 2015, 2017.
   7 // Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11
  12 // Use, modification and distribution is subject to the Boost Software License,
  13 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  14 // http://www.boost.org/LICENSE_1_0.txt)
  15
  16 #include <iomanip>
  17 #include <iostream>
  18 #include <sstream>
  19 #include <string>
  20
  21 #include <boost/geometry/algorithms/correct.hpp>
  22 #include <boost/geometry/algorithms/is_valid.hpp>
  23
  24 #include <boost/geometry/io/wkt/wkt.hpp>
  25
  26 #include <boost/geometry/geometries/point_xy.hpp>
  27
  28 #include "test_difference.hpp"
  29 #include <algorithms/test_overlay.hpp>
  30 #include <algorithms/overlay/overlay_cases.hpp>
  31 #include <algorithms/overlay/multi_overlay_cases.hpp>
  32
  33
  34 #ifdef HAVE_TTMATH
  35 #  include <boost/geometry/extensions/contrib/ttmath_stub.hpp>
  36 #endif
  37
  38 template <typename CoordinateType>
  39 void test_ticket_10835(std::string const& wkt_out1, std::string const& wkt_out2)
  40 {
  41     typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
  42     typedef bg::model::linestring<point_type> linestring_type;
  43     typedef bg::model::multi_linestring<linestring_type> multilinestring_type;
  44     typedef bg::model::polygon
  45         <
  46             point_type, /*ClockWise*/false, /*Closed*/false
  47         > polygon_type;
  48
  49     multilinestring_type multilinestring;
  50     bg::read_wkt(ticket_10835[0], multilinestring);
  51     polygon_type polygon1;
  52     bg::read_wkt(ticket_10835[1], polygon1);
  53     polygon_type polygon2;
  54     bg::read_wkt(ticket_10835[2], polygon2);
  55
  56     multilinestring_type multilinestringOut1;
  57     bg::difference(multilinestring, polygon1, multilinestringOut1);
  58     std::stringstream stream;
  59     stream << bg::wkt(multilinestringOut1);
  60
  61     BOOST_CHECK_EQUAL(stream.str(), wkt_out1);
  62
  63     multilinestring_type multilinestringOut2;
  64     bg::difference(multilinestringOut1, polygon2, multilinestringOut2);
  65     stream.str("");
  66     stream.clear();
  67     stream << bg::wkt(multilinestringOut2);
  68
  69     BOOST_CHECK_EQUAL(stream.str(), wkt_out2);
  70 }
  71
  72
  73 template <typename Polygon, typename LineString>
  74 void test_areal_linear()
  75 {
  76     typedef typename bg::point_type<Polygon>::type point;
  77     typedef typename bg::coordinate_type<point>::type ct;
  78
  79     std::string const poly_simplex = "POLYGON((1 1,1 3,3 3,3 1,1 1))";
  80     test_one_lp<LineString, LineString, Polygon>("simplex", "LINESTRING(0 2,4 2)", poly_simplex, 2, 4, 2.0);
  81     test_one_lp<LineString, LineString, Polygon>("case2",  "LINESTRING(0 1,4 3)", poly_simplex, 2, 4, sqrt(5.0));
  82     test_one_lp<LineString, LineString, Polygon>("case3", "LINESTRING(0 1,1 2,3 2,4 3,6 3,7 4)", "POLYGON((2 0,2 5,5 5,5 0,2 0))", 2, 6, 2.0 + 2.0 * sqrt(2.0));
  83     test_one_lp<LineString, LineString, Polygon>("case4", "LINESTRING(1 1,3 2,1 3)", "POLYGON((0 0,0 4,2 4,2 0,0 0))", 1, 3, sqrt(5.0));
  84
  85     test_one_lp<LineString, LineString, Polygon>("case5", "LINESTRING(0 1,3 4)", poly_simplex, 2, 4, 2.0 * sqrt(2.0));
  86     test_one_lp<LineString, LineString, Polygon>("case6", "LINESTRING(1 1,10 3)", "POLYGON((2 0,2 4,3 4,3 1,4 1,4 3,5 3,5 1,6 1,6 3,7 3,7 1,8 1,8 3,9 3,9 0,2 0))", 5, 10,
  87             // Pieces are 1 x 2/9:
  88             5.0 * sqrt(1.0 + 4.0/81.0));
  89
  90
  91     test_one_lp<LineString, LineString, Polygon>("case7", "LINESTRING(1.5 1.5,2.5 2.5)", poly_simplex, 0, 0, 0.0);
  92     test_one_lp<LineString, LineString, Polygon>("case8", "LINESTRING(1 0,2 0)", poly_simplex, 1, 2, 1.0);
  93
  94     std::string const poly_9 = "POLYGON((1 1,1 4,4 4,4 1,1 1))";
  95     test_one_lp<LineString, LineString, Polygon>("case9", "LINESTRING(0 1,1 2,2 2)", poly_9, 1, 2, sqrt(2.0));
  96     test_one_lp<LineString, LineString, Polygon>("case10", "LINESTRING(0 1,1 2,0 2)", poly_9, 1, 3, 1.0 + sqrt(2.0));
  97     test_one_lp<LineString, LineString, Polygon>("case11", "LINESTRING(2 2,4 2,3 3)", poly_9, 0, 0, 0.0);
  98     test_one_lp<LineString, LineString, Polygon>("case12", "LINESTRING(2 3,4 4,5 6)", poly_9, 1, 2, sqrt(5.0));
  99
 100     test_one_lp<LineString, LineString, Polygon>("case13", "LINESTRING(3 2,4 4,2 3)", poly_9, 0, 0, 0.0);
 101     test_one_lp<LineString, LineString, Polygon>("case14", "LINESTRING(5 6,4 4,6 5)", poly_9, 1, 3, 2.0 * sqrt(5.0));
 102
 103     test_one_lp<LineString, LineString, Polygon>("case15", "LINESTRING(0 2,1 2,1 3,0 3)", poly_9, 2, 4, 2.0);
 104     test_one_lp<LineString, LineString, Polygon>("case16", "LINESTRING(2 2,1 2,1 3,2 3)", poly_9, 0, 0, 0.0);
 105
 106     std::string const angly = "LINESTRING(2 2,2 1,4 1,4 2,5 2,5 3,4 3,4 4,5 4,3 6,3 5,2 5,2 6,0 4)";
 107     test_one_lp<LineString, LineString, Polygon>("case17", angly, "POLYGON((1 1,1 5,4 5,4 1,1 1))", 3, 11, 6.0 + 4.0 * sqrt(2.0));
 108     test_one_lp<LineString, LineString, Polygon>("case18", angly, "POLYGON((1 1,1 5,5 5,5 1,1 1))", 2, 6, 2.0 + 3.0 * sqrt(2.0));
 109     test_one_lp<LineString, LineString, Polygon>("case19", "LINESTRING(1 2,1 3,0 3)", poly_9, 1, 2, 1.0);
 110     test_one_lp<LineString, LineString, Polygon>("case20", "LINESTRING(1 2,1 3,2 3)", poly_9, 0, 0, 0.0);
 111
 112     // PROPERTIES CHANGED BY switch_to_integer
 113     // TODO test_one_lp<LineString, LineString, Polygon>("case21", "LINESTRING(1 2,1 4,4 4,4 1,2 1,2 2)", poly_9, 0, 0, 0.0);
 114
 115     // More collinear (opposite) cases
 116     test_one_lp<LineString, LineString, Polygon>("case22", "LINESTRING(4 1,4 4,7 4)", poly_9, 1, 2, 3.0);
 117     test_one_lp<LineString, LineString, Polygon>("case23", "LINESTRING(4 0,4 4,7 4)", poly_9, 2, 4, 4.0);
 118     test_one_lp<LineString, LineString, Polygon>("case24", "LINESTRING(4 1,4 5,7 5)", poly_9, 1, 3, 4.0);
 119     test_one_lp<LineString, LineString, Polygon>("case25", "LINESTRING(4 0,4 5,7 5)", poly_9, 2, 5, 5.0);
 120     test_one_lp<LineString, LineString, Polygon>("case26", "LINESTRING(4 0,4 3,4 5,7 5)", poly_9, 2, 5, 5.0);
 121     test_one_lp<LineString, LineString, Polygon>("case27", "LINESTRING(4 4,4 5,5 5)", poly_9, 1, 3, 2.0);
 122
 123     if (BOOST_GEOMETRY_CONDITION( (! boost::is_same<ct, float>::value)) )
 124     {
 125         // Fails for float
 126         test_one_lp<LineString, LineString, Polygon>("case28",
 127             "LINESTRING(-1.3 0,-15 0,-1.3 0)",
 128             "POLYGON((2 3,-9 -7,12 -13,2 3))",
 129              1, 3, 27.4);
 130     }
 131
 132     test_one_lp<LineString, LineString, Polygon>("case29",
 133         "LINESTRING(5 5,-10 5,5 5)",
 134         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 135          1, 3, 20);
 136
 137     test_one_lp<LineString, LineString, Polygon>("case29a",
 138         "LINESTRING(1 1,5 5,-10 5,5 5,6 6)",
 139         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 140          1, 3, 20);
 141
 142     test_one_lp<LineString, LineString, Polygon>("case30",
 143         "LINESTRING(-10 5,5 5,-10 5)",
 144         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 145          2, 4, 20);
 146
 147     test_one_lp<LineString, LineString, Polygon>("case30a",
 148         "LINESTRING(-20 10,-10 5,5 5,-10 5,-20 -10)",
 149         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 150          2, 6, 49.208096);
 151
 152     test_one_lp<LineString, LineString, Polygon>("case31",
 153         "LINESTRING(0 5,5 5,0 5)",
 154         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 155          0, 0, 0);
 156
 157     test_one_lp<LineString, LineString, Polygon>("case31",
 158         "LINESTRING(0 5,5 5,1 1,9 1,5 5,0 5)",
 159         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 160          0, 0, 0);
 161
 162     test_one_lp<LineString, LineString, Polygon>("case32",
 163         "LINESTRING(5 5,0 5,5 5)",
 164         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 165          0, 0, 0);
 166
 167     test_one_lp<LineString, LineString, Polygon>("case32a",
 168         "LINESTRING(-10 10,5 5,0 5,5 5,20 10)",
 169         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 170          2, 4, 21.081851);
 171
 172     test_one_lp<LineString, LineString, Polygon>("case33",
 173         "LINESTRING(-5 5,0 5,-5 5)",
 174         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 175          1, 3, 10);
 176
 177     test_one_lp<LineString, LineString, Polygon>("case33a",
 178         "LINESTRING(-10 10,-5 5,0 5,-5 5,-10 -10)",
 179         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 180          1, 5, 32.882456);
 181
 182     test_one_lp<LineString, LineString, Polygon>("case33b",
 183         "LINESTRING(0 5,-5 5,0 5)",
 184         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 185          1, 3, 10);
 186
 187     test_one_lp<LineString, LineString, Polygon>("case34",
 188         "LINESTRING(5 5,0 5,5 5,5 4,0 4,5 4)",
 189         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 190          0, 0, 0);
 191
 192     test_one_lp<LineString, LineString, Polygon>("case35",
 193         "LINESTRING(5 5,0 5,5 5,5 4,0 4,5 3)",
 194         "POLYGON((0 0,0 10,10 10,10 0,0 0))",
 195          0, 0, 0);
 196
 197     test_one_lp<LineString, LineString, Polygon>("case36",
 198         "LINESTRING(-1 -1,10 10)",
 199         "POLYGON((5 5,15 15,15 5,5 5))",
 200         1, 2, 6 * std::sqrt(2.0));
 201
 202     test_one_lp<LineString, LineString, Polygon>("case37_1",
 203         "LINESTRING(1 1,2 2)",
 204         "POLYGON((0 0,0 3,3 3,3 0,0 0),(1 1,1 2,2 2,2 1,1 1))",
 205         1, 2, std::sqrt(2.0));
 206
 207     test_one_lp<LineString, LineString, Polygon>("case37_2",
 208         "LINESTRING(1 1,2 2,3 3)",
 209         "POLYGON((0 0,0 3,3 3,3 0,0 0),(1 1,1 2,2 2,2 1,1 1))",
 210         1, 2, std::sqrt(2.0));
 211
 212     test_one_lp<LineString, LineString, Polygon>("case38",
 213         "LINESTRING(0 0,1 1,2 2,3 3)",
 214         "POLYGON((0 0,0 9,9 9,9 0,0 0),(0 0,2 1,2 2,1 2,0 0))",
 215         1, 3, 2 * std::sqrt(2.0));
 216
 217     // several linestrings are in the output, the result is geometrically correct
 218     // still single linestring could be generated
 219     test_one_lp<LineString, LineString, Polygon>("case39",
 220         "LINESTRING(0 0,1 1,2 2,3 3)",
 221         "POLYGON((0 0,0 9,9 9,9 0,0 0),(0 0,2 1,2 2,1 2,0 0),(2 2,3 2,3 3,2 3,2 2))",
 222         2, 5, 3 * std::sqrt(2.0));
 223     test_one_lp<LineString, LineString, Polygon>("case40",
 224         "LINESTRING(0 0,1 1,2 2,4 4)",
 225         "POLYGON((0 0,0 9,9 9,9 0,0 0),(0 0,2 1,2 2,1 2,0 0),(2 2,3 2,3 3,2 3,2 2))",
 226         2, 5, 3 * std::sqrt(2.0));
 227     test_one_lp<LineString, LineString, Polygon>("case41",
 228         "LINESTRING(0 0,1 1,2 2,9 9)",
 229         "POLYGON((0 0,0 9,9 9,9 0,0 0),(0 0,2 1,2 2,1 2,0 0),(2 2,3 2,3 3,2 3,2 2),(7 7,8 7,9 9,7 8,7 7))",
 230         3, 7, 5 * std::sqrt(2.0));
 231 }
 232
 233 template <typename P>
 234 void test_all()
 235 {
 236     typedef bg::model::polygon<P> polygon;
 237     typedef bg::model::linestring<P> linestring;
 238
 239     test_areal_linear<polygon, linestring>();
 240 }
 241
 242
 243 int test_main(int, char* [])
 244 {
 245     test_all<bg::model::d2::point_xy<double> >();
 246
 247     test_ticket_10835<int>
 248         ("MULTILINESTRING((5239 2113,5233 2114),(4794 2205,1020 2986))",
 249          "MULTILINESTRING((5239 2113,5233 2114),(4794 2205,1460 2895))");
 250
 251     test_ticket_10835<double>
 252         ("MULTILINESTRING((5239 2113,5232.52 2114.34),(4794.39 2205,1020 2986))",
 253          "MULTILINESTRING((5239 2113,5232.52 2114.34),(4794.39 2205,1459.78 2895))");
 254
 255 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
 256     test_all<bg::model::d2::point_xy<float> >();
 257 #endif
 258
 259     return 0;
 260 }