1 /**
2 * SFCGAL
3 *
4 * Copyright (C) 2012-2013 Oslandia <infos@oslandia.com>
5 * Copyright (C) 2012-2013 IGN (http://www.ign.fr)
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Library General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Library General Public License for more details.
16
17 * You should have received a copy of the GNU Library General Public
18 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
19 */
20 #include <SFCGAL/Exception.h>
21 #include <SFCGAL/algorithm/isValid.h>
22 #include <SFCGAL/algorithm/difference.h>
23 #include <SFCGAL/algorithm/volume.h>
24 #include <SFCGAL/algorithm/covers.h>
25 #include <SFCGAL/Point.h>
26 #include <SFCGAL/detail/tools/Registry.h>
27
28 #include <SFCGAL/io/wkt.h>
29 #include <SFCGAL/io/vtk.h>
30
31 #include <boost/test/unit_test.hpp>
32
33 using namespace SFCGAL;
34 using namespace boost::unit_test ;
35
36 BOOST_AUTO_TEST_SUITE( SFCGAL_algorithm_DifferenceTest )
37
BOOST_AUTO_TEST_CASE(testDifferenceXPoint)38 BOOST_AUTO_TEST_CASE( testDifferenceXPoint )
39 {
40 // The same point
41 BOOST_CHECK( algorithm::difference( Point( 0,0 ), Point( 0,0 ) )->isEmpty() );
42 // A different point
43 BOOST_CHECK( *algorithm::difference( Point( 1,0 ), Point( 0,0 ) ) == Point( 1,0 ) );
44 // A different point (reversed)
45 BOOST_CHECK( *algorithm::difference( Point( 0,0 ), Point( 1,0 ) ) == Point( 0,0 ) );
46
47 // check difference(X, point) == X
48 std::vector<std::string> typeNames;
49
50 for ( size_t i = 0; i < typeNames.size(); ++i ) {
51 std::unique_ptr<Geometry> newGeo( tools::Registry::instance().newGeometryByTypeName( typeNames[i] ) );
52 std::unique_ptr<Geometry> diffGeo = algorithm::difference( *newGeo, Point( 0, 0 ) );
53 BOOST_CHECK( *newGeo == *diffGeo );
54 }
55 }
56
BOOST_AUTO_TEST_CASE(testDifferenceXLineString)57 BOOST_AUTO_TEST_CASE( testDifferenceXLineString )
58 {
59 // Point x Linestring intersecting
60 BOOST_CHECK( algorithm::difference( Point( 0,0 ), *io::readWkt( "LINESTRING(0 0,1 1)" ) )->isEmpty() );
61 // Point x linestring not intersecting
62 BOOST_CHECK( *algorithm::difference( Point( 0,0 ), *io::readWkt( "LINESTRING(0 1,1 1)" ) ) == Point( 0, 0 ) );
63
64 // two linestrings with two segments overlapping
65 {
66 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(0 0,1 0)" );
67 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(0.5 0,0.7 0)" );
68 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
69 BOOST_CHECK( *diff == *io::readWkt( "MULTILINESTRING((0 0,0.5 0),(0.7 0,1 0))" ) );
70 }
71 // two linestrings with two opposite segments overlapping
72 {
73 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(0 0,1 0)" );
74 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(0.7 0,0.5 0)" );
75 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
76 BOOST_CHECK( *diff == *io::readWkt( "MULTILINESTRING((0 0,0.5 0),(0.7 0,1 0))" ) );
77 }
78 // two linestrings with two segments crossing
79 {
80 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(-1 0,1 0)" );
81 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(0 -1,0 1)" );
82 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
83 BOOST_CHECK( *diff == *ls1 );
84 }
85 // two linestrings with two segments partly overlapping
86 {
87 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(0 0,1 0)" );
88 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(-1 0,0.7 0)" );
89 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
90 BOOST_CHECK( *diff == *io::readWkt( "LINESTRING(0.7 0,1 0)" ) );
91 }
92 // two linestrings with a segment covering another one
93 {
94 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(0 0,1 0)" );
95 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(-1 0,2 0)" );
96 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
97 BOOST_CHECK( diff->isEmpty() );
98 }
99 // two linestrings that do not intersect
100 {
101 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(0 0,1 0)" );
102 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(0 1,1 1)" );
103 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
104 BOOST_CHECK( *diff == *ls1 );
105 }
106 // two linestrings with more than one segment
107 {
108 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(0 0,1 0,1 1)" );
109 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(0.3 0,1 0,1 0.4)" );
110 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
111 BOOST_CHECK( *diff == *io::readWkt( "MULTILINESTRING((0 0,0.3 0),(1 0.4,1 1))" ) );
112 }
113
114 // check difference(X, linestring) == X, with dimension(X) > 1
115 // TODO: add generators of random geometries to avoid empty geometries here ?
116 std::vector<std::string> typeNames;
117
118 for ( size_t i = 0; i < typeNames.size(); ++i ) {
119 std::unique_ptr<Geometry> newGeo( tools::Registry::instance().newGeometryByTypeName( typeNames[i] ) );
120
121 if ( newGeo->dimension() > 1 ) {
122 std::unique_ptr<Geometry> diffGeo = algorithm::difference( *newGeo, Point( 0, 0 ) );
123 BOOST_CHECK( *newGeo == *diffGeo );
124 }
125 }
126 }
127
BOOST_AUTO_TEST_CASE(testDifferencePolygonPolygon2D)128 BOOST_AUTO_TEST_CASE( testDifferencePolygonPolygon2D )
129 {
130 // two identical polygons
131 {
132 std::unique_ptr<Geometry> ls1 = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1))" );
133 std::unique_ptr<Geometry> ls2 = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1))" );
134 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
135 BOOST_CHECK( *diff == *io::readWkt( "GEOMETRYCOLLECTION EMPTY" ) );
136 }
137
138 // two polygons, one of wich is invalid for CGAL but valid for SFS
139 {
140 std::unique_ptr<Geometry> ls1 = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1))" );
141 std::unique_ptr<Geometry> ls2 = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1),(-0.5 -0.5,-0.5 0.5,0.5 0.5,1 -0.5,-0.5 -0.5))" );
142 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
143 BOOST_CHECK( *diff == *io::readWkt( "POLYGON((-0.5 -0.5,1 -0.5,0.5 0.5,-0.5 0.5,-0.5 -0.5))" ) );
144 BOOST_CHECK( algorithm::isValid( *diff ) );
145 }
146
147 // two polygons the result has a hole touching the outer boundary
148 {
149 std::unique_ptr<Geometry> ls1 = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1))" );
150 std::unique_ptr<Geometry> ls2 = io::readWkt( "POLYGON((-0.5 -0.5,1 -0.5,0.5 0.5,-0.5 0.5,-0.5 -0.5))" );
151 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
152 BOOST_CHECK( algorithm::isValid( *diff ) );
153 BOOST_CHECK( *diff == *io::readWkt( "POLYGON((-1 -1,1 -1,1 -0.5,1 1,-1 1,-1 -1),(1 -0.5,-0.5 -0.5,-0.5 0.5,0.5 0.5,1 -0.5))" ) );
154 }
155 }
156
BOOST_AUTO_TEST_CASE(testDifferenceVolumeVolume)157 BOOST_AUTO_TEST_CASE( testDifferenceVolumeVolume )
158 {
159
160 // two cubes
161 {
162 std::unique_ptr<Geometry> ls1 = io::readWkt(
163 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
164 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
165 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
166 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
167 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
168 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
169 std::unique_ptr<Geometry> ls2 = io::readWkt(
170 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
171 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
172 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
173 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
174 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
175 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
176 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
177 BOOST_CHECK( *diff == *io::readWkt( "GEOMETRYCOLLECTION EMPTY" ) );
178 }
179 // two cubes
180 {
181 std::unique_ptr<Geometry> ls1 = io::readWkt(
182 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
183 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
184 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
185 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
186 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
187 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
188 std::unique_ptr<Geometry> ls2 = io::readWkt(
189 "SOLID((((0 0 0.5, 0 1 0.5, 1 1 0.5, 1 0 0.5, 0 0 0.5)),\
190 ((0 0 0.5, 0 0 1, 0 1 1, 0 1 0.5, 0 0 0.5)),\
191 ((0 0 0.5, 1 0 0.5, 1 0 1, 0 0 1, 0 0 0.5)),\
192 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
193 ((1 1 1, 1 0 1, 1 0 0.5, 1 1 0.5, 1 1 1)),\
194 ((1 1 1, 1 1 0.5, 0 1 0.5, 0 1 1, 1 1 1))))" );
195 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
196 BOOST_CHECK( algorithm::volume( *diff ) == Kernel::FT( 0.5 ) );
197 }
198
199
200 }
201
BOOST_AUTO_TEST_CASE(testDifferenceLinePolygon)202 BOOST_AUTO_TEST_CASE( testDifferenceLinePolygon )
203 {
204
205 // segment - polygon in 2D
206 {
207 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(-10 0,10 0)" );
208 std::unique_ptr<Geometry> ls2 = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1),(-0.5 -0.5,-0.5 0.5,0 0,-0.5 -0.5),(0.5 0.5,0.5 -0.5,0 0,0.5 0.5))" );
209 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
210 BOOST_CHECK( *diff == *io::readWkt( "MULTILINESTRING((-10 0,-1 0),(-0.5 0,0 0,0.5 0),(1 0,10 0))" ) );
211 }
212
213 // segment - polygon in 2D, with sement lying on hole border
214 {
215 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(-10 0,10 0)" );
216 std::unique_ptr<Geometry> ls2 = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1),(-0.5 -0.5,-0.5 0.5,0 0,-0.5 -0.5),(0.5 0,0.5 -0.5,0 0,0.5 0))" );
217 std::unique_ptr<Geometry> diff = algorithm::difference( *ls1, *ls2 );
218 BOOST_CHECK( *diff == *io::readWkt( "MULTILINESTRING((-10 0,-1 0),(-0.5 0,0 0),(1 0,10 0))" ) );
219 }
220
221 }
222
BOOST_AUTO_TEST_CASE(testDifferencePoinLine)223 BOOST_AUTO_TEST_CASE( testDifferencePoinLine )
224 {
225 // point - segment in 3D
226 {
227 std::unique_ptr<Geometry> ls1 = io::readWkt( "POINT(0.5 0.5 0.6)" );
228 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(0 0 0,1 1 1)" );
229 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
230 BOOST_CHECK( *diff == *io::readWkt( "POINT(0.5 0.5 0.6)" ) );
231 }
232 {
233 std::unique_ptr<Geometry> ls1 = io::readWkt( "POINT(0.5 0.5 0.5)" );
234 std::unique_ptr<Geometry> ls2 = io::readWkt( "LINESTRING(0 0 0,1 1 1)" );
235 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
236 BOOST_CHECK( *diff == *io::readWkt( "GEOMETRYCOLLECTION EMPTY" ) );
237 }
238
239 }
240
BOOST_AUTO_TEST_CASE(testDifferencePoinPolygon2D)241 BOOST_AUTO_TEST_CASE( testDifferencePoinPolygon2D )
242 {
243 // point - triangle in 3D
244 {
245 std::unique_ptr<Geometry> ls1 = io::readWkt( "POINT(0.5 0.5 0.6)" );
246 std::unique_ptr<Geometry> ls2 = io::readWkt( "POLYGON((0 0 0,1 1 1,1 0 1,0 0 0))" );
247 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
248 BOOST_CHECK( *diff == *io::readWkt( "POINT(0.5 0.5 0.6)" ) );
249 }
250 {
251 std::unique_ptr<Geometry> ls1 = io::readWkt( "POINT(0.5 0.5 0.5)" );
252 std::unique_ptr<Geometry> ls2 = io::readWkt( "POLYGON((0 0 0,1 1 1,1 0 1,0 0 0))" );
253 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
254 BOOST_CHECK( *diff == *io::readWkt( "GEOMETRYCOLLECTION EMPTY" ) );
255 }
256 }
257
BOOST_AUTO_TEST_CASE(testDifferencePoinVolume)258 BOOST_AUTO_TEST_CASE( testDifferencePoinVolume )
259 {
260
261 // point - volume
262 {
263 std::unique_ptr<Geometry> ls1 = io::readWkt( "POINT(0.5 0.5 0.5)" );
264 std::unique_ptr<Geometry> ls2 = io::readWkt(
265 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
266 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
267 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
268 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
269 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
270 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
271 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
272 BOOST_CHECK( *diff == *io::readWkt( "GEOMETRYCOLLECTION EMPTY" ) );
273 }
274 {
275 std::unique_ptr<Geometry> ls1 = io::readWkt( "POINT(1.001 0.5 0.5)" );
276 std::unique_ptr<Geometry> ls2 = io::readWkt(
277 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
278 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
279 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
280 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
281 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
282 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
283 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
284 BOOST_CHECK( *diff == *io::readWkt( "POINT(1.001 0.5 0.5)" ) );
285 }
286
287 }
288
BOOST_AUTO_TEST_CASE(testDifferenceTriangleTriangle3D)289 BOOST_AUTO_TEST_CASE( testDifferenceTriangleTriangle3D )
290 {
291 // triangle - trangle in 3D don't share the same plane
292 {
293 std::unique_ptr<Geometry> ls1 = io::readWkt( "TRIANGLE((0 0 0,0 1 1,1 0 0,0 0 0))" );
294 std::unique_ptr<Geometry> ls2 = io::readWkt( "TRIANGLE((0 0 0,0 1 1.01,1 0 0,0 0 0))" );
295 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
296 BOOST_CHECK( *diff == *io::readWkt( "TRIANGLE((0 0 0,0 1 1,1 0 0,0 0 0))" ) );
297 }
298 // triangle - trangle in 3D don't intersect
299 {
300 std::unique_ptr<Geometry> ls1 = io::readWkt( "TRIANGLE((0 0 0,0 1 1,1 0 0,0 0 0))" );
301 std::unique_ptr<Geometry> ls2 = io::readWkt( "TRIANGLE((.6 .6 .6,1.6 1.6 1.6,1.6 .6 .6,.6 .6 .6))" );
302 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
303 BOOST_CHECK( *diff == *io::readWkt( "TRIANGLE((0 0 0,0 1 1,1 0 0,0 0 0))" ) );
304 }
305 // triangle - triangle in 3D do intersect
306 {
307 std::unique_ptr<Geometry> ls1 = io::readWkt( "TRIANGLE((0 0 0,0 1 1,1 0 0,0 0 0))" );
308 std::unique_ptr<Geometry> ls2 = io::readWkt( "TRIANGLE((.1 .1 .1,1.6 1.6 1.6,1.6 .6 .6,.1 .1 .1))" );
309 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
310 BOOST_CHECK( *diff == *io::readWkt( "TIN(((0 1 1,.5 .5 .5,.1 .1 .1,0 1 1)),((0 0 0,0 1 1,.1 .1 .1,0 0 0)),((.7 .3 .3,1 0 0,.1 .1 .1,.7 .3 .3)),((1 0 0,0 0 0,.1 .1 .1,1 0 0)))" ) );
311 }
312
313 }
314
BOOST_AUTO_TEST_CASE(testDifferenceTriangleVolume)315 BOOST_AUTO_TEST_CASE( testDifferenceTriangleVolume )
316 {
317 // triangle - volume in 3D
318 {
319 std::unique_ptr<Geometry> ls1 = io::readWkt( "TRIANGLE((0 0 .5,10 0 .5,0 10 .5,0 0 .5))" );
320 std::unique_ptr<Geometry> ls2 = io::readWkt(
321 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
322 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
323 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
324 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
325 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
326 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
327 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
328 std::unique_ptr<Geometry> ref = io::readWkt( "TIN(((0/1 10/1 1/2,9/20 1/1 1/2,1/2 1/1 1/2,0/1 10/1 1/2)),((0/1 10/1 1/2,1/2 1/1 1/2,18/19 1/1 1/2,0/1 10/1 1/2)),((0/1 10/1 1/2,0/1 1/1 1/2,9/20 1/1 1/2,0/1 10/1 1/2)),((1/1 0/1 1/2,10/1 0/1 1/2,1/1 1/2 1/2,1/1 0/1 1/2)),((1/1 1/1 1/2,0/1 10/1 1/2,18/19 1/1 1/2,1/1 1/1 1/2)),((10/1 0/1 1/2,0/1 10/1 1/2,1/1 1/1 1/2,10/1 0/1 1/2)),((1/1 1/2 1/2,10/1 0/1 1/2,1/1 1/1 1/2,1/1 1/2 1/2)))" );
329 BOOST_CHECK( algorithm::covers( *diff, *ref ) && algorithm::covers( *ref, *diff ) );
330 }
331 }
332
BOOST_AUTO_TEST_CASE(testDifferenceLineVolume)333 BOOST_AUTO_TEST_CASE( testDifferenceLineVolume )
334 {
335 // segment - volume in 3D
336 {
337 std::unique_ptr<Geometry> ls1 = io::readWkt( "LINESTRING(-3 -3 .5,3 3 .5,1 1.1 .5,1 .1 .5,.1 .1 .5)" );
338 std::unique_ptr<Geometry> ls2 = io::readWkt(
339 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
340 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
341 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
342 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
343 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
344 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
345 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
346 BOOST_CHECK( *diff == *io::readWkt( "MULTILINESTRING((-3 -3 .5,0 0 .5),(1 1 .5,3 3 .5,1 1.1 .5,1 1 .5))" ) );
347 }
348
349 }
350
BOOST_AUTO_TEST_CASE(testDifferencePolygonVolume)351 BOOST_AUTO_TEST_CASE( testDifferencePolygonVolume )
352 {
353
354 // polygon - volume crashing the algo in garden
355 {
356 std::unique_ptr<Geometry> ls1 = io::readWkt( "POLYGON((1 -1 -1,1 1 -1,1 1 1,1 -1 1,1 -1 -1))" );
357 std::unique_ptr<Geometry> ls2 = io::readWkt(
358 "SOLID((((0 0 0,0 1 0,1 1 0,1 0 0,0 0 0)),\
359 ((0 0 0,0 0 1,0 1 1,0 1 0,0 0 0)),\
360 ((0 0 0,1 0 0,1 0 1,0 0 1,0 0 0)),\
361 ((1 1 1,0 1 1,0 0 1,1 0 1,1 1 1)),\
362 ((1 1 1,1 0 1,1 0 0,1 1 0,1 1 1)),\
363 ((1 1 1,1 1 0,0 1 0,0 1 1,1 1 1))))" );
364 std::unique_ptr<Geometry> diff = algorithm::difference3D( *ls1, *ls2 );
365 }
366
367 }
368
BOOST_AUTO_TEST_CASE(testDifference3DDivideByZeroCrash)369 BOOST_AUTO_TEST_CASE( testDifference3DDivideByZeroCrash )
370 {
371 // Correct behaviour is to throw an exception about the degenerate polygon in g1.
372 // Incorrect behaviour is a divide by zero error
373 {
374 std::unique_ptr<Geometry> g1 = io::readWkt("SOLID((((1 1 0.5,0.5 1 0.5,0.5 1.5 0.5,1 1 0.5)),\
375 ((0.5 1 0.5,1 1 0.5,1 1 -1,0.5 1 0.5)),\
376 ((0.5 1.5 0.5,0.5 1 0.5,0.5 1 1,0.5 1.5 0.5)),\
377 ((1 1 0.5,0.5 1.5 0.5,1.5 1.5 0.5,1 1 0.5)),\
378 ((1 1 -1,1 1 0.5,1 0.5 0.5,1 1 -1)),\
379 ((0.5 1 0.5,1 1 -1,-1 1 -1,0.5 1 0.5)),\
380 ((0.5 1 1,0.5 1 0.5,-1 1 1,0.5 1 1)),\
381 ((0.5 1.5 0.5,0.5 1 1,0.5 1.5 1.5,0.5 1.5 0.5)),\
382 ((1.5 1.5 0.5,0.5 1.5 0.5,1.5 1.5 1.5,1.5 1.5 0.5)),\
383 ((1 1 0.5,1.5 1.5 0.5,1 0.5 0.5,1 1 0.5)),\
384 ((1 1 -1,1 0.5 0.5,1 -1 -1,1 1 -1)),\
385 ((-1 1 -1,1 1 -1,-1 -1 -1,-1 1 -1)),\
386 ((0.5 1 0.5,-1 1 -1,-1 1 1,0.5 1 0.5)),\
387 ((0.5 1 1,-1 1 1,0.5 0.5 1,0.5 1 1)),\
388 ((0.5 1.5 1.5,0.5 1 1,0.5 0.5 1,0.5 1.5 1.5)),\
389 ((0.5 1.5 0.5,0.5 1.5 1.5,1.5 1.5 1.5,0.5 1.5 0.5)),\
390 ((1.5 1.5 0.5,1.5 1.5 1.5,1.5 0.5 1.5,1.5 1.5 0.5)),\
391 ((1 0.5 0.5,1.5 1.5 0.5,1.5 0.5 0.5,1 0.5 0.5)),\
392 ((1 -1 -1,1 0.5 0.5,1 0.5 0.5,1 -1 -1)),\
393 ((1 1 -1,1 -1 -1,-1 -1 -1,1 1 -1)),\
394 ((-1 1 -1,-1 -1 -1,-1 1 1,-1 1 -1)),\
395 ((0.5 0.5 1,-1 1 1,0.5 0.5 1,0.5 0.5 1)),\
396 ((0.5 1.5 1.5,0.5 0.5 1,0.5 0.5 1.5,0.5 1.5 1.5)),\
397 ((1.5 1.5 1.5,0.5 1.5 1.5,1.5 0.5 1.5,1.5 1.5 1.5)),\
398 ((1.5 1.5 0.5,1.5 0.5 1.5,1.5 0.5 0.5,1.5 1.5 0.5)),\
399 ((1 0.5 0.5,1.5 0.5 0.5,1 0.5 0.5,1 0.5 0.5)),\
400 ((1 -1 -1,1 0.5 0.5,1 0.5 0,1 -1 -1)),\
401 ((-1 -1 -1,1 -1 -1,-1 -1 1,-1 -1 -1)),\
402 ((-1 1 1,-1 -1 -1,-1 -1 1,-1 1 1)),\
403 ((0.5 0.5 1,-1 1 1,-1 -1 1,0.5 0.5 1)),\
404 ((0.5 0.5 1,0.5 0.5 1,0.5 0.5 1.5,0.5 0.5 1)),\
405 ((0.5 1.5 1.5,0.5 0.5 1.5,1.5 0.5 1.5,0.5 1.5 1.5)),\
406 ((1.5 0.5 0.5,1.5 0.5 1.5,1 0.5 0.5,1.5 0.5 0.5)),\
407 ((1 0.5 0.5,1.5 0.5 0.5,1 0.5 0,1 0.5 0.5)),\
408 ((1 -1 -1,1 0.5 0,1 -1 1,1 -1 -1)),\
409 ((-1 -1 1,1 -1 -1,1 -1 1,-1 -1 1)),\
410 ((0.5 0.5 1,-1 -1 1,0 0.5 1,0.5 0.5 1)),\
411 ((0.5 0.5 1.5,0.5 0.5 1,0 0.5 1,0.5 0.5 1.5)),\
412 ((1.5 0.5 1.5,0.5 0.5 1.5,0.5 0.5 1,1.5 0.5 1.5)),\
413 ((1 0.5 0.5,1.5 0.5 1.5,1 0.5 1,1 0.5 0.5)),\
414 ((1.5 0.5 0.5,1 0.5 0.5,1 0.5 0,1.5 0.5 0.5)),\
415 ((1 -1 1,1 0.5 0,1 0.5 0.5,1 -1 1)),\
416 ((-1 -1 1,1 -1 1,0 0.5 1,-1 -1 1)),\
417 ((0.5 0.5 1.5,0 0.5 1,0.5 0.5 1,0.5 0.5 1.5)),\
418 ((1.5 0.5 1.5,0.5 0.5 1,1 0.5 1,1.5 0.5 1.5)),\
419 ((1 0.5 0.5,1 0.5 1,1 -1 1,1 0.5 0.5)),\
420 ((0 0.5 1,1 -1 1,0.5 0.5 1,0 0.5 1)),\
421 ((1 0.5 1,0.5 0.5 1,1 -1 1,1 0.5 1))))");
422 std::unique_ptr<Geometry> g2 = io::readWkt("SOLID((((-0.5 1 1,-0.5 1 -0.5,-1 1 1,-0.5 1 1)),\
423 ((-0.5 1 -0.5,-0.5 1 1,-0.5 1.5 -0.5,-0.5 1 -0.5)),\
424 ((-1 1 1,-0.5 1 -0.5,-1 1 -1,-1 1 1)),\
425 ((-0.5 1 1,-1 1 1,-0.5 0.5 1,-0.5 1 1)),\
426 ((-0.5 1.5 -0.5,-0.5 1 1,-0.5 1.5 1.5,-0.5 1.5 -0.5)),\
427 ((-0.5 1 -0.5,-0.5 1.5 -0.5,1 1 -0.5,-0.5 1 -0.5)),\
428 ((-1 1 -1,-0.5 1 -0.5,1 1 -1,-1 1 -1)),\
429 ((-1 1 1,-1 1 -1,-1 -1 -1,-1 1 1)),\
430 ((-0.5 0.5 1,-1 1 1,-0.5 -0.5 1,-0.5 0.5 1)),\
431 ((-0.5 1 1,-0.5 0.5 1,-0.5 1.5 1.5,-0.5 1 1)),\
432 ((-0.5 1.5 -0.5,-0.5 1.5 1.5,1.5 1.5 1.5,-0.5 1.5 -0.5)),\
433 ((1 1 -0.5,-0.5 1.5 -0.5,1.5 1.5 -0.5,1 1 -0.5)),\
434 ((-0.5 1 -0.5,1 1 -0.5,1 1 -1,-0.5 1 -0.5)),\
435 ((-1 1 -1,1 1 -1,-1 -1 -1,-1 1 -1)),\
436 ((-1 1 1,-1 -1 -1,-1 -1 1,-1 1 1)),\
437 ((-0.5 -0.5 1,-1 1 1,-1 -1 1,-0.5 -0.5 1)),\
438 ((-0.5 0.5 1,-0.5 -0.5 1,-0.5 -0.5 1.5,-0.5 0.5 1)),\
439 ((-0.5 1.5 1.5,-0.5 0.5 1,-0.5 -0.5 1.5,-0.5 1.5 1.5)),\
440 ((1.5 1.5 1.5,-0.5 1.5 1.5,1.5 -0.5 1.5,1.5 1.5 1.5)),\
441 ((-0.5 1.5 -0.5,1.5 1.5 1.5,1.5 1.5 -0.5,-0.5 1.5 -0.5)),\
442 ((1 1 -0.5,1.5 1.5 -0.5,1 0.5 -0.5,1 1 -0.5)),\
443 ((1 1 -1,1 1 -0.5,1 0.5 -0.5,1 1 -1)),\
444 ((-1 -1 -1,1 1 -1,1 -1 -1,-1 -1 -1)),\
445 ((-1 -1 1,-1 -1 -1,1 -1 -1,-1 -1 1)),\
446 ((-0.5 -0.5 1,-1 -1 1,0 -0.5 1,-0.5 -0.5 1)),\
447 ((-0.5 -0.5 1.5,-0.5 -0.5 1,0 -0.5 1,-0.5 -0.5 1.5)),\
448 ((-0.5 1.5 1.5,-0.5 -0.5 1.5,1.5 -0.5 1.5,-0.5 1.5 1.5)),\
449 ((1.5 1.5 1.5,1.5 -0.5 1.5,1.5 1.5 -0.5,1.5 1.5 1.5)),\
450 ((1 0.5 -0.5,1.5 1.5 -0.5,1.5 -0.5 -0.5,1 0.5 -0.5)),\
451 ((1 1 -1,1 0.5 -0.5,1 -1 -1,1 1 -1)),\
452 ((-1 -1 1,1 -1 -1,1 -1 1,-1 -1 1)),\
453 ((0 -0.5 1,-1 -1 1,1 -1 1,0 -0.5 1)),\
454 ((-0.5 -0.5 1.5,0 -0.5 1,0.5 -0.5 1,-0.5 -0.5 1.5)),\
455 ((1.5 -0.5 1.5,-0.5 -0.5 1.5,0.5 -0.5 1,1.5 -0.5 1.5)),\
456 ((1.5 1.5 -0.5,1.5 -0.5 1.5,1.5 -0.5 -0.5,1.5 1.5 -0.5)),\
457 ((1 0.5 -0.5,1.5 -0.5 -0.5,1 -0.5 -0.5,1 0.5 -0.5)),\
458 ((1 -1 -1,1 0.5 -0.5,1 -0.5 -0.5,1 -1 -1)),\
459 ((1 -1 1,1 -1 -1,1 -0.5 -0,1 -1 1)),\
460 ((0 -0.5 1,1 -1 1,0.5 -0.5 1,0 -0.5 1)),\
461 ((1.5 -0.5 1.5,0.5 -0.5 1,1 -0.5 1,1.5 -0.5 1.5)),\
462 ((1.5 -0.5 -0.5,1.5 -0.5 1.5,1 -0.5 0.5,1.5 -0.5 -0.5)),\
463 ((1 -0.5 -0.5,1.5 -0.5 -0.5,1 -0.5 -0,1 -0.5 -0.5)),\
464 ((1 -1 -1,1 -0.5 -0.5,1 -0.5 -0,1 -1 -1)),\
465 ((1 -1 1,1 -0.5 -0,1 -0.5 0.5,1 -1 1)),\
466 ((0.5 -0.5 1,1 -1 1,1 -0.5 1,0.5 -0.5 1)),\
467 ((1.5 -0.5 1.5,1 -0.5 1,1 -0.5 0.5,1.5 -0.5 1.5)),\
468 ((1.5 -0.5 -0.5,1 -0.5 0.5,1 -0.5 -0,1.5 -0.5 -0.5)),\
469 ((1 -1 1,1 -0.5 0.5,1 -0.5 1,1 -1 1))))");
470
471 try
472 {
473 std::unique_ptr<Geometry> diff = algorithm::difference3D( *g1, *g2, algorithm::NoValidityCheck() );
474 }
475 catch(...)
476 {
477 }
478
479 try
480 {
481 std::unique_ptr<Geometry> diff = algorithm::difference3D( *g2, *g1, algorithm::NoValidityCheck() );
482 }
483 catch(...)
484 {
485 }
486 }
487 }
488
489 BOOST_AUTO_TEST_SUITE_END()
490