SAGA API v9.10
Loading...
Searching...
No Matches
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//---------------------------------------------------------
64class CSG_Converter_WorldToInt
65{
66public:
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
136private:
137
138 double m_xOffset, m_xScale, m_yOffset, m_yScale;
139
140
141};
142
143
145// //
147
148//---------------------------------------------------------
149bool 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//---------------------------------------------------------
180bool 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//---------------------------------------------------------
195bool 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//---------------------------------------------------------
232bool 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//---------------------------------------------------------
257bool _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//---------------------------------------------------------
307bool 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//---------------------------------------------------------
330bool 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//---------------------------------------------------------
349bool 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//---------------------------------------------------------
379bool 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//---------------------------------------------------------
414bool 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//---------------------------------------------------------
435bool 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//---------------------------------------------------------
470const 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:474
CSG_Rect::Get_YRange
double Get_YRange(void) const
Definition geo_tools.h:511
CSG_Rect::Union
CSG_Rect & Union(double x, double y)
Definition geo_classes.cpp:824
CSG_Rect::Inflate
CSG_Rect & Inflate(double d, bool bPercent=true)
Definition geo_classes.cpp:808
CSG_Rect::Get_XRange
double Get_XRange(void) const
Definition geo_tools.h:510
CSG_Rect::Get_XMin
double Get_XMin(void) const
Definition geo_tools.h:505
CSG_Rect::Get_YMin
double Get_YMin(void) const
Definition geo_tools.h:507
CSG_Shape_Points::Get_Point
virtual TSG_Point Get_Point(int iPoint=0) const
Definition shape_points.cpp:294
CSG_Shape_Points::Get_Point_Count
virtual int Get_Point_Count(void) const
Definition shapes.h:493
CSG_Shape_Polygon
Definition shapes.h:698
CSG_Shape
Definition shapes.h:141
CSG_Shape::Get_Point_Count
virtual int Get_Point_Count(void) const =0
CSG_Shape::Intersects
TSG_Intersection Intersects(CSG_Shape *pShape)
Definition shape.cpp:118
CSG_Shape::Get_Type
TSG_Shape_Type Get_Type(void) const
Definition shape.cpp:88
CSG_Shape::Add_Point
virtual int Add_Point(double x, double y, int iPart=0)=0
CSG_Shape::Get_Part_Count
virtual int Get_Part_Count(void) const =0
CSG_Shape::Del_Parts
virtual int Del_Parts(void)
Definition shapes.h:168
CSG_Shape::Assign
virtual bool Assign(CSG_Table_Record *pRecord)
Definition shape.cpp:195
CSG_Shape::Get_Extent
virtual const CSG_Rect & Get_Extent(void)=0
CSG_Shapes
Definition shapes.h:772
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_Shapes::Del_Shapes
virtual bool Del_Shapes(void)
Definition shapes.h:821
CSG_Shapes::Get_Shape
virtual CSG_Shape * Get_Shape(const CSG_Point &Point, double Epsilon=0.)
Definition shapes.cpp:483
CSG_Table::Get_Count
sLong Get_Count(void) const
Definition table.h:400
TSG_Point
struct SSG_Point TSG_Point
INTERSECTION_Overlaps
@ INTERSECTION_Overlaps
Definition geo_tools.h:104
INTERSECTION_None
@ INTERSECTION_None
Definition geo_tools.h:102
INTERSECTION_Contains
@ INTERSECTION_Contains
Definition geo_tools.h:106
INTERSECTION_Identical
@ INTERSECTION_Identical
Definition geo_tools.h:103
INTERSECTION_Contained
@ INTERSECTION_Contained
Definition geo_tools.h:105
SHAPE_TYPE_Polygon
@ SHAPE_TYPE_Polygon
Definition shapes.h:105
SHAPE_TYPE_Line
@ SHAPE_TYPE_Line
Definition shapes.h:104
SG_Shape_Get_Dissolve
bool SG_Shape_Get_Dissolve(CSG_Shape *pPolygon, CSG_Shape *pResult)
Definition shapes_polygons.cpp:414
SG_Shape_Get_ExclusiveOr
bool SG_Shape_Get_ExclusiveOr(CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
Definition shapes_polygons.cpp:349
SG_Shape_Get_Union
bool SG_Shape_Get_Union(CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
Definition shapes_polygons.cpp:379
SG_Clipper_Get_Version
const char * SG_Clipper_Get_Version(void)
Definition shapes_polygons.cpp:470
SG_Shape_Get_Difference
bool SG_Shape_Get_Difference(CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
Definition shapes_polygons.cpp:330
_SG_Polygon_Clip
bool _SG_Polygon_Clip(ClipperLib::ClipType ClipType, CSG_Shape *pPolygon, CSG_Shape *pClip, CSG_Shape *pResult)
Definition shapes_polygons.cpp:257
SG_Shape_Get_Intersection
bool SG_Shape_Get_Intersection(CSG_Shape *pPolygon, CSG_Shape_Polygon *pClip, CSG_Shape *pResult)
Definition shapes_polygons.cpp:307
SG_Shape_Get_Offset
bool SG_Shape_Get_Offset(CSG_Shape *pPolygon, double dSize, double dArc, CSG_Shape *pResult)
Definition shapes_polygons.cpp:435
SSG_Point::x
double x
Definition geo_tools.h:129
SSG_Point::y
double y
Definition geo_tools.h:129