SAGA API  v9.5
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 *pA = m_Points;
162  TSG_Point *pB = m_Points + m_nPoints - 1;
163 
164  if( x == pB->x && y == pB->y ) // for performance reason check vertex first
165  {
166  return( SG_POLYGON_POINT_Vertex );
167  }
168 
169  double dy = pB->y - pA->y; // indicates the direction that we come from
170 
171  if( dy == 0.0 )
172  {
173  for(int iPoint=m_nPoints-2; dy==0.0 && iPoint>0; iPoint--)
174  {
175  dy = m_Points[iPoint].y - pA->y;
176  }
177  }
178 
179  int nCrossings = 0;
180 
181  for(int iPoint=0; iPoint<m_nPoints; iPoint++, pB=pA++)
182  {
183  if( x == pA->x && y == pA->y ) // for performance reason check vertex first
184  {
185  return( SG_POLYGON_POINT_Vertex );
186  }
187 
188  if( pA->x == pB->x && pA->y == pB->y ) // ignore doubles
189  {
190  continue;
191  }
192 
193  if( y < pA->y ) // pA above y
194  {
195  if( y > pB->y ) // pB below y
196  {
197  double cx = pB->x + (y - pB->y) * (pA->x - pB->x) / (pA->y - pB->y);
198 
199  if( cx == x )
200  {
201  return( SG_POLYGON_POINT_Edge );
202  }
203 
204  if( cx < x )
205  {
206  nCrossings++;
207  }
208  }
209  else if( y == pB->y && pB->x < x && dy < 0.0 )
210  {
211  nCrossings++;
212  }
213  }
214  else if( y > pA->y ) // pA below y
215  {
216  if( y < pB->y ) // pB above y
217  {
218  double cx = pB->x + (y - pB->y) * (pA->x - pB->x) / (pA->y - pB->y);
219 
220  if( cx == x )
221  {
222  return( SG_POLYGON_POINT_Edge );
223  }
224 
225  if( cx < x )
226  {
227  nCrossings++;
228  }
229  }
230  else if( y == pB->y && pB->x < x && dy > 0.0 )
231  {
232  nCrossings++;
233  }
234  }
235  else // pA on line y
236  {
237  if( y == pB->y ) // pB on line y
238  {
239  if( (pA->x < x && x < pB->x)
240  || (pA->x > x && x > pB->x) )
241  {
242  return( SG_POLYGON_POINT_Edge );
243  }
244  }
245  }
246 
247  if( pA->y != pB->y )
248  {
249  dy = pB->y - pA->y;
250  }
251  }
252 
253  if( nCrossings % 2 != 0 )
254  {
255  return( SG_POLYGON_POINT_Interior );
256  }
257  }
258 
259  return( SG_POLYGON_POINT_Outside );
260 }
261 
262 
264 // //
266 
267 //---------------------------------------------------------
268 bool CSG_Shape_Polygon_Part::is_OnEdge(const CSG_Point &p)
269 {
270  return( is_OnEdge(p.x, p.y) );
271 }
272 
273 //---------------------------------------------------------
274 bool CSG_Shape_Polygon_Part::is_OnEdge(double x, double y)
275 {
276  TSG_Polygon_Point_Relation r = Get_Point_Relation(x, y);
277 
278  return( r == SG_POLYGON_POINT_Vertex
279  || r == SG_POLYGON_POINT_Edge
280  );
281 }
282 
283 
285 // //
287 
288 //---------------------------------------------------------
289 bool CSG_Shape_Polygon_Part::Contains(const CSG_Point &p)
290 {
291  return( Contains(p.x, p.y) );
292 }
293 
294 //---------------------------------------------------------
295 bool CSG_Shape_Polygon_Part::Contains(double x, double y)
296 {
297  TSG_Polygon_Point_Relation r = Get_Point_Relation(x, y);
298 
299  return( r == SG_POLYGON_POINT_Interior
300  || r == SG_POLYGON_POINT_Vertex
301  || r == SG_POLYGON_POINT_Edge
302  );
303 
304  //-----------------------------------------------------
305  if( m_nPoints > 2 && Get_Extent().Contains(x, y) )
306  {
307  int nCrossings = 0;
308 
309  TSG_Point *pA = m_Points;
310  TSG_Point *pB = m_Points + m_nPoints - 1;
311 
312  for(int iPoint=0; iPoint<m_nPoints; iPoint++, pB=pA++)
313  {
314  if( y <= pA->y ) // pA on or above ray
315  {
316  if( pB->y <= y ) // pB on or below ray
317  {
318  if( ((y - pB->y) * (pA->x - pB->x)) >= ((x - pB->x) * (pA->y - pB->y)) )
319  {
320  nCrossings++;
321  }
322  }
323  }
324  else // pA below ray
325  {
326  if( pB->y >= y ) // pB above ray
327  {
328  if( ((y - pB->y) * (pA->x - pB->x)) <= ((x - pB->x) * (pA->y - pB->y)) )
329  {
330  nCrossings++;
331  }
332  }
333  }
334  }
335 
336  return( nCrossings % 2 != 0 );
337  }
338 
339  return( false );
340 }
341 
342 
344 // //
346 
347 //---------------------------------------------------------
356 //---------------------------------------------------------
357 bool CSG_Shape_Polygon_Part::is_Neighbour(CSG_Shape_Polygon_Part *pPart, bool bSimpleCheck)
358 {
359  if( !Get_Extent().Intersects(pPart->Get_Extent()) )
360  {
361  return( false );
362  }
363 
364  bool bNeighbour = false;
365 
366  //---------------------------------------------------------
367  for(int iPoint=0; iPoint<pPart->Get_Count(); iPoint++)
368  {
369  switch( Get_Point_Relation(pPart->Get_Point(iPoint)) )
370  {
371  case SG_POLYGON_POINT_Outside : break;
372  case SG_POLYGON_POINT_Interior: return( false );
373  case SG_POLYGON_POINT_Vertex :
374  case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
375  bNeighbour = true;
376  break;
377  }
378  }
379 
380  //---------------------------------------------------------
381  for(int iPoint=0; iPoint<Get_Count(); iPoint++)
382  {
383  switch( pPart->Get_Point_Relation(Get_Point(iPoint)) )
384  {
385  case SG_POLYGON_POINT_Outside : break;
386  case SG_POLYGON_POINT_Interior: return( false );
387  case SG_POLYGON_POINT_Vertex :
388  case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
389  bNeighbour = true;
390  break;
391  }
392  }
393 
394  return( bNeighbour );
395 }
396 
397 
399 // //
401 
402 //---------------------------------------------------------
403 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)
404 {
405  CSG_Points Points;
406 
407  for(int i=0; i<pPart->Get_Count(); i++)
408  {
409  CSG_Point P = pPart->Get_Point(i);
410 
411  if( P != P0 && P != P1 && SG_Is_Point_On_Line(P, P0, P1, true, Epsilon) )
412  {
413  Points.Add(P);
414  }
415  }
416 
417  if( Points.Get_Count() == 1 )
418  {
419  Part.Add(Points[0]);
420  }
421  else if( Points.Get_Count() > 1 )
422  {
423  double *Distances = new double[Points.Get_Count()];
424 
425  for(sLong i=0; i<Points.Get_Count(); i++)
426  {
427  Distances[i] = SG_Get_Distance(P0, Points[i]);
428  }
429 
430  CSG_Index Index(Points.Get_Count(), Distances); delete[](Distances);
431 
432  for(sLong i=0; i<Points.Get_Count(); i++)
433  {
434  Part.Add(Points[Index[i]]);
435  }
436  }
437 }
438 
439 //---------------------------------------------------------
440 bool CSG_Shape_Polygon_Part::_is_OnEdge(CSG_Shape_Polygon_Part *pPart, const CSG_Point &P, bool bVertex, double Epsilon)
441 {
442  CSG_Point P1 = pPart->Get_Point(0, false); // close the ring, starting with last point!
443 
444  if( !bVertex && P == P1 )
445  {
446  return( false );
447  }
448 
449  for(int i=0; i<pPart->Get_Count(); i++)
450  {
451  CSG_Point P0 = P1; P1 = pPart->Get_Point(i);
452 
453  if( !bVertex && P == P1 )
454  {
455  return( false );
456  }
457 
458  if( SG_Is_Point_On_Line(P, P0, P1, true, Epsilon) )
459  {
460  return( true );
461  }
462  }
463 
464  return( false );
465 }
466 
467 //---------------------------------------------------------
478 //---------------------------------------------------------
479 CSG_Lines CSG_Shape_Polygon_Part::Get_Shared_Edges(CSG_Shape_Polygon_Part *pPart, bool bVertexCheck, double Epsilon)
480 {
481  CSG_Lines Edges;
482 
483  if( Get_Extent().Intersects(pPart->Get_Extent()) )
484  {
485  if( bVertexCheck == false )
486  {
487  bool bOnEdge = is_OnEdge(pPart->Get_Point(0, false)); // close the ring, starting with last point!
488 
489  if( bOnEdge )
490  {
491  Edges.Add().Add(pPart->Get_Point(0, false));
492  }
493 
494  for(int i=0; i<pPart->Get_Count(); i++)
495  {
496  CSG_Point Point = pPart->Get_Point(i);
497 
498  if( is_OnEdge(Point) )
499  {
500  if( !bOnEdge ) // start a new edge segment
501  {
502  Edges.Add().Add(Point);
503  }
504  else // continue edge segment
505  {
506  Edges[Edges.Get_Count() - 1].Add(Point);
507  }
508 
509  bOnEdge = true;
510  }
511  else
512  {
513  bOnEdge = false;
514  }
515  }
516  }
517  else
518  {
519  CSG_Points Part; CSG_Point P1 = Get_Point(0, false); // close the ring, starting with last point!
520 
521  if( _is_OnEdge(pPart, P1, true, Epsilon) ) { Part.Add(P1); }
522 
523  for(int i=0; i<Get_Count(); i++)
524  {
525  CSG_Point P0 = P1; P1 = Get_Point(i);
526 
527  _Add_Edge_Points(pPart, P0, P1, Part, Epsilon);
528 
529  if( _is_OnEdge(pPart, P1, true, Epsilon) ) { Part.Add(P1); }
530  }
531 
532  //---------------------------------------------
533  if( Part.Get_Count() > 1 )
534  {
535  P1 = Part[0]; bool bOnEdge = false;
536  CSG_Point C0 = P1;
537 
538  for(sLong i=1, n=-1; i<Part.Get_Count(); i++)
539  {
540  CSG_Point C1, P0 = P1; P1 = Part[i];
541 
542  C1.x = P0.x + 0.5 * (P1.x - P0.x);
543  C1.y = P0.y + 0.5 * (P1.y - P0.y);
544 
545  if( C0 == C1 )
546  {
547  continue; // do not add the same edge twice (in different directions)
548  }
549 
550  if( _is_OnEdge(this, C1, true, Epsilon) && _is_OnEdge(pPart, C1, true, Epsilon) )
551  {
552  if( !bOnEdge ) // start a new edge segment
553  {
554  n = Edges.Get_Count(); Edges.Add();
555  Edges[n].Add(P0);
556  Edges[n].Add(P1);
557  }
558  else // continue edge segment
559  {
560  Edges[n].Add(P1);
561  }
562 
563  bOnEdge = true;
564  }
565  else
566  {
567  bOnEdge = false;
568  }
569 
570  C0 = C1;
571  }
572  }
573  }
574  }
575 
576  return( Edges );
577 }
578 
579 //---------------------------------------------------------
585 //---------------------------------------------------------
586 double CSG_Shape_Polygon_Part::Get_Shared_Length(CSG_Shape_Polygon_Part *pPart, bool bVertexCheck, double Epsilon)
587 {
588  CSG_Lines Edges(Get_Shared_Edges(pPart, bVertexCheck, Epsilon));
589 
590  return( Edges.Get_Length() );
591 }
592 
593 
595 // //
597 
598 //---------------------------------------------------------
599 double CSG_Shape_Polygon_Part::Get_Distance(TSG_Point Point, TSG_Point &Next)
600 {
601  if( m_nPoints < 1 )
602  {
603  return( -1.0 );
604  }
605 
606  if( Contains(Point) )
607  {
608  return( 0.0 );
609  }
610 
611  TSG_Point *pB = m_Points + m_nPoints - 1;
612  TSG_Point *pA = m_Points, C;
613 
614  double Distance = SG_Get_Nearest_Point_On_Line(Point, *pA, *pB, Next);
615 
616  for(int iPoint=0; iPoint<m_nPoints && Distance>0.0; iPoint++, pB=pA++)
617  {
618  double d = SG_Get_Nearest_Point_On_Line(Point, *pA, *pB, C);
619 
620  if( d >= 0.0 && d < Distance )
621  {
622  Distance = d;
623  Next = C;
624  }
625  }
626 
627  return( Distance );
628 }
629 
630 
632 // //
633 // //
634 // //
636 
637 //---------------------------------------------------------
638 CSG_Shape_Polygon::CSG_Shape_Polygon(CSG_Shapes *pOwner, sLong Index)
639  : CSG_Shape_Points(pOwner, Index)
640 {
641  m_bUpdate_Lakes = true;
642 }
643 
644 //---------------------------------------------------------
645 CSG_Shape_Polygon::~CSG_Shape_Polygon(void)
646 {}
647 
648 
650 // //
652 
653 //---------------------------------------------------------
654 void CSG_Shape_Polygon::_Invalidate(void)
655 {
656  CSG_Shape_Points::_Invalidate();
657 
658  if( m_bUpdate_Lakes )
659  {
660  m_bUpdate_Lakes = false;
661 
662  for(int i=0; i<m_nParts; i++)
663  {
664  Get_Polygon_Part(i)->m_bLake = BOOL3_NOTSET;
665  }
666  }
667 }
668 
669 
671 // //
673 
674 //---------------------------------------------------------
675 TSG_Intersection CSG_Shape_Polygon::On_Intersects(CSG_Shape *pShape)
676 {
677  //-----------------------------------------------------
678  bool bIn = false;
679  bool bOut = false;
680 
681  for(int iPart=0; iPart<pShape->Get_Part_Count(); iPart++)
682  {
683  for(int iPoint=0; iPoint<pShape->Get_Point_Count(iPart); iPoint++)
684  {
685  if( Contains(pShape->Get_Point(iPoint, iPart)) )
686  {
687  bIn = true;
688  }
689  else
690  {
691  bOut = true;
692  }
693 
694  if( bIn && bOut ) // some vertices are in, some are out
695  {
696  return( INTERSECTION_Overlaps );
697  }
698  }
699  }
700 
701  //-----------------------------------------------------
702  if( pShape->Get_Type() == SHAPE_TYPE_Point || pShape->Get_Type() == SHAPE_TYPE_Points )
703  {
704  return( bIn ? INTERSECTION_Contains : INTERSECTION_None ); // there are no other options for points
705  }
706 
707  //-----------------------------------------------------
708  for(int iPart=0; iPart<Get_Part_Count(); iPart++)
709  {
710  if( Get_Point_Count(iPart) < 3 )
711  {
712  continue;
713  }
714 
715  TSG_Point A[2], B[2], C; A[0] = Get_Point(0, iPart, false);
716 
717  for(int iPoint=0; iPoint<Get_Point_Count(iPart); iPoint++)
718  {
719  A[1] = A[0]; A[0] = Get_Point(iPoint, iPart);
720 
721  for(int jPart=0; jPart<pShape->Get_Part_Count(); jPart++)
722  {
723  //-----------------------------------------
724  if( pShape->Get_Type() == SHAPE_TYPE_Line && pShape->Get_Point_Count(jPart) >= 2 )
725  {
726  B[0] = pShape->Get_Point(0, jPart);
727 
728  for(int jPoint=1; jPoint<pShape->Get_Point_Count(jPart); jPoint++)
729  {
730  B[1] = B[0]; B[0] = pShape->Get_Point(jPoint, jPart);
731 
732  if( SG_Get_Crossing(C, A[0], A[1], B[0], B[1]) )
733  {
734  return( INTERSECTION_Overlaps );
735  }
736  }
737  }
738 
739  //-----------------------------------------
740  if( pShape->Get_Type() == SHAPE_TYPE_Polygon && pShape->Get_Point_Count(jPart) >= 3 )
741  {
742  B[0] = pShape->Get_Point(0, jPart, false);
743 
744  for(int jPoint=0; jPoint<pShape->Get_Point_Count(jPart); jPoint++)
745  {
746  B[1] = B[0]; B[0] = pShape->Get_Point(jPoint, jPart);
747 
748  if( SG_Get_Crossing(C, A[0], A[1], B[0], B[1]) )
749  {
750  return( INTERSECTION_Overlaps );
751  }
752  }
753  }
754  }
755  }
756  }
757 
758  //-----------------------------------------------------
759  return( bIn ? INTERSECTION_Contains : INTERSECTION_None );
760 }
761 
762 //---------------------------------------------------------
763 TSG_Intersection CSG_Shape_Polygon::On_Intersects(TSG_Rect Region)
764 {
765  // called if polygon's bounding box contains or overlaps with region.
766  // now let's figure out how region intersects with polygon itself
767 
768  //-----------------------------------------------------
769  for(int iPart=0; iPart<m_nParts; iPart++)
770  {
771  CSG_Shape_Part *pPart = m_pParts[iPart];
772 
773  switch( pPart->Get_Extent().Intersects(Region) )
774  {
775  case INTERSECTION_None: // region and polygon part are distinct
776  break;
777 
778  case INTERSECTION_Identical: // region contains polygon part
779  case INTERSECTION_Contained:
780  return( Get_Extent().Intersects(Region) );
781 
782  case INTERSECTION_Contains:
783  case INTERSECTION_Overlaps: // region at least partly contained by polygon part's extent, now let's look at the polygon part itself!
784  if( pPart->Get_Count() > 2 )
785  {
786  TSG_Point *pB = pPart->m_Points + pPart->m_nPoints - 1;
787  TSG_Point *pA = pPart->m_Points, C;
788 
789  for(int iPoint=0; iPoint<pPart->m_nPoints; iPoint++, pB=pA++)
790  {
791  if( SG_Get_Crossing_InRegion(C, *pA, *pB, Region) )
792  {
793  return( INTERSECTION_Overlaps );
794  }
795  }
796  }
797  break;
798  }
799  }
800 
801  //-----------------------------------------------------
802  return( Contains(Region.xMin, Region.yMin) ? INTERSECTION_Contains : INTERSECTION_None );
803 }
804 
805 
807 // //
809 
810 //---------------------------------------------------------
811 bool CSG_Shape_Polygon::is_Lake(int iPart)
812 {
813  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
814 
815  if( !pPart )
816  {
817  return( false );
818  }
819 
820  if( pPart->m_bLake == BOOL3_NOTSET )
821  {
822  if( pPart->m_nPoints < 1 || m_nParts <= 1 )
823  {
824  pPart->m_bLake = BOOL3_FALSE;
825  }
826  else
827  {
828  m_bUpdate_Lakes = true;
829 
830  pPart->m_bLake = BOOL3_FALSE;
831 
832  for(int iPoint=0; iPoint<pPart->m_nPoints; iPoint++) // find a point that is not on vertex/edge
833  {
834  TSG_Point p = pPart->Get_Point(iPoint);
835  bool bEdge = false;
836  int nContained = 0;
837 
838  for(iPart=0; !bEdge && iPart<m_nParts; iPart++)
839  {
840  if( pPart != m_pParts[iPart] )
841  {
842  switch( Get_Polygon_Part(iPart)->Get_Point_Relation(p) )
843  {
844  case SG_POLYGON_POINT_Outside : break;
845  case SG_POLYGON_POINT_Interior: nContained++; break;
846  case SG_POLYGON_POINT_Vertex :
847  case SG_POLYGON_POINT_Edge : bEdge = true; break;
848  }
849  }
850  }
851 
852  if( !bEdge )
853  {
854  pPart->m_bLake = nContained % 2 ? BOOL3_TRUE : BOOL3_FALSE;
855 
856  break;
857  }
858  }
859  }
860  }
861 
862  return( pPart->m_bLake == BOOL3_TRUE );
863 }
864 
865 
867 // //
869 
870 //---------------------------------------------------------
871 bool CSG_Shape_Polygon::is_Clockwise(int iPart)
872 {
873  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
874 
875  return( pPart && pPart->is_Clockwise() );
876 }
877 
878 //---------------------------------------------------------
879 double CSG_Shape_Polygon::Get_Perimeter(int iPart)
880 {
881  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
882 
883  return( pPart ? pPart->Get_Perimeter() : 0.0 );
884 }
885 
886 //---------------------------------------------------------
887 double CSG_Shape_Polygon::Get_Perimeter(void)
888 {
889  double Perimeter = 0.0;
890 
891  for(int iPart=0; iPart<m_nParts; iPart++)
892  {
893  Perimeter += Get_Perimeter(iPart);
894  }
895 
896  return( Perimeter );
897 }
898 
899 //---------------------------------------------------------
900 double CSG_Shape_Polygon::Get_Area(int iPart)
901 {
902  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
903 
904  return( pPart ? pPart->Get_Area() : 0.0 );
905 }
906 
907 //---------------------------------------------------------
908 double CSG_Shape_Polygon::Get_Area(void)
909 {
910  double Area = 0.0;
911 
912  for(int iPart=0; iPart<m_nParts; iPart++)
913  {
914  Area += is_Lake(iPart) ? -Get_Area(iPart) : Get_Area(iPart);
915  }
916 
917  return( Area );
918 }
919 
920 //---------------------------------------------------------
921 TSG_Point CSG_Shape_Polygon::Get_Centroid(int iPart)
922 {
923  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
924 
925  if( pPart )
926  {
927  return( pPart->Get_Centroid() );
928  }
929 
930  return( CSG_Point(0.0, 0.0) );
931 }
932 
933 //---------------------------------------------------------
934 TSG_Point CSG_Shape_Polygon::Get_Centroid(void)
935 {
936  if( m_nParts == 1 )
937  {
938  return( Get_Centroid(0) );
939  }
940 
941  int iPart;
942  double Weights;
943  TSG_Point Centroid;
944 
945  Centroid.x = 0.0;
946  Centroid.y = 0.0;
947 
948  for(iPart=0, Weights=0.0; iPart<m_nParts; iPart++)
949  {
950  if( !is_Lake(iPart) )
951  {
952  TSG_Point p = Get_Centroid(iPart);
953  double w = Get_Area (iPart);
954 
955  Centroid.x += w * p.x;
956  Centroid.y += w * p.y;
957 
958  Weights += w;
959  }
960  }
961 
962  if( Weights > 0.0 )
963  {
964  Centroid.x /= Weights;
965  Centroid.y /= Weights;
966  }
967 
968  return( Centroid );
969 }
970 
971 
973 // //
975 
976 //---------------------------------------------------------
977 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(const CSG_Point &p, int iPart)
978 {
979  return( Get_Point_Relation(p.x, p.y, iPart) );
980 }
981 
982 //---------------------------------------------------------
983 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(double x, double y, int iPart)
984 {
985  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
986 
987  return( pPart ? pPart->Get_Point_Relation(x, y) : SG_POLYGON_POINT_Outside );
988 }
989 
990 //---------------------------------------------------------
991 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(const CSG_Point &p)
992 {
993  return( Get_Point_Relation(p.x, p.y) );
994 }
995 
996 //---------------------------------------------------------
997 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(double x, double y)
998 {
999  if( Get_Extent().Contains(x, y) )
1000  {
1001  int nContained = 0;
1002 
1003  for(int iPart=0; iPart<m_nParts; iPart++)
1004  {
1005  switch( Get_Polygon_Part(iPart)->Get_Point_Relation(x, y) )
1006  {
1007  case SG_POLYGON_POINT_Outside : break;
1008  case SG_POLYGON_POINT_Interior: nContained++; break;
1009  case SG_POLYGON_POINT_Vertex : return( SG_POLYGON_POINT_Vertex );
1010  case SG_POLYGON_POINT_Edge : return( SG_POLYGON_POINT_Edge );
1011  }
1012  }
1013 
1014  if( nContained % 2 != 0 )
1015  {
1016  return( SG_POLYGON_POINT_Interior );
1017  }
1018  }
1019 
1020  return( SG_POLYGON_POINT_Outside );
1021 }
1022 
1023 
1025 // //
1027 
1028 //---------------------------------------------------------
1029 bool CSG_Shape_Polygon::is_OnEdge(const CSG_Point &p, int iPart)
1030 {
1031  return( is_OnEdge(p.x, p.y, iPart) );
1032 }
1033 
1034 //---------------------------------------------------------
1035 bool CSG_Shape_Polygon::is_OnEdge(double x, double y, int iPart)
1036 {
1037  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
1038 
1039  return( pPart && pPart->is_OnEdge(x, y) );
1040 }
1041 
1042 //---------------------------------------------------------
1043 bool CSG_Shape_Polygon::is_OnEdge(const CSG_Point &p)
1044 {
1045  return( is_OnEdge(p.x, p.y) );
1046 }
1047 
1048 //---------------------------------------------------------
1049 bool CSG_Shape_Polygon::is_OnEdge(double x, double y)
1050 {
1051  if( Get_Extent().Contains(x, y) )
1052  {
1053  for(int iPart=0; iPart<m_nParts; iPart++)
1054  {
1055  if( Get_Polygon_Part(iPart)->is_OnEdge(x, y) )
1056  {
1057  return( true );
1058  }
1059  }
1060  }
1061 
1062  return( false );
1063 }
1064 
1065 
1067 // //
1069 
1070 //---------------------------------------------------------
1071 bool CSG_Shape_Polygon::Contains(const CSG_Point &p, int iPart)
1072 {
1073  return( Contains(p.x, p.y, iPart) );
1074 }
1075 
1076 //---------------------------------------------------------
1077 bool CSG_Shape_Polygon::Contains(double x, double y, int iPart)
1078 {
1079  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
1080 
1081  return( pPart && pPart->Contains(x, y) );
1082 }
1083 
1084 //---------------------------------------------------------
1085 bool CSG_Shape_Polygon::Contains(const CSG_Point &p)
1086 {
1087  return( Contains(p.x, p.y) );
1088 }
1089 
1090 //---------------------------------------------------------
1091 bool CSG_Shape_Polygon::Contains(double x, double y)
1092 {
1093  if( Get_Extent().Contains(x, y) )
1094  {
1095  int nContained = 0;
1096 
1097  for(int iPart=0; iPart<m_nParts; iPart++)
1098  {
1099  if( Get_Polygon_Part(iPart)->Contains(x, y) )
1100  {
1101  nContained++;
1102  }
1103  }
1104 
1105  return( nContained % 2 != 0 );
1106  }
1107 
1108  return( false );
1109 }
1110 
1111 
1113 // //
1115 
1116 //---------------------------------------------------------
1125 //---------------------------------------------------------
1126 bool CSG_Shape_Polygon::is_Neighbour(CSG_Shape_Polygon *pPolygon, bool bSimpleCheck)
1127 {
1128  if( !Get_Extent().Intersects(pPolygon->Get_Extent()) )
1129  {
1130  return( false );
1131  }
1132 
1133  bool bNeighbour = false;
1134 
1135  //---------------------------------------------------------
1136  for(int iPoint=0; iPoint<pPolygon->Get_Point_Count(); iPoint++)
1137  {
1138  switch( Get_Point_Relation(pPolygon->Get_Point(iPoint)) )
1139  {
1140  case SG_POLYGON_POINT_Outside : break;
1141  case SG_POLYGON_POINT_Interior: return( false );
1142  case SG_POLYGON_POINT_Vertex :
1143  case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
1144  bNeighbour = true;
1145  break;
1146  }
1147  }
1148 
1149  //---------------------------------------------------------
1150  for(int iPoint=0; iPoint<Get_Point_Count(); iPoint++)
1151  {
1152  switch( pPolygon->Get_Point_Relation(Get_Point(iPoint)) )
1153  {
1154  case SG_POLYGON_POINT_Outside : break;
1155  case SG_POLYGON_POINT_Interior: return( false );
1156  case SG_POLYGON_POINT_Vertex :
1157  case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
1158  bNeighbour = true;
1159  break;
1160  }
1161  }
1162 
1163  return( bNeighbour );
1164 }
1165 
1166 
1168 // //
1170 
1171 //---------------------------------------------------------
1182 //---------------------------------------------------------
1183 CSG_Lines CSG_Shape_Polygon::Get_Shared_Edges(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon)
1184 {
1185  CSG_Lines Edges;
1186 
1187  if( Get_Extent().Intersects(pPolygon->Get_Extent()) )
1188  {
1189  for(int i=0; i<Get_Part_Count(); i++)
1190  {
1191  for(int j=0; j<pPolygon->Get_Part_Count(); j++)
1192  {
1193  Edges.Add(Get_Polygon_Part(i)->Get_Shared_Edges(pPolygon->Get_Polygon_Part(j), bVertexCheck, Epsilon));
1194  }
1195  }
1196  }
1197 
1198  return( Edges );
1199 }
1200 
1201 //---------------------------------------------------------
1207 //---------------------------------------------------------
1208 double CSG_Shape_Polygon::Get_Shared_Length(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon)
1209 {
1210  CSG_Lines Edges(Get_Shared_Edges(pPolygon, bVertexCheck, Epsilon));
1211 
1212  return( Edges.Get_Length() );
1213 }
1214 
1215 
1217 // //
1219 
1220 //---------------------------------------------------------
1221 double CSG_Shape_Polygon::Get_Distance(TSG_Point Point, TSG_Point &Next, int iPart) const
1222 {
1223  CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
1224 
1225  return( pPart ? pPart->Get_Distance(Point, Next) : -1. );
1226 }
1227 
1228 
1230 // //
1231 // //
1232 // //
1234 
1235 //---------------------------------------------------------
CSG_Index
Definition: mat_tools.h:200
SG_POLYGON_POINT_Edge
@ SG_POLYGON_POINT_Edge
Definition: shapes.h:640
CSG_Shape_Polygon_Part::is_Clockwise
bool is_Clockwise(void)
Definition: shapes.h:652
CSG_Shape_Polygon_Part::Get_Centroid
const TSG_Point & Get_Centroid(void)
Definition: shapes.h:658
CSG_Shape_Polygon::Get_Point_Relation
TSG_Polygon_Point_Relation Get_Point_Relation(const CSG_Point &p, int iPart)
Definition: shape_polygon.cpp:977
CSG_Shape_Points::m_pParts
CSG_Shape_Part ** m_pParts
Definition: shapes.h:569
CSG_Shape_Polygon_Part::is_Neighbour
bool is_Neighbour(CSG_Shape_Polygon_Part *pPart, bool bSimpleCheck=true)
Definition: shape_polygon.cpp:357
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:641
CSG_Shape_Polygon::m_bUpdate_Lakes
int m_bUpdate_Lakes
Definition: shapes.h:754
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:599
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:871
A
#define A
CSG_Shape_Part::Get_Point
TSG_Point Get_Point(int iPoint, bool bAscending=true) const
Definition: shapes.h:388
C
#define C
CSG_Shape_Polygon_Part
Definition: shapes.h:647
SHAPE_TYPE_Polygon
@ SHAPE_TYPE_Polygon
Definition: shapes.h:105
CSG_Shape_Polygon_Part::m_Perimeter
double m_Perimeter
Definition: shapes.h:685
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:486
CSG_Shape_Polygon::Get_Shared_Edges
CSG_Lines Get_Shared_Edges(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon=0.)
Definition: shape_polygon.cpp:1183
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:440
CSG_Shape_Polygon::is_OnEdge
bool is_OnEdge(const CSG_Point &p, int iPart)
Definition: shape_polygon.cpp:1029
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:1208
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:268
TSG_Polygon_Point_Relation
TSG_Polygon_Point_Relation
Definition: shapes.h:637
SSG_Rect::xMin
double xMin
Definition: geo_tools.h:465
SSG_Rect
Definition: geo_tools.h:464
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:403
CSG_Shape_Polygon_Part::m_bClockwise
int m_bClockwise
Definition: shapes.h:683
SG_POLYGON_POINT_Vertex
@ SG_POLYGON_POINT_Vertex
Definition: shapes.h:639
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:1071
CSG_Point
Definition: geo_tools.h:135
CSG_Points::Get_Count
sLong Get_Count(void) const
Definition: geo_tools.h:200
SG_POLYGON_POINT_Outside
@ SG_POLYGON_POINT_Outside
Definition: shapes.h:638
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:934
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:384
INTERSECTION_None
@ INTERSECTION_None
Definition: geo_tools.h:102
CSG_Shape_Part::m_Points
TSG_Point * m_Points
Definition: shapes.h:464
CSG_Shape_Polygon_Part::m_bLake
int m_bLake
Definition: shapes.h:683
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:687
CSG_Shape_Part::m_nPoints
int m_nPoints
Definition: shapes.h:460
CSG_Shape_Polygon::Get_Perimeter
double Get_Perimeter(void)
Definition: shape_polygon.cpp:887
CSG_Shape_Polygon::_Invalidate
virtual void _Invalidate(void)
Definition: shape_polygon.cpp:654
CSG_Shape_Polygon::On_Intersects
virtual TSG_Intersection On_Intersects(CSG_Shape *pShape)
Definition: shape_polygon.cpp:675
CSG_Shape_Polygon::Get_Distance
virtual double Get_Distance(TSG_Point Point, TSG_Point &Next, int iPart) const
Definition: shape_polygon.cpp:1221
CSG_Shape_Polygon::Get_Area
double Get_Area(void)
Definition: shape_polygon.cpp:908
CSG_Shape_Polygon::Get_Polygon_Part
CSG_Shape_Polygon_Part * Get_Polygon_Part(int iPart) const
Definition: shapes.h:709
CSG_Lines::Get_Count
sLong Get_Count(void) const
Definition: geo_tools.h:239
CSG_Shape_Polygon::~CSG_Shape_Polygon
virtual ~CSG_Shape_Polygon(void)
Definition: shape_polygon.cpp:645
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:638
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:184
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:563
CSG_Shape_Points::_Invalidate
virtual void _Invalidate(void)
Definition: shapes.h:576
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:654
CSG_Shape_Polygon::is_Neighbour
bool is_Neighbour(CSG_Shape_Polygon *pPolygon, bool bSimpleCheck=true)
Definition: shape_polygon.cpp:1126
SHAPE_TYPE_Point
@ SHAPE_TYPE_Point
Definition: shapes.h:102
CSG_Shape_Polygon_Part::Get_Area
double Get_Area(void)
Definition: shapes.h:656
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:543
CSG_Lines::Get_Length
double Get_Length(void) const
Definition: geo_classes.cpp:508
SSG_Rect::yMin
double yMin
Definition: geo_tools.h:465
CSG_Rect::Get_XCenter
double Get_XCenter(void) const
Definition: geo_tools.h:517
CSG_Shape_Part::Get_Count
int Get_Count(void) const
Definition: shapes.h:386
SSG_Point::y
double y
Definition: geo_tools.h:129
CSG_Shape_Polygon_Part::m_Area
double m_Area
Definition: shapes.h:685
CSG_Shape_Polygon::is_Lake
bool is_Lake(int iPart)
Definition: shape_polygon.cpp:811
CSG_Rect::Get_YCenter
double Get_YCenter(void) const
Definition: geo_tools.h:518
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:496
CSG_Shapes
Definition: shapes.h:775
SHAPE_TYPE_Points
@ SHAPE_TYPE_Points
Definition: shapes.h:103
CSG_Lines
Definition: geo_tools.h:216
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:498
CSG_Shape_Polygon
Definition: shapes.h:701
INTERSECTION_Overlaps
@ INTERSECTION_Overlaps
Definition: geo_tools.h:104
CSG_Shape
Definition: shapes.h:141
CSG_Shape_Part
Definition: shapes.h:372
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:479
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:586
CSG_Shape_Polygon_Part::Contains
bool Contains(const CSG_Point &p)
Definition: shape_polygon.cpp:289