SAGA API  v9.5
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)
234  {
235  Clipper2Lib::PathsD Paths, Solution;
236 
237  if( to_Paths(pShape, Paths) )
238  {
239  Clipper2Lib::EndType EndType;
240 
241  if( pShape->Get_Type() != SHAPE_TYPE_Polygon )
242  {
243  Delta *= 2.;
244 
245  EndType = Clipper2Lib::EndType::Round;
246  }
247  else
248  {
249  EndType = Clipper2Lib::EndType::Polygon;
250  }
251 
252  double ArcTolerance = std::pow(10., m_Precision) * Delta * (1. - cos(dArc / 2.));
253 
254  Solution = Clipper2Lib::InflatePaths(Paths, Delta, Clipper2Lib::JoinType::Round, EndType, 2., m_Precision, ArcTolerance);
255 
256  return( to_Shape(Solution, pSolution ? pSolution : pShape) );
257  }
258 
259  return( false );
260  }
261 
262  //-----------------------------------------------------
263  static int Get_Precision (void) { return( m_Precision ); }
264 
265  static bool Set_Precision (int Precision)
266  {
267  if( Precision < -8 || Precision > 8 )
268  {
269  return( false );
270  }
271 
272  m_Precision = Precision;
273 
274  return( true );
275  }
276 
277  private:
278 
279  static int m_Precision;
280 };
281 
282 //---------------------------------------------------------
283 int CSG_Clipper::m_Precision = 4;
284 
285 
287 // //
288 // //
289 // //
291 
292 //---------------------------------------------------------
293 bool SG_Shape_Get_Intersection (CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
294 {
295  switch( pClip->Intersects(pShape) )
296  {
297  case INTERSECTION_None :
298  return( false );
299 
300  case INTERSECTION_Identical:
301  case INTERSECTION_Contains :
302  return( !pSolution || pSolution->Assign(pShape, false) );
303 
304  case INTERSECTION_Contained:
305  return( !pSolution ? pShape->Assign(pClip, false) : pSolution->Assign(pClip, false) );
306 
307  case INTERSECTION_Overlaps : default:
308  return( CSG_Clipper::Clip(Clipper2Lib::ClipType::Intersection, pShape, pClip, pSolution) );
309  }
310 }
311 
312 //---------------------------------------------------------
313 bool SG_Shape_Get_Difference (CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
314 {
315  switch( pClip->Intersects(pShape) )
316  {
317  case INTERSECTION_None :
318  return( !pSolution || pSolution->Assign(pShape, false) );
319 
320  case INTERSECTION_Identical:
321  case INTERSECTION_Contains :
322  return( false );
323 
324  case INTERSECTION_Contained:
325  case INTERSECTION_Overlaps : default:
326  return( CSG_Clipper::Clip(Clipper2Lib::ClipType::Difference, pShape, pClip, pSolution) );
327  }
328 }
329 
330 //---------------------------------------------------------
331 bool SG_Shape_Get_ExclusiveOr (CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
332 {
333  switch( pClip->Intersects(pShape) )
334  {
335  case INTERSECTION_None :
336  if( pSolution ) { pSolution->Assign(pShape, false); } else { pSolution = pShape; }
337 
338  for(int iPart=0; iPart<pClip->Get_Part_Count(); iPart++)
339  {
340  pSolution->Add_Part(pClip->Get_Part(iPart));
341  }
342  return( true );
343 
344  case INTERSECTION_Identical:
345  return( false );
346 
347  case INTERSECTION_Contains :
348  case INTERSECTION_Contained:
349  case INTERSECTION_Overlaps : default:
350  return( CSG_Clipper::Clip(Clipper2Lib::ClipType::Xor, pShape, pClip, pSolution) );
351  }
352 }
353 
354 //---------------------------------------------------------
355 bool SG_Shape_Get_Union (CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
356 {
357  switch( pClip->Intersects(pShape) )
358  {
359  case INTERSECTION_None :
360  if( pSolution ) { pSolution->Assign(pShape, false); } else { pSolution = pShape; }
361 
362  for(int iPart=0; iPart<pClip->Get_Part_Count(); iPart++)
363  {
364  pSolution->Add_Part(pClip->Get_Part(iPart));
365  }
366  return( true );
367 
368  case INTERSECTION_Identical:
369  case INTERSECTION_Contained:
370  return( !pSolution || pSolution->Assign(pShape, false) );
371 
372  case INTERSECTION_Contains :
373  return( !pSolution ? pShape->Assign(pClip, false) : pSolution->Assign(pClip, false) );
374 
375  case INTERSECTION_Overlaps: default:
376  return( CSG_Clipper::Clip(Clipper2Lib::ClipType::Union, pShape, pClip, pSolution) );
377  }
378 }
379 
380 //---------------------------------------------------------
389 //---------------------------------------------------------
390 bool SG_Shape_Get_Dissolve (CSG_Shape *pShape, CSG_Shape *pSolution)
391 {
392  return( CSG_Clipper::Dissolve(pShape, pSolution) );
393 }
394 
395 //---------------------------------------------------------
396 bool SG_Shape_Get_Offset (CSG_Shape *pShape, double Size, double dArc, CSG_Shape *pSolution)
397 {
398  return( CSG_Clipper::Offset(pShape, Size, dArc, pSolution) );
399 }
400 
401 
403 // //
405 
406 //---------------------------------------------------------
407 const char * SG_Clipper_Get_Version (void)
408 {
409  static CSG_String Version(CSG_String("Clipper2 ") + CLIPPER2_VERSION);
410 
411  return( Version );
412 }
413 
414 
416 // //
417 // //
418 // //
420 
421 //---------------------------------------------------------
CSG_Shapes::Get_Shape
virtual CSG_Shape * Get_Shape(const CSG_Point &Point, double Epsilon=0.)
Definition: shapes.cpp:499
CSG_Shape_Polygon::is_Clockwise
bool is_Clockwise(int iPart)
Definition: shape_polygon.cpp:871
CSG_Shape::Del_Parts
virtual int Del_Parts(void)
Definition: shapes.h:171
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:390
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:168
SSG_Point
Definition: geo_tools.h:128
CSG_Shape::Get_Type
TSG_Shape_Type Get_Type(void) const
Definition: shape.cpp:88
SG_Shape_Get_Offset
bool SG_Shape_Get_Offset(CSG_Shape *pShape, double Size, double dArc, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:396
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:418
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:824
SG_Shape_Get_Union
bool SG_Shape_Get_Union(CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:355
INTERSECTION_None
@ INTERSECTION_None
Definition: geo_tools.h:102
sLong
signed long long sLong
Definition: api_core.h:158
SG_Clipper_Get_Version
const char * SG_Clipper_Get_Version(void)
Definition: shapes_clipper.cpp:407
CSG_Table::Get_Count
sLong Get_Count(void) const
Definition: table.h:392
SG_Shape_Get_ExclusiveOr
bool SG_Shape_Get_ExclusiveOr(CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:331
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
CSG_Shape::is_Valid
virtual bool is_Valid(void) const =0
SG_Shape_Get_Difference
bool SG_Shape_Get_Difference(CSG_Shape *pShape, CSG_Shape_Polygon *pClip, CSG_Shape *pSolution)
Definition: shapes_clipper.cpp:313
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:501
SSG_Point::x
double x
Definition: geo_tools.h:129
SSG_Point::y
double y
Definition: geo_tools.h:129
CSG_Shape_Polygon::is_Lake
bool is_Lake(int iPart)
Definition: shape_polygon.cpp:811
CSG_Shapes
Definition: shapes.h:775
CSG_Shape::asPolygon
class CSG_Shape_Polygon * asPolygon(void) const
Definition: shapes.h:161
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:498
CSG_Shape_Polygon
Definition: shapes.h:701
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:293