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