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/union.h>
23 #include <SFCGAL/algorithm/volume.h>
24 #include <SFCGAL/algorithm/translate.h>
25 #include <SFCGAL/algorithm/area.h>
26 #include <SFCGAL/detail/tools/Registry.h>
27 #include <SFCGAL/algorithm/tesselate.h>
28 #include <SFCGAL/triangulate/triangulatePolygon.h>
29
30 #include <SFCGAL/io/wkt.h>
31 #include <SFCGAL/io/vtk.h>
32
33 #include <boost/test/unit_test.hpp>
34
35 namespace SFCGAL {
36 namespace algorithm {
37 void handleLeakTest();
38 }
39 }
40
41 #define DEBUG_OUT if (0) std::cerr << __FILE__ << ":" << __LINE__ << " debug: "
42
43 using namespace SFCGAL;
44 using namespace boost::unit_test ;
45
46 BOOST_AUTO_TEST_SUITE( SFCGAL_algorithm_UnionTest )
47
48
BOOST_AUTO_TEST_CASE(Handle)49 BOOST_AUTO_TEST_CASE( Handle )
50 {
51 algorithm::handleLeakTest();
52 }
53
BOOST_AUTO_TEST_CASE(Handle1)54 BOOST_AUTO_TEST_CASE( Handle1 )
55 {
56 std::unique_ptr<Geometry> a = io::readWkt( "POINT(0 1)" );
57 std::unique_ptr<Geometry> b = io::readWkt( "POINT(0 1)" );
58 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
59 DEBUG_OUT << u->asText() <<"\n";
60 BOOST_CHECK( *u == *io::readWkt( "POINT(0 1)" ) );
61 }
62
BOOST_AUTO_TEST_CASE(Handle2)63 BOOST_AUTO_TEST_CASE( Handle2 )
64 {
65 std::unique_ptr<Geometry> a = io::readWkt( "MULTIPOINT(0 1,0 1,0 1)" );
66 std::unique_ptr<Geometry> b = io::readWkt( "POINT(0 1)" );
67 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
68 DEBUG_OUT << u->asText() <<"\n";
69 BOOST_CHECK( *u == *io::readWkt( "POINT(0 1)" ) );
70 }
71
BOOST_AUTO_TEST_CASE(PointPoint)72 BOOST_AUTO_TEST_CASE( PointPoint )
73 {
74 {
75 std::unique_ptr<Geometry> a = io::readWkt( "POINT(0 1)" );
76 std::unique_ptr<Geometry> b = io::readWkt( "POINT(0 1)" );
77 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
78 DEBUG_OUT << u->asText() <<"\n";
79 BOOST_CHECK( *u == *io::readWkt( "POINT(0 1)" ) );
80 }
81 {
82 std::unique_ptr<Geometry> a = io::readWkt( "POINT(0 0)" );
83 std::unique_ptr<Geometry> b = io::readWkt( "POINT(0 1)" );
84 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
85 DEBUG_OUT << u->asText() <<"\n";
86 BOOST_CHECK( *u == *io::readWkt( "MULTIPOINT(0 0,0 1)" ) );
87 }
88 {
89 std::unique_ptr<Geometry> a = io::readWkt( "POINT(0 1 1)" );
90 std::unique_ptr<Geometry> b = io::readWkt( "POINT(0 1 1)" );
91 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
92 DEBUG_OUT << u->asText() <<"\n";
93 BOOST_CHECK( *u == *io::readWkt( "POINT(0 1 1)" ) );
94 }
95 {
96 std::unique_ptr<Geometry> a = io::readWkt( "POINT(0 0 0)" );
97 std::unique_ptr<Geometry> b = io::readWkt( "POINT(0 0 1)" );
98 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
99 DEBUG_OUT << u->asText() <<"\n";
100 BOOST_CHECK( *u == *io::readWkt( "MULTIPOINT(0 0 0,0 0 1)" ) );
101 }
102 }
103
BOOST_AUTO_TEST_CASE(PointLine)104 BOOST_AUTO_TEST_CASE( PointLine )
105 {
106 {
107 std::unique_ptr<Geometry> a = io::readWkt( "POINT(.5 0)" );
108 std::unique_ptr<Geometry> b = io::readWkt( "LINESTRING(-1 0,1 0)" );
109 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
110 DEBUG_OUT << u->asText() <<"\n";
111 BOOST_CHECK( *u == *io::readWkt( "LINESTRING(-1 0,.5 0,1 0)" ) );
112 }
113 {
114 std::unique_ptr<Geometry> a = io::readWkt( "POINT(0 0 .5)" );
115 std::unique_ptr<Geometry> b = io::readWkt( "LINESTRING(0 0 -1,0 0 1)" );
116 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
117 DEBUG_OUT << u->asText() <<"\n";
118 BOOST_CHECK( *u == *io::readWkt( "LINESTRING(0 0 -1,0 0 .5,0 0 1)" ) );
119 }
120 }
121
BOOST_AUTO_TEST_CASE(LineLine)122 BOOST_AUTO_TEST_CASE( LineLine )
123 {
124 {
125 std::unique_ptr<Geometry> a = io::readWkt( "LINESTRING(-1 0,1 0)" );
126 std::unique_ptr<Geometry> b = io::readWkt( "LINESTRING(-1 1,1 1)" );
127 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
128 DEBUG_OUT << u->asText() <<"\n";
129 BOOST_CHECK( *u == *io::readWkt( "MULTILINESTRING((-1 0,1 0),(-1 1,1 1))" ) );
130 }
131 {
132 std::unique_ptr<Geometry> a = io::readWkt( "LINESTRING(-1 0,1 0)" );
133 std::unique_ptr<Geometry> b = io::readWkt( "LINESTRING(0 -1,0 1)" );
134 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
135 DEBUG_OUT << u->asText() <<"\n";
136 BOOST_CHECK( *u == *io::readWkt( "MULTILINESTRING((-1 0,0 0),(0 0,1 0),(0 -1,0 0),(0 0,0 1))" ) );
137 }
138 }
139
BOOST_AUTO_TEST_CASE(LineVolume)140 BOOST_AUTO_TEST_CASE( LineVolume )
141 {
142 std::unique_ptr<Geometry> a = io::readWkt( "LINESTRING(-1 -1 -1,2 2 2)" );
143 std::unique_ptr<Geometry> b = io::readWkt(
144 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
145 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
146 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
147 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
148 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
149 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
150 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
151 BOOST_CHECK( u->geometryTypeId() == TYPE_GEOMETRYCOLLECTION );
152 BOOST_CHECK( u->geometryN( 0 ).geometryTypeId() == TYPE_LINESTRING );
153 BOOST_CHECK( u->geometryN( 1 ).geometryTypeId() == TYPE_LINESTRING );
154 BOOST_CHECK( u->geometryN( 2 ).geometryTypeId() == TYPE_SOLID );
155 }
156
BOOST_AUTO_TEST_CASE(PointSurface)157 BOOST_AUTO_TEST_CASE( PointSurface )
158 {
159 {
160 std::unique_ptr<Geometry> a = io::readWkt( "TRIANGLE((0 0,0 1,1 0,0 0))" );
161 std::unique_ptr<Geometry> b = io::readWkt( "POINT(.1 .1)" );
162 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
163 DEBUG_OUT << u->asText() <<"\n";
164 BOOST_CHECK( *u == *io::readWkt( "TRIANGLE((0 0,0 1,1 0,0 0))" ) );
165 }
166 {
167 std::unique_ptr<Geometry> a = io::readWkt( "TRIANGLE((0 0 1,0 1 1,1 0 1,0 0 1))" );
168 std::unique_ptr<Geometry> b = io::readWkt( "POINT(.1 .1 1)" );
169 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
170 DEBUG_OUT << u->asText() <<"\n";
171 BOOST_CHECK( *u == *io::readWkt( "TRIANGLE((0 0 1,0 1 1,1 0 1,0 0 1))" ) );
172 }
173 }
174
BOOST_AUTO_TEST_CASE(PointVolume)175 BOOST_AUTO_TEST_CASE( PointVolume )
176 {
177 std::unique_ptr<Geometry> a = io::readWkt(
178 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
179 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
180 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
181 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
182 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
183 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
184 {
185 std::unique_ptr<Geometry> b = io::readWkt( "POINT(.1 .1 1)" );
186 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
187 BOOST_CHECK( u->geometryTypeId() == TYPE_SOLID );
188 }
189 {
190 std::unique_ptr<Geometry> b = io::readWkt( "POINT(-.1 .1 1)" );
191 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
192 BOOST_CHECK( u->geometryTypeId() == TYPE_GEOMETRYCOLLECTION );
193 }
194 }
195
BOOST_AUTO_TEST_CASE(TriangleTriangle)196 BOOST_AUTO_TEST_CASE( TriangleTriangle )
197 {
198 {
199 std::unique_ptr<Geometry> a = io::readWkt( "TRIANGLE((0 0,1 0,0 1,0 0))" );
200 std::unique_ptr<Geometry> b = io::readWkt( "TRIANGLE((0 0,1 0,0 1,0 0))" );
201 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
202 DEBUG_OUT << u->asText() <<"\n";
203 BOOST_CHECK( *u == *io::readWkt( "TRIANGLE((0 0,0 1,1 0,0 0))" ) );
204 }
205 }
206
BOOST_AUTO_TEST_CASE(PolygonPolygon1)207 BOOST_AUTO_TEST_CASE( PolygonPolygon1 )
208 {
209 {
210 std::unique_ptr<Geometry> a = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1))" );
211 std::unique_ptr<Geometry> b = 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,0.5 -0.5,-0.5 -0.5))" );
212 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
213 BOOST_CHECK( *u == *io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1))" ) );
214 }
215
216 {
217 std::unique_ptr<Geometry> a = io::readWkt( "POLYGON((0 0,1 0,1 1,0 1,0 0))" );
218 std::unique_ptr<Geometry> b = io::readWkt( "POLYGON((1 0,2 0,2 1,1 1,1 0))" );
219 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
220 DEBUG_OUT << u->asText() <<"\n";
221 BOOST_CHECK( *u == *io::readWkt( "POLYGON((0 0,1 0,2 0,2 1,1 1,0 1,0 0))" ) );
222 }
223 }
224
BOOST_AUTO_TEST_CASE(PolygonPolygon2)225 BOOST_AUTO_TEST_CASE( PolygonPolygon2 )
226 {
227 {
228 std::unique_ptr<Geometry> base = io::readWkt( "POLYGON((0 0,1 0,1 1,0 1,0 0))" );
229 Polygon a( base->as<Polygon>() );
230 algorithm::translate( a, .75, 0, 0 ); //disjoined
231 GeometryCollection b;
232 b.addGeometry( base->as<Polygon>() );
233 b.addGeometry( base->as<Polygon>() );
234 algorithm::translate( b.geometryN( 1 ), 1.5, 0, 0 );
235
236 std::unique_ptr<Geometry> u = algorithm::union_( a, b );
237 DEBUG_OUT << u->asText() << "\n";
238 DEBUG_OUT << "area " << algorithm::area3D( *u ) <<"\n";
239 BOOST_CHECK( u->geometryTypeId() == TYPE_POLYGON );
240 BOOST_CHECK( algorithm::area3D( *u ) == 2.5 );
241
242 u = algorithm::union3D( a, b );
243 DEBUG_OUT << u->asText() <<"\n";
244 DEBUG_OUT << "area " << algorithm::area3D( *u ) <<"\n";
245 BOOST_CHECK( u->geometryTypeId() == TYPE_TRIANGULATEDSURFACE );
246 BOOST_CHECK( algorithm::area3D( *u ) == 2.5 );
247 }
248 }
249
BOOST_AUTO_TEST_CASE(PolygonPolygon3)250 BOOST_AUTO_TEST_CASE( PolygonPolygon3 )
251 {
252 std::unique_ptr<Geometry> base = io::readWkt( "POLYGON((0 0,1 0,1 1,0 1,0 0))" );
253 GeometryCollection a;
254 GeometryCollection b;
255
256 for ( unsigned i = 0; i<4; ++i ) {
257 for ( unsigned j = 0; j<4; ++j ) {
258 Polygon p( base->as<Polygon>() );
259 algorithm::translate( p, std::pow( i, 1.3 ), std::pow( j, 1.3 ), 0 );
260 a.addGeometry( p );
261 algorithm::translate( p, .5, .5, 0 );
262 b.addGeometry( p );
263 }
264 }
265
266 std::unique_ptr<Geometry> u = algorithm::union_( a, b );
267 DEBUG_OUT << "surface " << algorithm::area( *u ) << "\n";
268 BOOST_CHECK( std::abs( algorithm::area( *u ) - 25.56 ) < .01 );
269 //TriangulatedSurface ts;
270 //triangulate::triangulatePolygon3D( *u, ts );
271 //io::vtk( ts, "out.vtk" );
272 u = algorithm::union3D( a, b );
273 BOOST_CHECK( std::abs( algorithm::area3D( *u ) - 25.56 ) < .01 );
274 //io::vtk( *u, "out.vtk" );
275 }
276
BOOST_AUTO_TEST_CASE(GardenFailures1)277 BOOST_AUTO_TEST_CASE( GardenFailures1 )
278 {
279 // cgal precondition violation
280 {
281 std::unique_ptr<Geometry> a = io::readWkt( "POLYGON((0 0,10 0,10 0,10 10,0 10,0 0),(2 2,2 5,5 5,5 2,2 2))" );
282 std::unique_ptr<Geometry> b = io::readWkt( "TRIANGLE((-1 -1,1 -1,-1 1,-1 -1))" );
283 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
284 DEBUG_OUT << u->asText() <<"\n";
285 BOOST_CHECK( algorithm::area( *a ) + algorithm::area( *b ) == algorithm::area( *u ) );
286 }
287 }
288
BOOST_AUTO_TEST_CASE(GardenFailures2)289 BOOST_AUTO_TEST_CASE( GardenFailures2 )
290 {
291 // cgal assertion
292 {
293 std::unique_ptr<Geometry> a = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1),(-.5 -.5,-.5 .5,.5 .5,.5 -.5,-.5 -.5))" );
294 std::unique_ptr<Geometry> b = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1),(-.5 -.5,-.5 .5,.5 .5,.5 -.5,-.5 -.5))" );
295 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
296 DEBUG_OUT << u->asText() <<"\n";
297 }
298 }
299
BOOST_AUTO_TEST_CASE(GardenFailures3)300 BOOST_AUTO_TEST_CASE( GardenFailures3 )
301 {
302 // crash (valgrind err) with invalidated iterator after push_back
303 {
304 std::unique_ptr<Geometry> a = io::readWkt( "LINESTRING(-1 -1,1 1)" );
305 std::unique_ptr<Geometry> b = io::readWkt( "MULTILINESTRING((1/1 -1/1 -1/1,1/1 1/1 1/1),(1/1 1/1 1/1,1/1 1/1 -1/1))" );
306 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
307 DEBUG_OUT << u->asText() <<"\n";
308 }
309 }
310
BOOST_AUTO_TEST_CASE(GardenFailures4)311 BOOST_AUTO_TEST_CASE( GardenFailures4 )
312 {
313 // infinite loop
314 {
315 std::unique_ptr<Geometry> a = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1))" );
316 std::unique_ptr<Geometry> b = io::readWkt( "POLYGON((0 0,10 0,10 0,10 10,0 10,0 0))" );
317 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
318 DEBUG_OUT << u->asText() <<"\n";
319 }
320 }
321
BOOST_AUTO_TEST_CASE(GardenFailures5)322 BOOST_AUTO_TEST_CASE( GardenFailures5 )
323 {
324 // infinite loop
325 {
326 std::unique_ptr<Geometry> a = io::readWkt( "MULTIPOLYGON(((-3 -1,-1 -1,-1 1,-3 1,-3 -1)),((1 -1,3 -1,3 1,1 1,1 -1)))" );
327 std::unique_ptr<Geometry> b = io::readWkt( "MULTIPOLYGON(((-3 -1,-1 -1,-1 1,-3 1,-3 -1)),((1 -1,3 -1,3 1,1 1,1 -1)))" );
328 std::unique_ptr<Geometry> u = algorithm::union_( *a, *b );
329 DEBUG_OUT << u->asText() <<"\n";
330 }
331 }
332
BOOST_AUTO_TEST_CASE(GardenFailures6)333 BOOST_AUTO_TEST_CASE( GardenFailures6 )
334 {
335 // segfault
336 {
337 std::unique_ptr<Geometry> a = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1))" );
338 std::unique_ptr<Geometry> b = 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,0.5 -0.5,-0.5 -0.5))" );
339 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
340 DEBUG_OUT << u->asText() <<"\n";
341 }
342 }
343
BOOST_AUTO_TEST_CASE(GardenFailures7)344 BOOST_AUTO_TEST_CASE( GardenFailures7 )
345 {
346 std::unique_ptr<Geometry> a = io::readWkt( "LINESTRING(-1 -1,1 1)" );
347 std::unique_ptr<Geometry> b = io::readWkt( "POLYGON((-1 -1,1 -1,1 1,-1 1,-1 -1),(-.5 -.5,-.5 .5,.5 .5,1 -.5,-.5 -.5))" );
348 std::unique_ptr<Geometry> u = algorithm::union3D( *a, *b );
349 DEBUG_OUT << u->asText() <<"\n";
350 }
351
BOOST_AUTO_TEST_CASE(VolumeVolume)352 BOOST_AUTO_TEST_CASE( VolumeVolume )
353 {
354 std::unique_ptr<Geometry> a = io::readWkt(
355 "SOLID((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)),\
356 ((0 0 0, 0 0 1, 0 1 1, 0 1 0, 0 0 0)),\
357 ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)),\
358 ((1 1 1, 0 1 1, 0 0 1, 1 0 1, 1 1 1)),\
359 ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)),\
360 ((1 1 1, 1 1 0, 0 1 0, 0 1 1, 1 1 1))))" );
361 {
362 Solid b = a->as<Solid>();
363 algorithm::translate( b, 2, 0, 0 ); //disjoined
364 std::unique_ptr<Geometry> u = algorithm::union3D( *a, b );
365 BOOST_CHECK( u->geometryTypeId() == TYPE_MULTISOLID );
366 BOOST_CHECK( algorithm::volume( *u ) == 2 );
367 }
368 {
369 Solid b = a->as<Solid>();
370 algorithm::translate( b, .5, 0, 0 );
371 std::unique_ptr<Geometry> u = algorithm::union3D( *a, b );
372 BOOST_CHECK( u->geometryTypeId() == TYPE_SOLID );
373 BOOST_CHECK( algorithm::volume( *u ) == 1.5 );
374 }
375 {
376 Solid b = a->as<Solid>();
377 algorithm::translate( b, 1, 0, 0 );
378 std::unique_ptr<Geometry> u = algorithm::union3D( *a, b );
379 BOOST_CHECK( u->geometryTypeId() == TYPE_SOLID );
380 BOOST_CHECK( algorithm::volume( *u ) == 2 );
381 }
382
383 {
384 Solid b = a->as<Solid>();
385 algorithm::translate( b, 1, 1, 0 );
386 std::unique_ptr<Geometry> u = algorithm::union3D( *a, b );
387 BOOST_CHECK( u->geometryTypeId() == TYPE_MULTISOLID );
388 BOOST_CHECK( algorithm::volume( *u ) == 2 );
389 }
390
391 {
392 Solid b = a->as<Solid>();
393 algorithm::translate( b, 1, 1, 1 ); // share a corner
394 std::unique_ptr<Geometry> u = algorithm::union3D( *a, b );
395 BOOST_CHECK( u->geometryTypeId() == TYPE_MULTISOLID );
396 BOOST_CHECK( algorithm::volume( *u ) == 2 );
397 }
398 }
399
400 BOOST_AUTO_TEST_SUITE_END()
401
402