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