1 // Boost.Geometry (aka GGL, Generic Geometry Library)
4 // Copyright (c) 2010-2015 Barend Gehrels, Amsterdam, the Netherlands.
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
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)
20 #include <boost/geometry/algorithms/correct.hpp>
21 #include <boost/geometry/algorithms/is_valid.hpp>
23 #include <boost/geometry/io/wkt/wkt.hpp>
25 #include <boost/geometry/geometries/point_xy.hpp>
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>
33 template <typename CoordinateType
>
34 void test_ticket_10835(std::string
const& wkt_out1
, std::string
const& wkt_out2
)
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
41 point_type
, /*ClockWise*/false, /*Closed*/false
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
);
51 multilinestring_type multilinestringOut1
;
52 bg::difference(multilinestring
, polygon1
, multilinestringOut1
);
53 std::stringstream stream
;
54 stream
<< bg::wkt(multilinestringOut1
);
56 BOOST_CHECK_EQUAL(stream
.str(), wkt_out1
);
58 multilinestring_type multilinestringOut2
;
59 bg::difference(multilinestringOut1
, polygon2
, multilinestringOut2
);
62 stream
<< bg::wkt(multilinestringOut2
);
64 BOOST_CHECK_EQUAL(stream
.str(), wkt_out2
);
68 template <typename Polygon
, typename LineString
>
69 void test_areal_linear()
71 typedef typename
bg::point_type
<Polygon
>::type point
;
72 typedef typename
bg::coordinate_type
<point
>::type ct
;
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));
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));
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);
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));
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));
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);
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);
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);
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);
118 if (BOOST_GEOMETRY_CONDITION( (! std::is_same
<ct
, float>::value
)) )
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))",
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))",
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))",
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))",
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))",
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))",
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))",
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))",
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))",
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))",
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))",
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))",
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))",
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))",
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));
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));
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));
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));
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));
228 template <typename P
>
231 typedef bg::model::polygon
<P
> polygon
;
232 typedef bg::model::linestring
<P
> linestring
;
234 test_areal_linear
<polygon
, linestring
>();
238 int test_main(int, char* [])
240 test_all
<bg::model::d2::point_xy
<double> >();
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))");
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))");
250 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
251 test_all
<bg::model::d2::point_xy
<float> >();