SAGA API  v9.5
shapes_polygons.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_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 // //
50 
51 //---------------------------------------------------------
52 #include "shapes.h"
53 
54 #include "clipper1/clipper.hpp"
55 
56 
58 // //
59 // //
60 // //
62 
63 //---------------------------------------------------------
64 class CSG_Converter_WorldToInt
65 {
66 public:
67 
68  CSG_Converter_WorldToInt (void) { Create(0.0, 1.0, 0.0, 1.0); }
69  CSG_Converter_WorldToInt (const CSG_Converter_WorldToInt &Converter) { Create(Converter); }
70  CSG_Converter_WorldToInt (double xOffset, double xScale, double yOffset, double yScale) { Create(xOffset, xScale, yOffset, yScale); }
71  CSG_Converter_WorldToInt (const CSG_Rect &Extent, bool bAspectRatio = false) { Create(Extent, bAspectRatio); }
72 
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 
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 
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 
118  static ClipperLib::cInt Round (double Value) { return( (ClipperLib::cInt)(Value < 0.0 ? Value - 0.5 : Value + 0.5) ); }
119 
120  ClipperLib::cInt Get_X_asInt (double Value) const { return( Round((Value - m_xOffset) * m_xScale) ); }
121  ClipperLib::cInt Get_Y_asInt (double Value) const { return( Round((Value - m_yOffset) * m_yScale) ); }
122 
123  double Get_X_asWorld (ClipperLib::cInt Value) const { return( m_xOffset + Value / m_xScale ); }
124  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 
132  double Get_xScale (void) const { return( m_xScale ); }
133  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 
145 // //
147 
148 //---------------------------------------------------------
149 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 //---------------------------------------------------------
180 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 
191 // //
193 
194 //---------------------------------------------------------
195 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 //---------------------------------------------------------
232 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; 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)iPolygon
244  );
245  }
246  }
247 
248  return( pPolygon->Get_Part_Count() > 0 );
249 }
250 
251 
253 // //
255 
256 //---------------------------------------------------------
257 bool _SG_Polygon_Clip(ClipperLib::ClipType ClipType, CSG_Shape *pPolygon, CSG_Shape *pClip, CSG_Shape *pResult)
258 {
259  CSG_Rect r(pPolygon->Get_Extent()); r.Union(pClip->Get_Extent());
260 
261  CSG_Converter_WorldToInt Converter(r);
262 
263  ClipperLib::Paths Polygon, Clip, Result;
264 
265  if( Converter.Convert(pPolygon, Polygon)
266  && Converter.Convert(pClip , Clip ) )
267  {
268  ClipperLib::Clipper Clipper;
269 
270  Clipper.AddPaths(Clip, ClipperLib::ptClip, true);
271 
272  if( pPolygon->Get_Type() != SHAPE_TYPE_Line )
273  {
274  Clipper.AddPaths(Polygon, ClipperLib::ptSubject, true);
275 
276  if( !Clipper.Execute(ClipType, Result) )
277  {
278  return( false );
279  }
280  }
281  else
282  {
283  Clipper.AddPaths(Polygon, ClipperLib::ptSubject, false);
284 
285  ClipperLib::PolyTree PolyTree;
286 
287  if( !Clipper.Execute(ClipType, PolyTree) )
288  {
289  return( false );
290  }
291 
292  ClipperLib::PolyTreeToPaths(PolyTree, Result);
293  }
294 
295  return( Converter.Convert(Result, pResult ? pResult : pPolygon) );
296  }
297 
298  return( false );
299 }
300 
301 
303 // //
305 
306 //---------------------------------------------------------
307 bool SG_Shape_Get_Intersection (CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
308 {
309  switch( pClip->Intersects(pPolygon) )
310  {
311  case INTERSECTION_None:
312  return( false );
313 
314  case INTERSECTION_Identical:
315  case INTERSECTION_Contains:
316  if( pResult ) pResult->Assign(pPolygon, false);
317  return( true );
318 
319  case INTERSECTION_Contained:
320  if( pResult ) pResult ->Assign(pClip , false);
321  else pPolygon->Assign(pClip , false);
322  return( true );
323 
324  case INTERSECTION_Overlaps: default:
325  return( _SG_Polygon_Clip(ClipperLib::ctIntersection , pPolygon, pClip, pResult) );
326  }
327 }
328 
329 //---------------------------------------------------------
330 bool SG_Shape_Get_Difference (CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
331 {
332  switch( pClip->Intersects(pPolygon) )
333  {
334  case INTERSECTION_Contains:
335  case INTERSECTION_Identical:
336  return( false );
337 
338  case INTERSECTION_None:
339  if( pResult ) pResult->Assign(pPolygon, false);
340  return( true );
341 
342  case INTERSECTION_Contained:
343  case INTERSECTION_Overlaps: default:
344  return( _SG_Polygon_Clip(ClipperLib::ctDifference , pPolygon, pClip, pResult) );
345  }
346 }
347 
348 //---------------------------------------------------------
349 bool SG_Shape_Get_ExclusiveOr (CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
350 {
351  switch( pClip->Intersects(pPolygon) )
352  {
353  case INTERSECTION_Identical:
354  return( false );
355 
356  case INTERSECTION_None:
357  if( pResult ) pResult->Assign(pPolygon, false);
358  else pResult = pPolygon;
359 
360  { for(int iPart=0, jPart=pResult->Get_Part_Count(); iPart<pClip->Get_Part_Count(); iPart++, jPart++)
361  {
362  for(int iPoint=0; iPoint<pClip->Get_Point_Count(iPart); iPoint++)
363  {
364  pResult->Add_Point(pClip->Get_Point(iPoint, iPart), jPart);
365  }
366  }
367  }
368 
369  return( true );
370 
371  case INTERSECTION_Contained:
372  case INTERSECTION_Contains:
373  case INTERSECTION_Overlaps: default:
374  return( _SG_Polygon_Clip(ClipperLib::ctXor , pPolygon, pClip, pResult) );
375  }
376 }
377 
378 //---------------------------------------------------------
379 bool SG_Shape_Get_Union (CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
380 {
381  switch( pClip->Intersects(pPolygon) )
382  {
383  case INTERSECTION_Contained:
384  case INTERSECTION_Identical:
385  if( pResult ) pResult->Assign(pPolygon, false);
386  return( true );
387 
388  case INTERSECTION_Contains:
389  if( pResult ) pResult ->Assign(pClip , false);
390  else pPolygon->Assign(pClip , false);
391  return( true );
392 
393  case INTERSECTION_None:
394  if( pResult ) pResult->Assign(pPolygon, false);
395  else pResult = pPolygon;
396 
397  { for(int iPart=0, jPart=pResult->Get_Part_Count(); iPart<pClip->Get_Part_Count(); iPart++, jPart++)
398  {
399  for(int iPoint=0; iPoint<pClip->Get_Point_Count(iPart); iPoint++)
400  {
401  pResult->Add_Point(pClip->Get_Point(iPoint, iPart), jPart);
402  }
403  }
404  }
405 
406  return( true );
407 
408  case INTERSECTION_Overlaps: default:
409  return( _SG_Polygon_Clip(ClipperLib::ctUnion , pPolygon, pClip, pResult) );
410  }
411 }
412 
413 //---------------------------------------------------------
414 bool SG_Shape_Get_Dissolve (CSG_Shape *pPolygon, CSG_Shape *pResult)
415 {
416  CSG_Converter_WorldToInt Converter(pPolygon->Get_Extent());
417 
418  ClipperLib::Paths Polygon, Result;
419 
420  if( Converter.Convert(pPolygon, Polygon) )
421  {
422  ClipperLib::Clipper Clipper;
423 
424  Clipper.AddPaths(Polygon, ClipperLib::ptSubject, true);
425 
426  Clipper.Execute(ClipperLib::ctUnion, Result);
427 
428  return( Converter.Convert(Result, pResult ? pResult : pPolygon) );
429  }
430 
431  return( false );
432 }
433 
434 //---------------------------------------------------------
435 bool SG_Shape_Get_Offset (CSG_Shape *pPolygon, double dSize, double dArc, CSG_Shape *pResult)
436 {
437  CSG_Rect r(pPolygon->Get_Extent()); if( dSize > 0.0 ) r.Inflate(5.0 * dSize, false);
438 
439  CSG_Converter_WorldToInt Converter(r, true);
440 
441  ClipperLib::Paths Paths, Result;
442 
443  if( Converter.Convert(pPolygon, Paths) )
444  {
445  ClipperLib::ClipperOffset Offset(2.0, dArc * Converter.Get_xScale());
446 
447  if( pPolygon->Get_Type() == SHAPE_TYPE_Polygon )
448  {
449  Offset.AddPaths(Paths, ClipperLib::jtRound, ClipperLib::etClosedPolygon);
450  }
451  else
452  {
453  Offset.AddPaths(Paths, ClipperLib::jtRound, ClipperLib::etOpenRound);
454  }
455 
456  Offset.Execute(Result, dSize * Converter.Get_xScale());
457 
458  return( Converter.Convert(Result, pResult ? pResult : pPolygon) );
459  }
460 
461  return( false );
462 }
463 
464 
466 // //
468 
469 //---------------------------------------------------------
470 const char * SG_Clipper_Get_Version (void)
471 {
472  return( "Clipper1 " CLIPPER_VERSION );
473 }
474 
475 
477 // //
478 // //
479 // //
481 
482 //---------------------------------------------------------
CSG_Rect
Definition: geo_tools.h:471
SG_Shape_Get_ExclusiveOr
bool SG_Shape_Get_ExclusiveOr(CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
Definition: shapes_polygons.cpp:349
CSG_Shapes::Get_Shape
virtual CSG_Shape * Get_Shape(const CSG_Point &Point, double Epsilon=0.)
Definition: shapes.cpp:499
SG_Shape_Get_Union
bool SG_Shape_Get_Union(CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
Definition: shapes_polygons.cpp:379
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 *pPolygon, CSG_Shape *pResult)
Definition: shapes_polygons.cpp:414
CSG_Shape::Intersects
TSG_Intersection Intersects(CSG_Shape *pShape)
Definition: shape.cpp:118
SSG_Point
Definition: geo_tools.h:128
CSG_Shape::Get_Type
TSG_Shape_Type Get_Type(void) const
Definition: shape.cpp:88
CSG_Shape_Points::Get_Point
virtual TSG_Point Get_Point(int iPoint=0) const
Definition: shape_points.cpp:294
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
CSG_Rect::Get_XRange
double Get_XRange(void) const
Definition: geo_tools.h:507
CSG_Rect::Get_YMin
double Get_YMin(void) const
Definition: geo_tools.h:504
INTERSECTION_None
@ INTERSECTION_None
Definition: geo_tools.h:102
CSG_Table::Get_Count
sLong Get_Count(void) const
Definition: table.h:392
SG_Shape_Get_Intersection
bool SG_Shape_Get_Intersection(CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
Definition: shapes_polygons.cpp:307
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_Rect::Union
CSG_Rect & Union(double x, double y)
Definition: geo_classes.cpp:824
SG_Shape_Get_Difference
bool SG_Shape_Get_Difference(CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
Definition: shapes_polygons.cpp:330
SHAPE_TYPE_Line
@ SHAPE_TYPE_Line
Definition: shapes.h:104
CSG_Shape::Get_Point_Count
virtual int Get_Point_Count(void) const =0
SG_Shape_Get_Offset
bool SG_Shape_Get_Offset(CSG_Shape *pPolygon, double dSize, double dArc, CSG_Shape *pResult)
Definition: shapes_polygons.cpp:435
shapes.h
SSG_Point::x
double x
Definition: geo_tools.h:129
CSG_Rect::Get_XMin
double Get_XMin(void) const
Definition: geo_tools.h:502
CSG_Rect::Inflate
CSG_Rect & Inflate(double d, bool bPercent=true)
Definition: geo_classes.cpp:808
SSG_Point::y
double y
Definition: geo_tools.h:129
CSG_Shape::Get_Extent
virtual const CSG_Rect & Get_Extent(void)=0
CSG_Shape_Points::Get_Point_Count
virtual int Get_Point_Count(void) const
Definition: shapes.h:496
CSG_Shapes
Definition: shapes.h:775
INTERSECTION_Contained
@ INTERSECTION_Contained
Definition: geo_tools.h:105
CSG_Shape_Polygon
Definition: shapes.h:701
INTERSECTION_Overlaps
@ INTERSECTION_Overlaps
Definition: geo_tools.h:104
CSG_Shape
Definition: shapes.h:141
_SG_Polygon_Clip
bool _SG_Polygon_Clip(ClipperLib::ClipType ClipType, CSG_Shape *pPolygon, CSG_Shape *pClip, CSG_Shape *pResult)
Definition: shapes_polygons.cpp:257
CSG_Rect::Get_YRange
double Get_YRange(void) const
Definition: geo_tools.h:508
SG_Clipper_Get_Version
const char * SG_Clipper_Get_Version(void)
Definition: shapes_polygons.cpp:470