SAGA API  v9.8
shape_polygon.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 // shape_polygon.cpp //
15 // //
16 // Copyright (C) 2005 by Olaf Conrad //
17 // //
18 //-------------------------------------------------------//
19 // //
20 // This file is part of 'SAGA - System for Automated //
21 // Geoscientific Analyses'. //
22 // //
23 // This library is free software; you can redistribute //
24 // it and/or modify it under the terms of the GNU Lesser //
25 // General Public License as published by the Free //
26 // Software Foundation, either version 2.1 of the //
27 // License, or (at your option) any later version. //
28 // //
29 // This library is distributed in the hope that it will //
30 // be useful, but WITHOUT ANY WARRANTY; without even the //
31 // implied warranty of MERCHANTABILITY or FITNESS FOR A //
32 // PARTICULAR PURPOSE. See the GNU Lesser General Public //
33 // License for more details. //
34 // //
35 // You should have received a copy of the GNU Lesser //
36 // General Public License along with this program; if //
37 // not, see <http://www.gnu.org/licenses/>. //
38 // //
39 //-------------------------------------------------------//
40 // //
41 // contact: Olaf Conrad //
42 // Institute of Geography //
43 // University of Goettingen //
44 // Goldschmidtstr. 5 //
45 // 37077 Goettingen //
46 // Germany //
47 // //
48 // e-mail: oconrad@saga-gis.org //
49 // //
51 
52 //---------------------------------------------------------
53 #include "shapes.h"
54 
55 
57 // //
58 // //
59 // //
61 
62 //---------------------------------------------------------
63 #define BOOL3_NOTSET -1
64 #define BOOL3_FALSE 0
65 #define BOOL3_TRUE 1
66 
67 
69 // //
70 // //
71 // //
73 
74 //---------------------------------------------------------
75 CSG_Shape_Polygon_Part::CSG_Shape_Polygon_Part(CSG_Shape_Points *pOwner)
76  : CSG_Shape_Part(pOwner)
77 {
78  m_bLake = BOOL3_NOTSET;
79  m_bClockwise = BOOL3_NOTSET;
80 }
81 
82 //---------------------------------------------------------
83 CSG_Shape_Polygon_Part::~CSG_Shape_Polygon_Part(void)
84 {}
85 
86 
88 // //
90 
91 //---------------------------------------------------------
92 void CSG_Shape_Polygon_Part::_Invalidate(void)
93 {
94  CSG_Shape_Part::_Invalidate();
95 
96  m_bLake = BOOL3_NOTSET;
97  m_bClockwise = BOOL3_NOTSET;
98 }
99 
100 //---------------------------------------------------------
101 void CSG_Shape_Polygon_Part::_Update_Area(void)
102 {
103  if( m_nPoints > 2 && m_bClockwise == BOOL3_NOTSET )
104  {
105  TSG_Point *pPoint, A, B;
106 
107  m_Area = 0.0;
108  m_Perimeter = 0.0;
109 
110  m_Centroid.x = 0.0;
111  m_Centroid.y = 0.0;
112 
113  pPoint = m_Points + m_nPoints - 1;
114  B.x = pPoint->x - Get_Extent().Get_XCenter();
115  B.y = pPoint->y - Get_Extent().Get_YCenter();
116  pPoint = m_Points;
117 
118  for(int iPoint=0; iPoint<m_nPoints; iPoint++, pPoint++, B=A)
119  {
120  A.x = pPoint->x - Get_Extent().Get_XCenter();
121  A.y = pPoint->y - Get_Extent().Get_YCenter();
122 
123  double d = B.x * A.y - A.x * B.y;
124 
125  m_Centroid.x += d * (A.x + B.x);
126  m_Centroid.y += d * (A.y + B.y);
127 
128  m_Area += d;
129 
130  m_Perimeter += SG_Get_Distance(A, B);
131  }
132 
133  if( m_Area != 0.0 )
134  {
135  m_Centroid.x /= (3.0 * m_Area); m_Centroid.x += Get_Extent().Get_XCenter();
136  m_Centroid.y /= (3.0 * m_Area); m_Centroid.y += Get_Extent().Get_YCenter();
137  }
138 
139  m_bClockwise = m_Area < 0.0 ? BOOL3_TRUE : BOOL3_FALSE;
140 
141  m_Area = fabs(m_Area) / 2.0;
142  }
143 }
144 
145 
147 // //
149 
150 //---------------------------------------------------------
151 TSG_Polygon_Point_Relation CSG_Shape_Polygon_Part::Get_Point_Relation(const CSG_Point &p)
152 {
153  return( Get_Point_Relation(p.x, p.y) );
154 }
155 
156 //---------------------------------------------------------
157 TSG_Polygon_Point_Relation CSG_Shape_Polygon_Part::Get_Point_Relation(double x, double y)
158 {
159  if( m_nPoints > 2 && Get_Extent().Contains(x, y) )
160  {
161  TSG_Point *pB = m_Points + m_nPoints - 1;
162 
163  if( x == pB->x && y == pB->y ) // check identity
164  {
165  return( SG_POLYGON_POINT_Vertex );
166  }
167 
168  TSG_Point *pA = m_Points; bool bInterior = false;
169 
170  for(int iPoint=0; iPoint<m_nPoints; iPoint++, pB=pA++)
171  {
172  if( pA->x == pB->x && pA->y == pB->y ) // ignore duplicates
173  {
174  continue;
175  }
176 
177  if( x == pA->x && y == pA->y ) // check identity (previous vertex has already been checked)
178  {
179  return( SG_POLYGON_POINT_Vertex );
180  }
181 
182  if( pA->y == pB->y && y == pA->y && SG_IS_BETWEEN(pA->x, x, pB->x) )
183  {
184  return( SG_POLYGON_POINT_Edge );
185  }
186 
187  if( SG_IS_BETWEEN(pA->y, y, pB->y) )
188  {
189  if( (y == pA->y && pB->y >= pA->y) || (y == pB->y && pA->y >= pB->y) ) // filter out "ray pass vertex" problem by treating the line a little lower
190  {
191  continue;
192  }
193 
194  double c = (pB->x - x) * (pA->y - y) - (pA->x - x) * (pB->y - y); // cross product PA X PB, P(x, y) is on left side of AB if c > 0.
195 
196  if( c == 0. )
197  {
198  return( SG_POLYGON_POINT_Edge );
199  }
200 
201  if( (pB->y < pA->y) == (c > 0.) )
202  {
203  bInterior = !bInterior;
204  }
205  }
206  }
207 
208  if( bInterior )
209  {
210  return( SG_POLYGON_POINT_Interior );
211  }
212  }
213 
214  return( SG_POLYGON_POINT_Outside );
215 }
216 
217 
219 // //
221 
222 //---------------------------------------------------------
223 bool CSG_Shape_Polygon_Part::is_OnEdge(const CSG_Point &p)
224 {
225  return( is_OnEdge(p.x, p.y) );
226 }
227 
228 //---------------------------------------------------------
229 bool CSG_Shape_Polygon_Part::is_OnEdge(double x, double y)
230 {
231  TSG_Polygon_Point_Relation r = Get_Point_Relation(x, y);
232 
233  return( r == SG_POLYGON_POINT_Vertex
234  || r == SG_POLYGON_POINT_Edge
235  );
236 }
237 
238 
240 // //
242 
243 //---------------------------------------------------------
244 bool CSG_Shape_Polygon_Part::Contains(const CSG_Point &p)
245 {
246  return( Contains(p.x, p.y) );
247 }
248 
249 //---------------------------------------------------------
250 bool CSG_Shape_Polygon_Part::Contains(double x, double y)
251 {
252  TSG_Polygon_Point_Relation r = Get_Point_Relation(x, y);
253 
254  return( r == SG_POLYGON_POINT_Interior
255  || r == SG_POLYGON_POINT_Vertex
256  || r == SG_POLYGON_POINT_Edge
257  );
258 
259  //-----------------------------------------------------
260  if( m_nPoints > 2 && Get_Extent().Contains(x, y) )
261  {
262  int nCrossings = 0;
263 
264  TSG_Point *pA = m_Points;
265  TSG_Point *pB = m_Points + m_nPoints - 1;
266 
267  for(int iPoint=0; iPoint<m_nPoints; iPoint++, pB=pA++)
268  {
269  if( y <= pA->y ) // pA on or above ray
270  {
271  if( pB->y <= y ) // pB on or below ray
272  {
273  if( ((y - pB->y) * (pA->x - pB->x)) >= ((x - pB->x) * (pA->y - pB->y)) )
274  {
275  nCrossings++;
276  }
277  }
278  }
279  else // pA below ray
280  {
281  if( pB->y >= y ) // pB above ray
282  {
283  if( ((y - pB->y) * (pA->x - pB->x)) <= ((x - pB->x) * (pA->y - pB->y)) )
284  {
285  nCrossings++;
286  }
287  }
288  }
289  }
290 
291  return( nCrossings % 2 != 0 );
292  }
293 
294  return( false );
295 }
296 
297 
299 // //
301 
302 //---------------------------------------------------------
311 //---------------------------------------------------------
312 bool CSG_Shape_Polygon_Part::is_Neighbour(CSG_Shape_Polygon_Part *pPart, bool bSimpleCheck)
313 {
314  if( !Get_Extent().Intersects(pPart->Get_Extent()) )
315  {
316  return( false );
317  }
318 
319  bool bNeighbour = false;
320 
321  //---------------------------------------------------------
322  for(int iPoint=0; iPoint<pPart->Get_Count(); iPoint++)
323  {
324  switch( Get_Point_Relation(pPart->Get_Point(iPoint)) )
325  {
326  case SG_POLYGON_POINT_Outside : break;
327  case SG_POLYGON_POINT_Interior: return( false );
328  case SG_POLYGON_POINT_Vertex :
329  case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
330  bNeighbour = true;
331  break;
332  }
333  }
334 
335  //---------------------------------------------------------
336  for(int iPoint=0; iPoint<Get_Count(); iPoint++)
337  {
338  switch( pPart->Get_Point_Relation(Get_Point(iPoint)) )
339  {
340  case SG_POLYGON_POINT_Outside : break;
341  case SG_POLYGON_POINT_Interior: return( false );
342  case SG_POLYGON_POINT_Vertex :
343  case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
344  bNeighbour = true;
345  break;
346  }
347  }
348 
349  return( bNeighbour );
350 }
351 
352 
354 // //
356 
357 //---------------------------------------------------------
358 void CSG_Shape_Polygon_Part::_Add_Edge_Points(CSG_Shape_Polygon_Part *pPart, const CSG_Point &P0, const CSG_Point &P1, CSG_Points &Part, double Epsilon)
359 {
360  CSG_Points Points;
361 
362  for(int i=0; i<pPart->Get_Count(); i++)
363  {
364  CSG_Point P = pPart->Get_Point(i);
365 
366  if( P != P0 && P != P1 && SG_Is_Point_On_Line(P, P0, P1, true, Epsilon) )
367  {
368  Points.Add(P);
369  }
370  }
371 
372  if( Points.Get_Count() == 1 )
373  {
374  Part.Add(Points[0]);
375  }
376  else if( Points.Get_Count() > 1 )
377  {
378  double *Distances = new double[Points.Get_Count()];
379 
380  for(sLong i=0; i<Points.Get_Count(); i++)
381  {
382  Distances[i] = SG_Get_Distance(P0, Points[i]);
383  }
384 
385  CSG_Index Index(Points.Get_Count(), Distances); delete[](Distances);
386 
387  for(sLong i=0; i<Points.Get_Count(); i++)
388  {
389  Part.Add(Points[Index[i]]);
390  }
391  }
392 }
393 
394 //---------------------------------------------------------
395 bool CSG_Shape_Polygon_Part::_is_OnEdge(CSG_Shape_Polygon_Part *pPart, const CSG_Point &P, bool bVertex, double Epsilon)
396 {
397  CSG_Point P1 = pPart->Get_Point(0, false); // close the ring, starting with last point!
398 
399  if( !bVertex && P == P1 )
400  {
401  return( false );
402  }
403 
404  for(int i=0; i<pPart->Get_Count(); i++)
405  {
406  CSG_Point P0 = P1; P1 = pPart->Get_Point(i);
407 
408  if( !bVertex && P == P1 )
409  {
410  return( false );
411  }
412 
413  if( SG_Is_Point_On_Line(P, P0, P1, true, Epsilon) )
414  {
415  return( true );
416  }
417  }
418 
419  return( false );
420 }
421 
422 //---------------------------------------------------------
433 //---------------------------------------------------------
434 CSG_Lines CSG_Shape_Polygon_Part::Get_Shared_Edges(CSG_Shape_Polygon_Part *pPart, bool bVertexCheck, double Epsilon)
435 {
436  CSG_Lines Edges;
437 
438  if( Get_Extent().Intersects(pPart->Get_Extent()) )
439  {
440  if( bVertexCheck == false )
441  {
442  bool bOnEdge = is_OnEdge(pPart->Get_Point(0, false)); // close the ring, starting with last point!
443 
444  if( bOnEdge )
445  {
446  Edges.Add().Add(pPart->Get_Point(0, false));
447  }
448 
449  for(int i=0; i<pPart->Get_Count(); i++)
450  {
451  CSG_Point Point = pPart->Get_Point(i);
452 
453  if( is_OnEdge(Point) )
454  {
455  if( !bOnEdge ) // start a new edge segment
456  {
457  Edges.Add().Add(Point);
458  }
459  else // continue edge segment
460  {
461  Edges[Edges.Get_Count() - 1].Add(Point);
462  }
463 
464  bOnEdge = true;
465  }
466  else
467  {
468  bOnEdge = false;
469  }
470  }
471  }
472  else
473  {
474  CSG_Points Part; CSG_Point P1 = Get_Point(0, false); // close the ring, starting with last point!
475 
476  if( _is_OnEdge(pPart, P1, true, Epsilon) ) { Part.Add(P1); }
477 
478  for(int i=0; i<Get_Count(); i++)
479  {
480  CSG_Point P0 = P1; P1 = Get_Point(i);
481 
482  _Add_Edge_Points(pPart, P0, P1, Part, Epsilon);
483 
484  if( _is_OnEdge(pPart, P1, true, Epsilon) ) { Part.Add(P1); }
485  }
486 
487  //---------------------------------------------
488  if( Part.Get_Count() > 1 )
489  {
490  P1 = Part[0]; bool bOnEdge = false;
491  CSG_Point C0 = P1;
492 
493  for(sLong i=1, n=-1; i<Part.Get_Count(); i++)
494  {
495  CSG_Point C1, P0 = P1; P1 = Part[i];
496 
497  C1.x = P0.x + 0.5 * (P1.x - P0.x);
498  C1.y = P0.y + 0.5 * (P1.y - P0.y);
499 
500  if( C0 == C1 )
501  {
502  continue; // do not add the same edge twice (in different directions)
503  }
504 
505  if( _is_OnEdge(this, C1, true, Epsilon) && _is_OnEdge(pPart, C1, true, Epsilon) )
506  {
507  if( !bOnEdge ) // start a new edge segment
508  {
509  n = Edges.Get_Count(); Edges.Add();
510  Edges[n].Add(P0);
511  Edges[n].Add(P1);
512  }
513  else // continue edge segment
514  {
515  Edges[n].Add(P1);
516  }
517 
518  bOnEdge = true;
519  }
520  else
521  {
522  bOnEdge = false;
523  }
524 
525  C0 = C1;
526  }
527  }
528  }
529  }
530 
531  return( Edges );
532 }
533 
534 //---------------------------------------------------------
540 //---------------------------------------------------------
541 double CSG_Shape_Polygon_Part::Get_Shared_Length(CSG_Shape_Polygon_Part *pPart, bool bVertexCheck, double Epsilon)
542 {
543  CSG_Lines Edges(Get_Shared_Edges(pPart, bVertexCheck, Epsilon));
544 
545  return( Edges.Get_Length() );
546 }
547 
548 
550 // //
552 
553 //---------------------------------------------------------
554 double CSG_Shape_Polygon_Part::Get_Distance(TSG_Point Point, TSG_Point &Next)
555 {
556  if( m_nPoints < 1 )
557  {
558  return( -1.0 );
559  }
560 
561  if( Contains(Point) )
562  {
563  return( 0.0 );
564  }
565 
566  TSG_Point *pB = m_Points + m_nPoints - 1;
567  TSG_Point *pA = m_Points, C;
568 
569  double Distance = SG_Get_Nearest_Point_On_Line(Point, *pA, *pB, Next);
570 
571  for(int iPoint=0; iPoint<m_nPoints && Distance>0.0; iPoint++, pB=pA++)
572  {
573  double d = SG_Get_Nearest_Point_On_Line(Point, *pA, *pB, C);
574 
575  if( d >= 0.0 && d < Distance )
576  {
577  Distance = d;
578  Next = C;
579  }
580  }
581 
582  return( Distance );
583 }
584 
585 
587 // //
588 // //
589 // //
591 
592 //---------------------------------------------------------
593 CSG_Shape_Polygon::CSG_Shape_Polygon(CSG_Shapes *pOwner, sLong Index)
594  : CSG_Shape_Points(pOwner, Index)
595 {
596  m_bUpdate_Lakes = true;
597 }
598 
599 //---------------------------------------------------------
600 CSG_Shape_Polygon::~CSG_Shape_Polygon(void)
601 {}
602 
603 
605 // //
607 
608 //---------------------------------------------------------
609 void CSG_Shape_Polygon::_Invalidate(void)
610 {
611  CSG_Shape_Points::_Invalidate();
612 
613  if( m_bUpdate_Lakes )
614  {
615  m_bUpdate_Lakes = false;
616 
617  for(int i=0; i<m_nParts; i++)
618  {
619  Get_Polygon_Part(i)->m_bLake = BOOL3_NOTSET;
620  }
621  }
622 }
623 
624 
626 // //
628 
629 //---------------------------------------------------------
630 TSG_Intersection CSG_Shape_Polygon::On_Intersects(CSG_Shape *pShape)
631 {
632  //-----------------------------------------------------
633  bool bIn = false;
634  bool bOut = false;
635 
636  for(int iPart=0; iPart<pShape->Get_Part_Count(); iPart++)
637  {
638  for(int iPoint=0; iPoint<pShape->Get_Point_Count(iPart); iPoint++)
639  {
640  if( Contains(pShape->Get_Point(iPoint, iPart)) )
641  {
642  bIn = true;
643  }
644  else
645  {
646  bOut = true;
647  }
648 
649  if( bIn && bOut ) // some vertices are in, some are out
650  {
651  return( INTERSECTION_Overlaps );
652  }
653  }
654  }
655 
656  //-----------------------------------------------------
657  if( pShape->Get_Type() == SHAPE_TYPE_Point || pShape->Get_Type() == SHAPE_TYPE_Points )
658  {
659  return( bIn ? INTERSECTION_Contains : INTERSECTION_None ); // there are no other options for points
660  }
661 
662  //-----------------------------------------------------
663  for(int iPart=0; iPart<Get_Part_Count(); iPart++)
664  {
665  if( Get_Point_Count(iPart) < 3 )
666  {
667  continue;
668  }
669 
670  TSG_Point A[2], B[2], C; A[0] = Get_Point(0, iPart, false);
671 
672  for(int iPoint=0; iPoint<Get_Point_Count(iPart); iPoint++)
673  {
674  A[1] = A[0]; A[0] = Get_Point(iPoint, iPart);
675 
676  for(int jPart=0; jPart<pShape->Get_Part_Count(); jPart++)
677  {
678  //-----------------------------------------
679  if( pShape->Get_Type() == SHAPE_TYPE_Line && pShape->Get_Point_Count(jPart) >= 2 )
680  {
681  B[0] = pShape->Get_Point(0, jPart);
682 
683  for(int jPoint=1; jPoint<pShape->Get_Point_Count(jPart); jPoint++)
684  {
685  B[1] = B[0]; B[0] = pShape->Get_Point(jPoint, jPart);
686 
687  if( SG_Get_Crossing(C, A[0], A[1], B[0], B[1]) )
688  {
689  return( INTERSECTION_Overlaps );
690  }
691  }
692  }
693 
694  //-----------------------------------------
695  if( pShape->Get_Type() == SHAPE_TYPE_Polygon && pShape->Get_Point_Count(jPart) >= 3 )
696  {
697  B[0] = pShape->Get_Point(0, jPart, false);
698 
699  for(int jPoint=0; jPoint<pShape->Get_Point_Count(jPart); jPoint++)
700  {
701  B[1] = B[0]; B[0] = pShape->Get_Point(jPoint, jPart);
702 
703  if( SG_Get_Crossing(C, A[0], A[1], B[0], B[1]) )
704  {
705  return( INTERSECTION_Overlaps );
706  }
707  }
708  }
709  }
710  }
711  }
712 
713  //-----------------------------------------------------
714  return( bIn ? INTERSECTION_Contains : INTERSECTION_None );
715 }
716 
717 //---------------------------------------------------------
718 TSG_Intersection CSG_Shape_Polygon::On_Intersects(TSG_Rect Region)
719 {
720  // called if polygon's bounding box contains or overlaps with region.
721  // now let's figure out how region intersects with polygon itself
722 
723  //-----------------------------------------------------
724  for(int iPart=0; iPart<m_nParts; iPart++)
725  {
726  CSG_Shape_Part *pPart = m_pParts[iPart];
727 
728  switch( pPart->Get_Extent().Intersects(Region) )
729  {
730  case INTERSECTION_None: // region and polygon part are distinct
731  break;
732 
733  case INTERSECTION_Identical: // region contains polygon part
734  case INTERSECTION_Contained:
735  return( Get_Extent().Intersects(Region) );
736 
737  case INTERSECTION_Contains:
738  case INTERSECTION_Overlaps: // region at least partly contained by polygon part's extent, now let's look at the polygon part itself!
739  if( pPart->Get_Count() > 2 )
740  {
741  TSG_Point *pB = pPart->m_Points + pPart->m_nPoints - 1;
742  TSG_Point *pA = pPart->m_Points, C;
743 
744  for(int iPoint=0; iPoint<pPart->m_nPoints; iPoint++, pB=pA++)
745  {
746  if( SG_Get_Crossing_InRegion(C, *pA, *pB, Region) )
747  {
748  return( INTERSECTION_Overlaps );
749  }
750  }
751  }
752  break;
753  }
754  }
755 
756  //-----------------------------------------------------
757  return( Contains(Region.xMin, Region.yMin) ? INTERSECTION_Contains : INTERSECTION_None );
758 }
759 
760 
762 // //
764 
765 //---------------------------------------------------------
766 bool CSG_Shape_Polygon::is_Lake(int iPart)
767 {
768  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
769 
770  if( !pPart )
771  {
772  return( false );
773  }
774 
775  if( pPart->m_bLake == BOOL3_NOTSET )
776  {
777  if( pPart->m_nPoints < 1 || m_nParts <= 1 )
778  {
779  pPart->m_bLake = BOOL3_FALSE;
780  }
781  else
782  {
783  m_bUpdate_Lakes = true;
784 
785  pPart->m_bLake = BOOL3_FALSE;
786 
787  for(int iPoint=0; iPoint<pPart->m_nPoints; iPoint++) // find a point that is not on vertex/edge
788  {
789  TSG_Point p = pPart->Get_Point(iPoint);
790  bool bEdge = false;
791  int nContained = 0;
792 
793  for(iPart=0; !bEdge && iPart<m_nParts; iPart++)
794  {
795  if( pPart != m_pParts[iPart] )
796  {
797  switch( Get_Polygon_Part(iPart)->Get_Point_Relation(p) )
798  {
799  case SG_POLYGON_POINT_Outside : break;
800  case SG_POLYGON_POINT_Interior: nContained++; break;
801  case SG_POLYGON_POINT_Vertex :
802  case SG_POLYGON_POINT_Edge : bEdge = true; break;
803  }
804  }
805  }
806 
807  if( !bEdge )
808  {
809  pPart->m_bLake = nContained % 2 ? BOOL3_TRUE : BOOL3_FALSE;
810 
811  break;
812  }
813  }
814  }
815  }
816 
817  return( pPart->m_bLake == BOOL3_TRUE );
818 }
819 
820 
822 // //
824 
825 //---------------------------------------------------------
826 bool CSG_Shape_Polygon::is_Clockwise(int iPart)
827 {
828  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
829 
830  return( pPart && pPart->is_Clockwise() );
831 }
832 
833 //---------------------------------------------------------
834 double CSG_Shape_Polygon::Get_Perimeter(int iPart)
835 {
836  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
837 
838  return( pPart ? pPart->Get_Perimeter() : 0.0 );
839 }
840 
841 //---------------------------------------------------------
842 double CSG_Shape_Polygon::Get_Perimeter(void)
843 {
844  double Perimeter = 0.0;
845 
846  for(int iPart=0; iPart<m_nParts; iPart++)
847  {
848  Perimeter += Get_Perimeter(iPart);
849  }
850 
851  return( Perimeter );
852 }
853 
854 //---------------------------------------------------------
855 double CSG_Shape_Polygon::Get_Area(int iPart)
856 {
857  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
858 
859  return( pPart ? pPart->Get_Area() : 0.0 );
860 }
861 
862 //---------------------------------------------------------
863 double CSG_Shape_Polygon::Get_Area(void)
864 {
865  double Area = 0.0;
866 
867  for(int iPart=0; iPart<m_nParts; iPart++)
868  {
869  Area += is_Lake(iPart) ? -Get_Area(iPart) : Get_Area(iPart);
870  }
871 
872  return( Area );
873 }
874 
875 //---------------------------------------------------------
876 TSG_Point CSG_Shape_Polygon::Get_Centroid(int iPart)
877 {
878  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
879 
880  if( pPart )
881  {
882  return( pPart->Get_Centroid() );
883  }
884 
885  return( CSG_Point(0.0, 0.0) );
886 }
887 
888 //---------------------------------------------------------
889 TSG_Point CSG_Shape_Polygon::Get_Centroid(void)
890 {
891  if( m_nParts == 1 )
892  {
893  return( Get_Centroid(0) );
894  }
895 
896  int iPart;
897  double Weights;
898  TSG_Point Centroid;
899 
900  Centroid.x = 0.0;
901  Centroid.y = 0.0;
902 
903  for(iPart=0, Weights=0.0; iPart<m_nParts; iPart++)
904  {
905  if( !is_Lake(iPart) )
906  {
907  TSG_Point p = Get_Centroid(iPart);
908  double w = Get_Area (iPart);
909 
910  Centroid.x += w * p.x;
911  Centroid.y += w * p.y;
912 
913  Weights += w;
914  }
915  }
916 
917  if( Weights > 0.0 )
918  {
919  Centroid.x /= Weights;
920  Centroid.y /= Weights;
921  }
922 
923  return( Centroid );
924 }
925 
926 
928 // //
930 
931 //---------------------------------------------------------
932 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(const CSG_Point &p, int iPart)
933 {
934  return( Get_Point_Relation(p.x, p.y, iPart) );
935 }
936 
937 //---------------------------------------------------------
938 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(double x, double y, int iPart)
939 {
940  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
941 
942  return( pPart ? pPart->Get_Point_Relation(x, y) : SG_POLYGON_POINT_Outside );
943 }
944 
945 //---------------------------------------------------------
946 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(const CSG_Point &p)
947 {
948  return( Get_Point_Relation(p.x, p.y) );
949 }
950 
951 //---------------------------------------------------------
952 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(double x, double y)
953 {
954  if( Get_Extent().Contains(x, y) )
955  {
956  int nContained = 0;
957 
958  for(int iPart=0; iPart<m_nParts; iPart++)
959  {
960  switch( Get_Polygon_Part(iPart)->Get_Point_Relation(x, y) )
961  {
962  case SG_POLYGON_POINT_Outside : break;
963  case SG_POLYGON_POINT_Interior: nContained++; break;
964  case SG_POLYGON_POINT_Vertex : return( SG_POLYGON_POINT_Vertex );
965  case SG_POLYGON_POINT_Edge : return( SG_POLYGON_POINT_Edge );
966  }
967  }
968 
969  if( nContained % 2 != 0 )
970  {
971  return( SG_POLYGON_POINT_Interior );
972  }
973  }
974 
975  return( SG_POLYGON_POINT_Outside );
976 }
977 
978 
980 // //
982 
983 //---------------------------------------------------------
984 bool CSG_Shape_Polygon::is_OnEdge(const CSG_Point &p, int iPart)
985 {
986  return( is_OnEdge(p.x, p.y, iPart) );
987 }
988 
989 //---------------------------------------------------------
990 bool CSG_Shape_Polygon::is_OnEdge(double x, double y, int iPart)
991 {
992  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
993 
994  return( pPart && pPart->is_OnEdge(x, y) );
995 }
996 
997 //---------------------------------------------------------
998 bool CSG_Shape_Polygon::is_OnEdge(const CSG_Point &p)
999 {
1000  return( is_OnEdge(p.x, p.y) );
1001 }
1002 
1003 //---------------------------------------------------------
1004 bool CSG_Shape_Polygon::is_OnEdge(double x, double y)
1005 {
1006  if( Get_Extent().Contains(x, y) )
1007  {
1008  for(int iPart=0; iPart<m_nParts; iPart++)
1009  {
1010  if( Get_Polygon_Part(iPart)->is_OnEdge(x, y) )
1011  {
1012  return( true );
1013  }
1014  }
1015  }
1016 
1017  return( false );
1018 }
1019 
1020 
1022 // //
1024 
1025 //---------------------------------------------------------
1026 bool CSG_Shape_Polygon::Contains(const CSG_Point &p, int iPart)
1027 {
1028  return( Contains(p.x, p.y, iPart) );
1029 }
1030 
1031 //---------------------------------------------------------
1032 bool CSG_Shape_Polygon::Contains(double x, double y, int iPart)
1033 {
1034  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
1035 
1036  return( pPart && pPart->Contains(x, y) );
1037 }
1038 
1039 //---------------------------------------------------------
1040 bool CSG_Shape_Polygon::Contains(const CSG_Point &p)
1041 {
1042  return( Contains(p.x, p.y) );
1043 }
1044 
1045 //---------------------------------------------------------
1046 bool CSG_Shape_Polygon::Contains(double x, double y)
1047 {
1048  if( Get_Extent().Contains(x, y) )
1049  {
1050  int nContained = 0;
1051 
1052  for(int iPart=0; iPart<m_nParts; iPart++)
1053  {
1054  if( Get_Polygon_Part(iPart)->Contains(x, y) )
1055  {
1056  nContained++;
1057  }
1058  }
1059 
1060  return( nContained % 2 != 0 );
1061  }
1062 
1063  return( false );
1064 }
1065 
1066 
1068 // //
1070 
1071 //---------------------------------------------------------
1080 //---------------------------------------------------------
1081 bool CSG_Shape_Polygon::is_Neighbour(CSG_Shape_Polygon *pPolygon, bool bSimpleCheck)
1082 {
1083  if( !Get_Extent().Intersects(pPolygon->Get_Extent()) )
1084  {
1085  return( false );
1086  }
1087 
1088  bool bNeighbour = false;
1089 
1090  //---------------------------------------------------------
1091  for(int iPoint=0; iPoint<pPolygon->Get_Point_Count(); iPoint++)
1092  {
1093  switch( Get_Point_Relation(pPolygon->Get_Point(iPoint)) )
1094  {
1095  case SG_POLYGON_POINT_Outside : break;
1096  case SG_POLYGON_POINT_Interior: return( false );
1097  case SG_POLYGON_POINT_Vertex :
1098  case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
1099  bNeighbour = true;
1100  break;
1101  }
1102  }
1103 
1104  //---------------------------------------------------------
1105  for(int iPoint=0; iPoint<Get_Point_Count(); iPoint++)
1106  {
1107  switch( pPolygon->Get_Point_Relation(Get_Point(iPoint)) )
1108  {
1109  case SG_POLYGON_POINT_Outside : break;
1110  case SG_POLYGON_POINT_Interior: return( false );
1111  case SG_POLYGON_POINT_Vertex :
1112  case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
1113  bNeighbour = true;
1114  break;
1115  }
1116  }
1117 
1118  return( bNeighbour );
1119 }
1120 
1121 
1123 // //
1125 
1126 //---------------------------------------------------------
1137 //---------------------------------------------------------
1138 CSG_Lines CSG_Shape_Polygon::Get_Shared_Edges(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon)
1139 {
1140  CSG_Lines Edges;
1141 
1142  if( Get_Extent().Intersects(pPolygon->Get_Extent()) )
1143  {
1144  for(int i=0; i<Get_Part_Count(); i++)
1145  {
1146  for(int j=0; j<pPolygon->Get_Part_Count(); j++)
1147  {
1148  Edges.Add(Get_Polygon_Part(i)->Get_Shared_Edges(pPolygon->Get_Polygon_Part(j), bVertexCheck, Epsilon));
1149  }
1150  }
1151  }
1152 
1153  return( Edges );
1154 }
1155 
1156 //---------------------------------------------------------
1162 //---------------------------------------------------------
1163 double CSG_Shape_Polygon::Get_Shared_Length(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon)
1164 {
1165  CSG_Lines Edges(Get_Shared_Edges(pPolygon, bVertexCheck, Epsilon));
1166 
1167  return( Edges.Get_Length() );
1168 }
1169 
1170 
1172 // //
1174 
1175 //---------------------------------------------------------
1176 double CSG_Shape_Polygon::Get_Distance(TSG_Point Point, TSG_Point &Next, int iPart) const
1177 {
1178  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
1179 
1180  return( pPart ? pPart->Get_Distance(Point, Next) : -1. );
1181 }
1182 
1183 
1185 // //
1186 // //
1187 // //
1189 
1190 //---------------------------------------------------------
CSG_Index
Definition: mat_tools.h:200
SG_POLYGON_POINT_Edge
@ SG_POLYGON_POINT_Edge
Definition: shapes.h:638
CSG_Shape_Polygon_Part::is_Clockwise
bool is_Clockwise(void)
Definition: shapes.h:650
CSG_Shape_Polygon_Part::Get_Centroid
const TSG_Point & Get_Centroid(void)
Definition: shapes.h:656
CSG_Shape_Polygon::Get_Point_Relation
TSG_Polygon_Point_Relation Get_Point_Relation(const CSG_Point &p, int iPart)
Definition: shape_polygon.cpp:932
CSG_Shape_Points::m_pParts
CSG_Shape_Part ** m_pParts
Definition: shapes.h:567
CSG_Shape_Polygon_Part::is_Neighbour
bool is_Neighbour(CSG_Shape_Polygon_Part *pPart, bool bSimpleCheck=true)
Definition: shape_polygon.cpp:312
BOOL3_NOTSET
#define BOOL3_NOTSET
Definition: shape_polygon.cpp:63
CSG_Points::Add
bool Add(double x, double y)
Definition: geo_classes.cpp:350
SG_POLYGON_POINT_Interior
@ SG_POLYGON_POINT_Interior
Definition: shapes.h:639
CSG_Shape_Polygon::m_bUpdate_Lakes
int m_bUpdate_Lakes
Definition: shapes.h:752
TSG_Intersection
TSG_Intersection
Definition: geo_tools.h:101
CSG_Shape_Polygon_Part::Get_Distance
double Get_Distance(TSG_Point Point, TSG_Point &Next)
Definition: shape_polygon.cpp:554
SG_Get_Crossing_InRegion
bool SG_Get_Crossing_InRegion(TSG_Point &Crossing, const TSG_Point &a, const TSG_Point &b, const TSG_Rect &Region)
Definition: geo_functions.cpp:342
CSG_Shape_Polygon_Part::~CSG_Shape_Polygon_Part
virtual ~CSG_Shape_Polygon_Part(void)
Definition: shape_polygon.cpp:83
CSG_Shape_Polygon::is_Clockwise
bool is_Clockwise(int iPart)
Definition: shape_polygon.cpp:826
A
#define A
CSG_Shape_Part::Get_Point
TSG_Point Get_Point(int iPoint, bool bAscending=true) const
Definition: shapes.h:386
C
#define C
CSG_Shape_Polygon_Part
Definition: shapes.h:645
SHAPE_TYPE_Polygon
@ SHAPE_TYPE_Polygon
Definition: shapes.h:105
CSG_Shape_Polygon_Part::m_Perimeter
double m_Perimeter
Definition: shapes.h:683
CSG_Shape_Polygon_Part::Get_Point_Relation
TSG_Polygon_Point_Relation Get_Point_Relation(const CSG_Point &p)
Definition: shape_polygon.cpp:151
INTERSECTION_Contains
@ INTERSECTION_Contains
Definition: geo_tools.h:106
CSG_Rect::Intersects
TSG_Intersection Intersects(const CSG_Rect &Rect) const
Definition: geo_classes.cpp:881
CSG_Shape_Points
Definition: shapes.h:484
CSG_Shape_Polygon::Get_Shared_Edges
CSG_Lines Get_Shared_Edges(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon=0.)
Definition: shape_polygon.cpp:1138
CSG_Shape_Polygon_Part::_is_OnEdge
bool _is_OnEdge(CSG_Shape_Polygon_Part *pPart, const CSG_Point &P, bool bVertex, double Epsilon)
Definition: shape_polygon.cpp:395
CSG_Shape_Polygon::is_OnEdge
bool is_OnEdge(const CSG_Point &p, int iPart)
Definition: shape_polygon.cpp:984
CSG_Shape_Part::_Invalidate
virtual void _Invalidate(void)
Definition: shape_part.cpp:391
CSG_Shape::Intersects
TSG_Intersection Intersects(CSG_Shape *pShape)
Definition: shape.cpp:118
CSG_Shape_Polygon::Get_Shared_Length
double Get_Shared_Length(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon=0.)
Definition: shape_polygon.cpp:1163
SSG_Point
Definition: geo_tools.h:128
SG_Get_Nearest_Point_On_Line
double SG_Get_Nearest_Point_On_Line(const TSG_Point &Point, const TSG_Point &Line_A, const TSG_Point &Line_B, TSG_Point &Line_Point, bool bExactMatch)
Definition: geo_functions.cpp:421
CSG_Shape::Get_Type
TSG_Shape_Type Get_Type(void) const
Definition: shape.cpp:88
CSG_Shape_Polygon_Part::is_OnEdge
bool is_OnEdge(const CSG_Point &p)
Definition: shape_polygon.cpp:223
TSG_Polygon_Point_Relation
TSG_Polygon_Point_Relation
Definition: shapes.h:635
SSG_Rect::xMin
double xMin
Definition: geo_tools.h:468
SSG_Rect
Definition: geo_tools.h:467
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_Shape_Polygon_Part::_Add_Edge_Points
void _Add_Edge_Points(CSG_Shape_Polygon_Part *pPart, const CSG_Point &P0, const CSG_Point &P1, CSG_Points &Part, double Epsilon)
Definition: shape_polygon.cpp:358
CSG_Shape_Polygon_Part::m_bClockwise
int m_bClockwise
Definition: shapes.h:681
SG_POLYGON_POINT_Vertex
@ SG_POLYGON_POINT_Vertex
Definition: shapes.h:637
CSG_Shape::Get_Part_Count
virtual int Get_Part_Count(void) const =0
CSG_Shape_Polygon::Contains
bool Contains(const CSG_Point &p, int iPart)
Definition: shape_polygon.cpp:1026
CSG_Point
Definition: geo_tools.h:135
CSG_Points::Get_Count
sLong Get_Count(void) const
Definition: geo_tools.h:201
SG_POLYGON_POINT_Outside
@ SG_POLYGON_POINT_Outside
Definition: shapes.h:636
CSG_Shape_Polygon_Part::_Invalidate
virtual void _Invalidate(void)
Definition: shape_polygon.cpp:92
CSG_Shape_Polygon::Get_Centroid
TSG_Point Get_Centroid(void)
Definition: shape_polygon.cpp:889
CSG_Shape_Polygon_Part::CSG_Shape_Polygon_Part
CSG_Shape_Polygon_Part(class CSG_Shape_Points *pOwner)
Definition: shape_polygon.cpp:75
CSG_Shape_Part::Get_Extent
const CSG_Rect & Get_Extent(void)
Definition: shapes.h:382
INTERSECTION_None
@ INTERSECTION_None
Definition: geo_tools.h:102
CSG_Shape_Part::m_Points
TSG_Point * m_Points
Definition: shapes.h:462
CSG_Shape_Polygon_Part::m_bLake
int m_bLake
Definition: shapes.h:681
SG_Get_Distance
double SG_Get_Distance(double ax, double ay, double bx, double by, bool bPolar)
Definition: geo_functions.cpp:103
sLong
signed long long sLong
Definition: api_core.h:158
CSG_Shape_Polygon_Part::m_Centroid
TSG_Point m_Centroid
Definition: shapes.h:685
CSG_Shape_Part::m_nPoints
int m_nPoints
Definition: shapes.h:458
CSG_Shape_Polygon::Get_Perimeter
double Get_Perimeter(void)
Definition: shape_polygon.cpp:842
CSG_Shape_Polygon::_Invalidate
virtual void _Invalidate(void)
Definition: shape_polygon.cpp:609
CSG_Shape_Polygon::On_Intersects
virtual TSG_Intersection On_Intersects(CSG_Shape *pShape)
Definition: shape_polygon.cpp:630
CSG_Shape_Polygon::Get_Distance
virtual double Get_Distance(TSG_Point Point, TSG_Point &Next, int iPart) const
Definition: shape_polygon.cpp:1176
CSG_Shape_Polygon::Get_Area
double Get_Area(void)
Definition: shape_polygon.cpp:863
CSG_Shape_Polygon::Get_Polygon_Part
CSG_Shape_Polygon_Part * Get_Polygon_Part(int iPart) const
Definition: shapes.h:707
CSG_Lines::Get_Count
sLong Get_Count(void) const
Definition: geo_tools.h:240
CSG_Shape_Polygon::~CSG_Shape_Polygon
virtual ~CSG_Shape_Polygon(void)
Definition: shape_polygon.cpp:600
INTERSECTION_Identical
@ INTERSECTION_Identical
Definition: geo_tools.h:103
CSG_Shape_Polygon::CSG_Shape_Polygon
CSG_Shape_Polygon(class CSG_Shapes *pOwner, sLong Index)
Definition: shape_polygon.cpp:593
CSG_Lines::Add
CSG_Points & Add(void)
Definition: geo_classes.cpp:437
BOOL3_TRUE
#define BOOL3_TRUE
Definition: shape_polygon.cpp:65
CSG_Points
Definition: geo_tools.h:185
SHAPE_TYPE_Line
@ SHAPE_TYPE_Line
Definition: shapes.h:104
SG_Is_Point_On_Line
bool SG_Is_Point_On_Line(const TSG_Point &Point, const TSG_Point &Line_A, const TSG_Point &Line_B, bool bExactMatch, double Epsilon)
Definition: geo_functions.cpp:394
CSG_Shape_Points::m_nParts
int m_nParts
Definition: shapes.h:561
CSG_Shape_Points::_Invalidate
virtual void _Invalidate(void)
Definition: shapes.h:574
BOOL3_FALSE
#define BOOL3_FALSE
Definition: shape_polygon.cpp:64
CSG_Shape::Get_Point_Count
virtual int Get_Point_Count(void) const =0
shapes.h
B
#define B
CSG_Shape_Polygon_Part::Get_Perimeter
double Get_Perimeter(void)
Definition: shapes.h:652
CSG_Shape_Polygon::is_Neighbour
bool is_Neighbour(CSG_Shape_Polygon *pPolygon, bool bSimpleCheck=true)
Definition: shape_polygon.cpp:1081
SHAPE_TYPE_Point
@ SHAPE_TYPE_Point
Definition: shapes.h:102
CSG_Shape_Polygon_Part::Get_Area
double Get_Area(void)
Definition: shapes.h:654
SSG_Point::x
double x
Definition: geo_tools.h:129
CSG_Shape_Points::Get_Extent
virtual const CSG_Rect & Get_Extent(void)
Definition: shapes.h:541
CSG_Lines::Get_Length
double Get_Length(void) const
Definition: geo_classes.cpp:508
SSG_Rect::yMin
double yMin
Definition: geo_tools.h:468
CSG_Rect::Get_XCenter
double Get_XCenter(void) const
Definition: geo_tools.h:520
CSG_Shape_Part::Get_Count
int Get_Count(void) const
Definition: shapes.h:384
SSG_Point::y
double y
Definition: geo_tools.h:129
CSG_Shape_Polygon_Part::m_Area
double m_Area
Definition: shapes.h:683
CSG_Shape_Polygon::is_Lake
bool is_Lake(int iPart)
Definition: shape_polygon.cpp:766
SG_IS_BETWEEN
#define SG_IS_BETWEEN(a, x, b)
Definition: geo_tools.h:90
CSG_Rect::Get_YCenter
double Get_YCenter(void) const
Definition: geo_tools.h:521
CSG_Shape_Polygon_Part::_Update_Area
void _Update_Area(void)
Definition: shape_polygon.cpp:101
CSG_Shape_Points::Get_Point_Count
virtual int Get_Point_Count(void) const
Definition: shapes.h:494
CSG_Shapes
Definition: shapes.h:773
SHAPE_TYPE_Points
@ SHAPE_TYPE_Points
Definition: shapes.h:103
CSG_Lines
Definition: geo_tools.h:217
INTERSECTION_Contained
@ INTERSECTION_Contained
Definition: geo_tools.h:105
SG_Get_Crossing
bool SG_Get_Crossing(TSG_Point &Crossing, const TSG_Point &a1, const TSG_Point &a2, const TSG_Point &b1, const TSG_Point &b2, bool bExactMatch)
Definition: geo_functions.cpp:280
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
CSG_Shape_Part
Definition: shapes.h:370
CSG_Shape_Polygon_Part::Get_Shared_Edges
CSG_Lines Get_Shared_Edges(CSG_Shape_Polygon_Part *pPart, bool bVertexCheck, double Epsilon=0.)
Definition: shape_polygon.cpp:434
CSG_Shape_Polygon_Part::Get_Shared_Length
double Get_Shared_Length(CSG_Shape_Polygon_Part *pPart, bool bVertexCheck, double Epsilon=0.)
Definition: shape_polygon.cpp:541
CSG_Shape_Polygon_Part::Contains
bool Contains(const CSG_Point &p)
Definition: shape_polygon.cpp:244