1
2 ///////////////////////////////////////////////////////////
3 // //
4 // SAGA //
5 // //
6 // System for Automated Geoscientific Analyses //
7 // //
8 // Application Programming Interface //
9 // //
10 // Library: SAGA_API //
11 // //
12 //-------------------------------------------------------//
13 // //
14 // shapes_polygons.cpp //
15 // //
16 // Copyright (C) 2011 by //
17 // Olaf Conrad //
18 // //
19 //-------------------------------------------------------//
20 // //
21 // This file is part of 'SAGA - System for Automated //
22 // Geoscientific Analyses'. //
23 // //
24 // This library is free software; you can redistribute //
25 // it and/or modify it under the terms of the GNU Lesser //
26 // General Public License as published by the Free //
27 // Software Foundation, either version 2.1 of the //
28 // License, or (at your option) any later version. //
29 // //
30 // This library is distributed in the hope that it will //
31 // be useful, but WITHOUT ANY WARRANTY; without even the //
32 // implied warranty of MERCHANTABILITY or FITNESS FOR A //
33 // PARTICULAR PURPOSE. See the GNU Lesser General Public //
34 // License for more details. //
35 // //
36 // You should have received a copy of the GNU Lesser //
37 // General Public License along with this program; if //
38 // not, see <http://www.gnu.org/licenses/>. //
39 // //
40 //-------------------------------------------------------//
41 // //
42 // e-mail: oconrad@saga-gis.de //
43 // //
44 // contact: Olaf Conrad //
45 // Institute of Geography //
46 // University of Hamburg //
47 // Germany //
48 // //
49 ///////////////////////////////////////////////////////////
50
51 //---------------------------------------------------------
52 #include "shapes.h"
53
54 #include "clipper.hpp"
55
56
57 ///////////////////////////////////////////////////////////
58 // //
59 // //
60 // //
61 ///////////////////////////////////////////////////////////
62
63 //---------------------------------------------------------
64 class CSG_Converter_WorldToInt
65 {
66 public:
67
CSG_Converter_WorldToInt(void)68 CSG_Converter_WorldToInt (void) { Create(0.0, 1.0, 0.0, 1.0); }
CSG_Converter_WorldToInt(const CSG_Converter_WorldToInt & Converter)69 CSG_Converter_WorldToInt (const CSG_Converter_WorldToInt &Converter) { Create(Converter); }
CSG_Converter_WorldToInt(double xOffset,double xScale,double yOffset,double yScale)70 CSG_Converter_WorldToInt (double xOffset, double xScale, double yOffset, double yScale) { Create(xOffset, xScale, yOffset, yScale); }
CSG_Converter_WorldToInt(const CSG_Rect & Extent,bool bAspectRatio=false)71 CSG_Converter_WorldToInt (const CSG_Rect &Extent, bool bAspectRatio = false) { Create(Extent, bAspectRatio); }
72
Create(const CSG_Converter_WorldToInt & Converter)73 bool Create (const CSG_Converter_WorldToInt &Converter)
74 {
75 return( Create(Converter.m_xOffset, Converter.m_xScale, Converter.m_yOffset, Converter.m_yScale) );
76 }
77
Create(double xOffset,double xScale,double yOffset,double yScale)78 bool Create (double xOffset, double xScale, double yOffset, double yScale)
79 {
80 if( xScale != 0.0 && yScale != 0.0 )
81 {
82 m_xOffset = xOffset;
83 m_xScale = xScale;
84 m_yOffset = yOffset;
85 m_yScale = yScale;
86
87 return( true );
88 }
89
90 return( false );
91 }
92
Create(const CSG_Rect & Extent,bool bAspectRatio=false)93 bool Create (const CSG_Rect &Extent, bool bAspectRatio = false)
94 {
95 double xRange = Extent.Get_XRange();
96 double yRange = Extent.Get_YRange();
97 double xMin = Extent.Get_XMin ();
98 double yMin = Extent.Get_YMin ();
99
100 if( bAspectRatio )
101 {
102 if( xRange < yRange )
103 {
104 xRange = yRange;
105 }
106 else if( yRange < xRange )
107 {
108 yRange = xRange;
109 }
110 }
111
112 return( xRange > 0 && yRange > 0 ? Create(
113 xMin, (0x3FFFFFFFFFFFFFF) / xRange,
114 yMin, (0x3FFFFFFFFFFFFFF) / yRange
115 ) : false);
116 }
117
Round(double Value)118 static ClipperLib::cInt Round (double Value) { return( (ClipperLib::cInt)(Value < 0.0 ? Value - 0.5 : Value + 0.5) ); }
119
Get_X_asInt(double Value) const120 ClipperLib::cInt Get_X_asInt (double Value) const { return( Round((Value - m_xOffset) * m_xScale) ); }
Get_Y_asInt(double Value) const121 ClipperLib::cInt Get_Y_asInt (double Value) const { return( Round((Value - m_yOffset) * m_yScale) ); }
122
Get_X_asWorld(ClipperLib::cInt Value) const123 double Get_X_asWorld (ClipperLib::cInt Value) const { return( m_xOffset + Value / m_xScale ); }
Get_Y_asWorld(ClipperLib::cInt Value) const124 double Get_Y_asWorld (ClipperLib::cInt Value) const { return( m_yOffset + Value / m_yScale ); }
125
126 bool Convert (CSG_Shapes *pPolygons , ClipperLib::Paths &P ) const;
127 bool Convert (const ClipperLib::Paths &P, CSG_Shapes *pPolygons) const;
128
129 bool Convert (CSG_Shape *pPolygon , ClipperLib::Paths &P) const;
130 bool Convert (const ClipperLib::Paths &P, CSG_Shape *pPolygon ) const;
131
Get_xScale(void) const132 double Get_xScale (void) const { return( m_xScale ); }
Get_yScale(void) const133 double Get_yScale (void) const { return( m_yScale ); }
134
135
136 private:
137
138 double m_xOffset, m_xScale, m_yOffset, m_yScale;
139
140
141 };
142
143
144 ///////////////////////////////////////////////////////////
145 // //
146 ///////////////////////////////////////////////////////////
147
148 //---------------------------------------------------------
Convert(CSG_Shapes * pPolygons,ClipperLib::Paths & Polygons) const149 bool CSG_Converter_WorldToInt::Convert(CSG_Shapes *pPolygons, ClipperLib::Paths &Polygons) const
150 {
151 Polygons.clear();
152
153 for(int iPolygon=0, jPolygon=0; iPolygon<pPolygons->Get_Count(); iPolygon++)
154 {
155 CSG_Shape *pPolygon = pPolygons->Get_Shape(iPolygon);
156
157 for(int iPart=0; iPart<pPolygon->Get_Part_Count(); iPart++, jPolygon++)
158 {
159 bool bAscending = pPolygon->Get_Type() != SHAPE_TYPE_Polygon
160 || (((CSG_Shape_Polygon *)pPolygon)->is_Lake(iPart)
161 == ((CSG_Shape_Polygon *)pPolygon)->is_Clockwise(iPart));
162
163 Polygons.resize(1 + jPolygon);
164 Polygons[jPolygon].resize(pPolygon->Get_Point_Count(iPart));
165
166 for(int iPoint=0; iPoint<pPolygon->Get_Point_Count(iPart); iPoint++)
167 {
168 TSG_Point p = pPolygon->Get_Point(iPoint, iPart, bAscending);
169
170 Polygons[jPolygon][iPoint].X = Get_X_asInt(p.x);
171 Polygons[jPolygon][iPoint].Y = Get_Y_asInt(p.y);
172 }
173 }
174 }
175
176 return( Polygons.size() > 0 );
177 }
178
179 //---------------------------------------------------------
Convert(const ClipperLib::Paths & Polygons,CSG_Shapes * pPolygons) const180 bool CSG_Converter_WorldToInt::Convert(const ClipperLib::Paths &Polygons, CSG_Shapes *pPolygons) const
181 {
182 pPolygons->Del_Shapes();
183
184 CSG_Shape *pPolygon = pPolygons->Add_Shape();
185
186 return( Convert(Polygons, pPolygon) );
187 }
188
189
190 ///////////////////////////////////////////////////////////
191 // //
192 ///////////////////////////////////////////////////////////
193
194 //---------------------------------------------------------
Convert(CSG_Shape * pPolygon,ClipperLib::Paths & Polygons) const195 bool CSG_Converter_WorldToInt::Convert(CSG_Shape *pPolygon, ClipperLib::Paths &Polygons) const
196 {
197 Polygons.clear();
198
199 for(int iPart=0, iPolygon=0; iPart<pPolygon->Get_Part_Count(); iPart++, iPolygon++)
200 {
201 if( pPolygon->Get_Point_Count(iPart) > 0 )
202 {
203 bool bAscending = pPolygon->Get_Type() != SHAPE_TYPE_Polygon
204 || (((CSG_Shape_Polygon *)pPolygon)->is_Lake(iPart)
205 == ((CSG_Shape_Polygon *)pPolygon)->is_Clockwise(iPart));
206
207 Polygons.resize(1 + iPolygon);
208
209 for(int iPoint=0; iPoint<pPolygon->Get_Point_Count(iPart); iPoint++)
210 {
211 TSG_Point p = pPolygon->Get_Point(iPoint, iPart, bAscending);
212
213 ClipperLib::IntPoint Point(Get_X_asInt(p.x), Get_Y_asInt(p.y));
214
215 if( iPoint == 0 || Polygons[iPolygon].back() != Point ) // don't add duplicates !!!
216 {
217 Polygons[iPolygon].push_back(Point);
218 }
219 }
220
221 if( pPolygon->Get_Type() == SHAPE_TYPE_Polygon && Polygons[iPolygon].size() > 1 && Polygons[iPolygon][0] == Polygons[iPolygon].back() )
222 {
223 Polygons[iPolygon].pop_back();
224 }
225 }
226 }
227
228 return( Polygons.size() > 0 );
229 }
230
231 //---------------------------------------------------------
Convert(const ClipperLib::Paths & Polygons,CSG_Shape * pPolygon) const232 bool CSG_Converter_WorldToInt::Convert(const ClipperLib::Paths &Polygons, CSG_Shape *pPolygon) const
233 {
234 pPolygon->Del_Parts();
235
236 for(size_t iPolygon=0, iPart=0; iPolygon<Polygons.size(); iPolygon++)
237 {
238 for(size_t iPoint=0; iPoint<Polygons[iPolygon].size(); iPoint++)
239 {
240 pPolygon->Add_Point(
241 Get_X_asWorld(Polygons[iPolygon][iPoint].X),
242 Get_Y_asWorld(Polygons[iPolygon][iPoint].Y),
243 (int)iPart
244 );
245 }
246
247 if( pPolygon->Get_Type() != SHAPE_TYPE_Polygon || ((CSG_Shape_Polygon *)pPolygon)->Get_Area((int)iPart) > (1.0e-12) )
248 {
249 iPart++;
250 }
251 else
252 {
253 pPolygon->Del_Part((int)iPart);
254 }
255 }
256
257 return( pPolygon->Get_Part_Count() > 0 );
258 }
259
260
261 ///////////////////////////////////////////////////////////
262 // //
263 ///////////////////////////////////////////////////////////
264
265 //---------------------------------------------------------
_SG_Polygon_Clip(ClipperLib::ClipType ClipType,CSG_Shape * pPolygon,CSG_Shape * pClip,CSG_Shape * pResult)266 bool _SG_Polygon_Clip(ClipperLib::ClipType ClipType, CSG_Shape *pPolygon, CSG_Shape *pClip, CSG_Shape *pResult)
267 {
268 CSG_Rect r(pPolygon->Get_Extent()); r.Union(pClip->Get_Extent());
269
270 CSG_Converter_WorldToInt Converter(r);
271
272 ClipperLib::Paths Polygon, Clip, Result;
273
274 if( Converter.Convert(pPolygon, Polygon)
275 && Converter.Convert(pClip , Clip ) )
276 {
277 ClipperLib::Clipper Clipper;
278
279 Clipper.AddPaths(Clip, ClipperLib::ptClip, true);
280
281 if( pPolygon->Get_Type() != SHAPE_TYPE_Line )
282 {
283 Clipper.AddPaths(Polygon, ClipperLib::ptSubject, true);
284
285 if( !Clipper.Execute(ClipType, Result) )
286 {
287 return( false );
288 }
289 }
290 else
291 {
292 Clipper.AddPaths(Polygon, ClipperLib::ptSubject, false);
293
294 ClipperLib::PolyTree PolyTree;
295
296 if( !Clipper.Execute(ClipType, PolyTree) )
297 {
298 return( false );
299 }
300
301 ClipperLib::PolyTreeToPaths(PolyTree, Result);
302 }
303
304 return( Converter.Convert(Result, pResult ? pResult : pPolygon) );
305 }
306
307 return( false );
308 }
309
310
311 ///////////////////////////////////////////////////////////
312 // //
313 ///////////////////////////////////////////////////////////
314
315 //---------------------------------------------------------
SG_Polygon_Intersection(CSG_Shape * pPolygon,CSG_Shape * pClip,CSG_Shape * pResult)316 bool SG_Polygon_Intersection (CSG_Shape *pPolygon, CSG_Shape *pClip, CSG_Shape *pResult)
317 {
318 switch( pClip->Intersects(pPolygon) )
319 {
320 case INTERSECTION_None:
321 return( false );
322
323 case INTERSECTION_Identical:
324 case INTERSECTION_Contains:
325 if( pResult ) pResult->Assign(pPolygon, false);
326 return( true );
327
328 case INTERSECTION_Contained:
329 if( pResult ) pResult ->Assign(pClip , false);
330 else pPolygon->Assign(pClip , false);
331 return( true );
332
333 case INTERSECTION_Overlaps: default:
334 return( _SG_Polygon_Clip(ClipperLib::ctIntersection , pPolygon, pClip, pResult) );
335 }
336 }
337
338 //---------------------------------------------------------
SG_Polygon_Difference(CSG_Shape * pPolygon,CSG_Shape * pClip,CSG_Shape * pResult)339 bool SG_Polygon_Difference (CSG_Shape *pPolygon, CSG_Shape *pClip, CSG_Shape *pResult)
340 {
341 switch( pClip->Intersects(pPolygon) )
342 {
343 case INTERSECTION_Contains:
344 case INTERSECTION_Identical:
345 return( false );
346
347 case INTERSECTION_None:
348 if( pResult ) pResult->Assign(pPolygon, false);
349 return( true );
350
351 case INTERSECTION_Contained:
352 case INTERSECTION_Overlaps: default:
353 return( _SG_Polygon_Clip(ClipperLib::ctDifference , pPolygon, pClip, pResult) );
354 }
355 }
356
357 //---------------------------------------------------------
SG_Polygon_ExclusiveOr(CSG_Shape * pPolygon,CSG_Shape * pClip,CSG_Shape * pResult)358 bool SG_Polygon_ExclusiveOr (CSG_Shape *pPolygon, CSG_Shape *pClip, CSG_Shape *pResult)
359 {
360 switch( pClip->Intersects(pPolygon) )
361 {
362 case INTERSECTION_Identical:
363 return( false );
364
365 case INTERSECTION_None:
366 if( pResult ) pResult->Assign(pPolygon, false);
367 else pResult = pPolygon;
368
369 { for(int iPart=0, jPart=pResult->Get_Part_Count(); iPart<pClip->Get_Part_Count(); iPart++, jPart++)
370 {
371 for(int iPoint=0; iPoint<pClip->Get_Point_Count(iPart); iPoint++)
372 {
373 pResult->Add_Point(pClip->Get_Point(iPoint, iPart), jPart);
374 }
375 }
376 }
377
378 return( true );
379
380 case INTERSECTION_Contained:
381 case INTERSECTION_Contains:
382 case INTERSECTION_Overlaps: default:
383 return( _SG_Polygon_Clip(ClipperLib::ctXor , pPolygon, pClip, pResult) );
384 }
385 }
386
387 //---------------------------------------------------------
SG_Polygon_Union(CSG_Shape * pPolygon,CSG_Shape * pClip,CSG_Shape * pResult)388 bool SG_Polygon_Union (CSG_Shape *pPolygon, CSG_Shape *pClip, CSG_Shape *pResult)
389 {
390 switch( pClip->Intersects(pPolygon) )
391 {
392 case INTERSECTION_Contained:
393 case INTERSECTION_Identical:
394 if( pResult ) pResult->Assign(pPolygon, false);
395 return( true );
396
397 case INTERSECTION_Contains:
398 if( pResult ) pResult ->Assign(pClip , false);
399 else pPolygon->Assign(pClip , false);
400 return( true );
401
402 case INTERSECTION_None:
403 if( pResult ) pResult->Assign(pPolygon, false);
404 else pResult = pPolygon;
405
406 { for(int iPart=0, jPart=pResult->Get_Part_Count(); iPart<pClip->Get_Part_Count(); iPart++, jPart++)
407 {
408 for(int iPoint=0; iPoint<pClip->Get_Point_Count(iPart); iPoint++)
409 {
410 pResult->Add_Point(pClip->Get_Point(iPoint, iPart), jPart);
411 }
412 }
413 }
414
415 return( true );
416
417 case INTERSECTION_Overlaps: default:
418 return( _SG_Polygon_Clip(ClipperLib::ctUnion , pPolygon, pClip, pResult) );
419 }
420 }
421
422 //---------------------------------------------------------
SG_Polygon_Dissolve(CSG_Shape * pPolygon,CSG_Shape * pResult)423 bool SG_Polygon_Dissolve (CSG_Shape *pPolygon, CSG_Shape *pResult)
424 {
425 CSG_Converter_WorldToInt Converter(pPolygon->Get_Extent());
426
427 ClipperLib::Paths Polygon, Result;
428
429 if( Converter.Convert(pPolygon, Polygon) )
430 {
431 ClipperLib::Clipper Clipper;
432
433 Clipper.AddPaths(Polygon, ClipperLib::ptSubject, true);
434
435 Clipper.Execute(ClipperLib::ctUnion, Result);
436
437 return( Converter.Convert(Result, pResult ? pResult : pPolygon) );
438 }
439
440 return( false );
441 }
442
443 //---------------------------------------------------------
SG_Polygon_Simplify(CSG_Shape * pPolygon,CSG_Shape * pResult)444 bool SG_Polygon_Simplify (CSG_Shape *pPolygon, CSG_Shape *pResult)
445 {
446 CSG_Converter_WorldToInt Converter(pPolygon->Get_Extent());
447
448 ClipperLib::Paths Polygon, Result;
449
450 if( Converter.Convert(pPolygon, Polygon) )
451 {
452 ClipperLib::SimplifyPolygons(Polygon, Result);
453
454 return( Converter.Convert(Result, pResult ? pResult : pPolygon) );
455 }
456
457 return( false );
458 }
459
460 //---------------------------------------------------------
SG_Polygon_Offset(CSG_Shape * pPolygon,double dSize,double dArc,CSG_Shape * pResult)461 bool SG_Polygon_Offset (CSG_Shape *pPolygon, double dSize, double dArc, CSG_Shape *pResult)
462 {
463 CSG_Rect r(pPolygon->Get_Extent()); if( dSize > 0.0 ) r.Inflate(5.0 * dSize, false);
464
465 CSG_Converter_WorldToInt Converter(r, true);
466
467 ClipperLib::Paths Paths, Result;
468
469 if( Converter.Convert(pPolygon, Paths) )
470 {
471 ClipperLib::ClipperOffset Offset(2.0, dArc * Converter.Get_xScale());
472
473 if( pPolygon->Get_Type() == SHAPE_TYPE_Polygon )
474 {
475 Offset.AddPaths(Paths, ClipperLib::jtRound, ClipperLib::etClosedPolygon);
476 }
477 else
478 {
479 Offset.AddPaths(Paths, ClipperLib::jtRound, ClipperLib::etOpenRound);
480 }
481
482 Offset.Execute(Result, dSize * Converter.Get_xScale());
483
484 return( Converter.Convert(Result, pResult ? pResult : pPolygon) );
485 }
486
487 return( false );
488 }
489
490
491 ///////////////////////////////////////////////////////////
492 // //
493 // //
494 // //
495 ///////////////////////////////////////////////////////////
496
497 //---------------------------------------------------------
498