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>
test_ticket_10835(std::string const & wkt_out1,std::string const & wkt_out2)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>
test_areal_linear()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>
test_all()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 
test_main(int,char * [])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 }
261