SAGA API  v9.8
shapes_clipper.cpp
Go to the documentation of this file.
1 
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_clipper.cpp //
15 // //
16 // Copyright (C) 2022 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 // //
50 
51 //---------------------------------------------------------
52 #include "shapes.h"
53 
54 #include "clipper2/clipper.h"
55 
56 
58 // //
59 // //
60 // //
62 
63 //---------------------------------------------------------
64 class CSG_Clipper
65 {
66 public:
67 
68  CSG_Clipper(void) {}
69 
70  //-----------------------------------------------------
71  static bool to_Paths (const CSG_Shapes *pShapes, Clipper2Lib::PathsD &Paths)
72  {
73  if( !pShapes )
74  {
75  return( false );
76  }
77 
78  Paths.clear();
79 
80  for(sLong iShape=0, iPath=0; iShape<pShapes->Get_Count(); iShape++)
81  {
82  CSG_Shape &Shape = *pShapes->Get_Shape(iShape);
83 
84  for(int iPart=0; iPart<Shape.Get_Part_Count(); iPart++, iPath++)
85  {
86  bool bAscending = Shape.Get_Type() != SHAPE_TYPE_Polygon
87  || (Shape.asPolygon()->is_Lake (iPart)
88  == Shape.asPolygon()->is_Clockwise(iPart));
89 
90  Paths.resize(1 + iPath);
91  Paths[iPath].resize(Shape.Get_Point_Count(iPart));
92 
93  for(int iPoint=0; iPoint<Shape.Get_Point_Count(iPart); iPoint++)
94  {
95  TSG_Point p = Shape.Get_Point(iPoint, iPart, bAscending);
96 
97  Paths[iPath][iPoint].x = p.x;
98  Paths[iPath][iPoint].y = p.y;
99  }
100  }
101  }
102 
103  return( Paths.size() > 0 );
104  }
105 
106  //-----------------------------------------------------
107  static bool to_Shape (const Clipper2Lib::PathsD &Paths, CSG_Shapes *pShapes)
108  {
109  return( pShapes && pShapes->Del_Shapes() && to_Shape(Paths, pShapes->Add_Shape()) );
110  }
111 
112  //-----------------------------------------------------
113  static bool to_Paths (const CSG_Shape *pShape, Clipper2Lib::PathsD &Paths, bool bCheckOrientation = true)
114  {
115  if( !pShape )
116  {
117  return( false );
118  }
119 
120  Paths.clear();
121 
122  for(int iPart=0, iPath=0; iPart<pShape->Get_Part_Count(); iPart++, iPath++)
123  {
124  if( pShape->Get_Point_Count(iPart) > 0 )
125  {
126  bool bAscending = !bCheckOrientation || pShape->Get_Type() != SHAPE_TYPE_Polygon
127  || (pShape->asPolygon()->is_Lake (iPart)
128  == pShape->asPolygon()->is_Clockwise(iPart));
129 
130  Paths.resize(1 + iPath);
131 
132  for(int iPoint=0; iPoint<pShape->Get_Point_Count(iPart); iPoint++)
133  {
134  TSG_Point p = pShape->Get_Point(iPoint, iPart, bAscending);
135 
136  Clipper2Lib::PointD Point(p.x, p.y);
137 
138  if( iPoint == 0 || Paths[iPath].back() != Point ) // don't add duplicates !!!
139  {
140  Paths[iPath].push_back(Point);
141  }
142  }
143 
144  if( pShape->Get_Type() == SHAPE_TYPE_Polygon && Paths[iPath].size() > 1 && Paths[iPath][0] == Paths[iPath].back() )
145  {
146  Paths[iPath].pop_back();
147  }
148  }
149  }
150 
151  return( Paths.size() > 0 );
152  }
153 
154  //-----------------------------------------------------
155  static bool to_Shape (const Clipper2Lib::PathsD &Paths, CSG_Shape *pShape)
156  {
157  if( !pShape )
158  {
159  return( false );
160  }
161 
162  pShape->Del_Parts();
163 
164  for(size_t iPath=0; iPath<Paths.size(); iPath++)
165  {
166  for(size_t iPoint=0; iPoint<Paths[iPath].size(); iPoint++)
167  {
168  pShape->Add_Point(Paths[iPath][iPoint].x, Paths[iPath][iPoint].y, (int)iPath);
169  }
170  }
171 
172  return( pShape->is_Valid() );
173  }
174 
175  //-----------------------------------------------------
176  static bool Clip (Clipper2Lib::ClipType ClipType, CSG_Shape *pSubject, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
177  {
178  Clipper2Lib::PathsD Subject, Clip, Solution;
179 
180  if( to_Paths(pSubject, Subject)
181  && to_Paths(pClip , Clip ) )
182  {
183  Clipper2Lib::ClipperD Clipper(m_Precision);
184 
185  Clipper.AddClip(Clip);
186 
187  if( pSubject->Get_Type() == SHAPE_TYPE_Polygon )
188  {
189  Clipper.AddSubject(Subject);
190 
191  if( !Clipper.Execute(ClipType, Clipper2Lib::FillRule::NonZero, Solution) )
192  {
193  return( false );
194  }
195  }
196  else
197  {
198  Clipper.AddOpenSubject(Subject);
199 
200  if( !Clipper.Execute(ClipType, Clipper2Lib::FillRule::NonZero, Solution) )
201  {
202  return( false );
203  }
204  }
205 
206  return( to_Shape(Solution, pSolution ? pSolution : pSubject) );
207  }
208 
209  return( false );
210  }
211 
212  //-----------------------------------------------------
213  static bool Dissolve (CSG_Shape *pShape, CSG_Shape *pSolution)
214  {
215  Clipper2Lib::PathsD Subject, Solution;
216 
217  if( to_Paths(pShape, Subject, false) )
218  {
219  Clipper2Lib::ClipperD Clipper(m_Precision);
220 
221  Clipper.AddSubject(Subject);
222 
223  if( Clipper.Execute(Clipper2Lib::ClipType::Union, Clipper2Lib::FillRule::NonZero, Solution) )
224  {
225  return( to_Shape(Solution, pSolution ? pSolution : pShape) );
226  }
227  }
228 
229  return( false );
230  }
231 
232  //-----------------------------------------------------
233  static bool Offset (CSG_Shape *pShape, double Delta, double dArc, CSG_Shape *pSolution, TSG_Line_JoinType JoinType, TSG_Line_EndType EndType)
234  {
235  Clipper2Lib::PathsD Paths, Solution;
236 
237  if( to_Paths(pShape, Paths) )
238  {
239  Clipper2Lib::EndType ClipperEndType;
240 
241  if( pShape->Get_Type() != SHAPE_TYPE_Polygon )
242  {
243  ClipperEndType = Clipper2Lib::EndType(EndType);
244  }
245  else
246  {
247  ClipperEndType = Clipper2Lib::EndType::Polygon;
248  }
249 
250  double ArcTolerance = std::pow(10., m_Precision) * Delta * (1. - cos(dArc / 2.));
251 
252  Solution = Clipper2Lib::InflatePaths(Paths, Delta, Clipper2Lib::JoinType(JoinType), ClipperEndType, 2., m_Precision, ArcTolerance);
253 
254  return( to_Shape(Solution, pSolution ? pSolution : pShape) );
255  }
256 
257  return( false );
258  }
259 
260  //-----------------------------------------------------
261  static int Get_Precision (void) { return( m_Precision ); }
262 
263  static bool Set_Precision (int Precision)
264  {
265  if( Precision < -8 || Precision > 8 )
266  {
267  return( false );
268  }
269 
270  m_Precision = Precision;
271 
272  return( true );
273  }
274 
275  private:
276 
277  static int m_Precision;
278 };
279 
280 //---------------------------------------------------------
281 int CSG_Clipper::m_Precision = 4;
282 
283 
285 // //
286 // //
287 // //
289 
290 //---------------------------------------------------------
291 bool SG_Shape_Get_Intersection (CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
292 {
293  switch( pClip->Intersects(pShape) )
294  {
295  case INTERSECTION_None :
296  return( false );
297 
298  case INTERSECTION_Identical:
299  case INTERSECTION_Contains :
300  return( !pSolution || pSolution->Assign(pShape, false) );
301 
302  case INTERSECTION_Contained:
303  return( !pSolution ? pShape->Assign(pClip, false) : pSolution->Assign(pClip, false) );
304 
305  case INTERSECTION_Overlaps : default:
306  return( CSG_Clipper::Clip(Clipper2Lib::ClipType::Intersection, pShape, pClip, pSolution) );
307  }
308 }
309 
310 //---------------------------------------------------------
311 bool SG_Shape_Get_Difference (CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
312 {
313  switch( pClip->Intersects(pShape) )
314  {
315  case INTERSECTION_None :
316  return( !pSolution || pSolution->Assign(pShape, false) );
317 
318  case INTERSECTION_Identical:
319  case INTERSECTION_Contains :
320  return( false );
321 
322  case INTERSECTION_Contained:
323  case INTERSECTION_Overlaps : default:
324  return( CSG_Clipper::Clip(Clipper2Lib::ClipType::Difference, pShape, pClip, pSolution) );
325  }
326 }
327 
328 //---------------------------------------------------------
329 bool SG_Shape_Get_ExclusiveOr (CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
330 {
331  switch( pClip->Intersects(pShape) )
332  {
333  case INTERSECTION_None :
334  if( pSolution ) { pSolution->Assign(pShape, false); } else { pSolution = pShape; }
335 
336  for(int iPart=0; iPart<pClip->Get_Part_Count(); iPart++)
337  {
338  pSolution->Add_Part(pClip->Get_Part(iPart));
339  }
340  return( true );
341 
342  case INTERSECTION_Identical:
343  return( false );
344 
345  case INTERSECTION_Contains :
346  case INTERSECTION_Contained:
347  case INTERSECTION_Overlaps : default:
348  return( CSG_Clipper::Clip(Clipper2Lib::ClipType::Xor, pShape, pClip, pSolution) );
349  }
350 }
351 
352 //---------------------------------------------------------
353 bool SG_Shape_Get_Union (CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
354 {
355  switch( pClip->Intersects(pShape) )
356  {
357  case INTERSECTION_None :
358  if( pSolution ) { pSolution->Assign(pShape, false); } else { pSolution = pShape; }
359 
360  for(int iPart=0; iPart<pClip->Get_Part_Count(); iPart++)
361  {
362  pSolution->Add_Part(pClip->Get_Part(iPart));
363  }
364  return( true );
365 
366  case INTERSECTION_Identical:
367  case INTERSECTION_Contained:
368  return( !pSolution || pSolution->Assign(pShape, false) );
369 
370  case INTERSECTION_Contains :
371  return( !pSolution ? pShape->Assign(pClip, false) : pSolution->Assign(pClip, false) );
372 
373  case INTERSECTION_Overlaps: default:
374  return( CSG_Clipper::Clip(Clipper2Lib::ClipType::Union, pShape, pClip, pSolution) );
375  }
376 }
377 
378 //---------------------------------------------------------
387 //---------------------------------------------------------
388 bool SG_Shape_Get_Dissolve (CSG_Shape *pShape, CSG_Shape *pSolution)
389 {
390  return( CSG_Clipper::Dissolve(pShape, pSolution) );
391 }
392 
393 //---------------------------------------------------------
394 bool SG_Shape_Get_Offset (CSG_Shape *pShape, double Size, double dArc, CSG_Shape *pSolution, TSG_Line_JoinType JoinType, TSG_Line_EndType EndType)
395 {
396  return( CSG_Clipper::Offset(pShape, Size, dArc, pSolution, JoinType, EndType) );
397 }
398 
399 
401 // //
403 
404 //---------------------------------------------------------
405 const char * SG_Clipper_Get_Version (void)
406 {
407  static CSG_String Version(CSG_String("Clipper2 ") + CLIPPER2_VERSION);
408 
409  return( Version );
410 }
411 
412 
414 // //
415 // //
416 // //
418 
419 //---------------------------------------------------------
CSG_Shapes::Get_Shape
virtual CSG_Shape * Get_Shape(const CSG_Point &Point, double Epsilon=0.)
Definition: shapes.cpp:483
CSG_Table_Record::is_Valid
virtual bool is_Valid(void) const
Definition: table.h:138
CSG_Shape_Polygon::is_Clockwise
bool is_Clockwise(int iPart)
Definition: shape_polygon.cpp:826
CSG_Shape::Del_Parts
virtual int Del_Parts(void)
Definition: shapes.h:169
SHAPE_TYPE_Polygon
@ SHAPE_TYPE_Polygon
Definition: shapes.h:105
INTERSECTION_Contains
@ INTERSECTION_Contains
Definition: geo_tools.h:106
SG_Shape_Get_Dissolve
bool SG_Shape_Get_Dissolve(CSG_Shape *pShape, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:388
CSG_Shape::Intersects
TSG_Intersection Intersects(CSG_Shape *pShape)
Definition: shape.cpp:118
CSG_Shape::Add_Part
virtual int Add_Part(class CSG_Shape_Part *pPart, bool bRevert=false)
Definition: shapes.h:166
SSG_Point
Definition: geo_tools.h:128
CSG_Shape::Get_Type
TSG_Shape_Type Get_Type(void) const
Definition: shape.cpp:88
CSG_Shape::Get_Point
virtual TSG_Point Get_Point(int iPoint=0) const =0
CSG_Shapes::Add_Shape
virtual CSG_Shape * Add_Shape(CSG_Table_Record *pCopy=NULL, TSG_ADD_Shape_Copy_Mode mCopy=SHAPE_COPY)
Definition: shapes.cpp:402
CSG_Shape::Get_Part_Count
virtual int Get_Part_Count(void) const =0
CSG_Shapes::Del_Shapes
virtual bool Del_Shapes(void)
Definition: shapes.h:822
SG_Shape_Get_Union
bool SG_Shape_Get_Union(CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:353
INTERSECTION_None
@ INTERSECTION_None
Definition: geo_tools.h:102
sLong
signed long long sLong
Definition: api_core.h:158
SG_Shape_Get_Offset
bool SG_Shape_Get_Offset(CSG_Shape *pShape, double Size, double dArc, CSG_Shape *pSolution, TSG_Line_JoinType JoinType, TSG_Line_EndType EndType)
Definition: shapes_clipper.cpp:394
SG_Clipper_Get_Version
const char * SG_Clipper_Get_Version(void)
Definition: shapes_clipper.cpp:405
CSG_Table::Get_Count
sLong Get_Count(void) const
Definition: table.h:397
SG_Shape_Get_ExclusiveOr
bool SG_Shape_Get_ExclusiveOr(CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:329
CSG_Shape::Add_Point
virtual int Add_Point(double x, double y, int iPart=0)=0
INTERSECTION_Identical
@ INTERSECTION_Identical
Definition: geo_tools.h:103
CSG_Shape::Assign
virtual bool Assign(CSG_Table_Record *pRecord)
Definition: shape.cpp:195
TSG_Line_JoinType
TSG_Line_JoinType
Definition: shapes.h:1449
SG_Shape_Get_Difference
bool SG_Shape_Get_Difference(CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:311
CSG_Shape::Get_Point_Count
virtual int Get_Point_Count(void) const =0
shapes.h
CSG_String
Definition: api_core.h:563
CSG_Shape_Points::Get_Part
virtual CSG_Shape_Part * Get_Part(int iPart) const
Definition: shapes.h:499
SSG_Point::x
double x
Definition: geo_tools.h:129
TSG_Line_EndType
TSG_Line_EndType
Definition: shapes.h:1459
SSG_Point::y
double y
Definition: geo_tools.h:129
CSG_Shape_Polygon::is_Lake
bool is_Lake(int iPart)
Definition: shape_polygon.cpp:766
CSG_Shapes
Definition: shapes.h:773
CSG_Shape::asPolygon
class CSG_Shape_Polygon * asPolygon(void) const
Definition: shapes.h:159
INTERSECTION_Contained
@ INTERSECTION_Contained
Definition: geo_tools.h:105
CSG_Shape_Points::Get_Part_Count
virtual int Get_Part_Count(void) const
Definition: shapes.h:496
CSG_Shape_Polygon
Definition: shapes.h:699
INTERSECTION_Overlaps
@ INTERSECTION_Overlaps
Definition: geo_tools.h:104
CSG_Shape
Definition: shapes.h:141
SG_Shape_Get_Intersection
bool SG_Shape_Get_Intersection(CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:291