SAGA API v9.10
Loading...
Searching...
No Matches
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//---------------------------------------------------------
81
82//---------------------------------------------------------
85
86
88// //
90
91//---------------------------------------------------------
99
100//---------------------------------------------------------
101void 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//---------------------------------------------------------
155
156//---------------------------------------------------------
157TSG_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//---------------------------------------------------------
223bool CSG_Shape_Polygon_Part::is_OnEdge(const CSG_Point &p)
224{
225 return( is_OnEdge(p.x, p.y) );
226}
227
228//---------------------------------------------------------
229bool 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//---------------------------------------------------------
244bool CSG_Shape_Polygon_Part::Contains(const CSG_Point &p)
245{
246 return( Contains(p.x, p.y) );
247}
248
249//---------------------------------------------------------
250bool 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//---------------------------------------------------------
312bool 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//---------------------------------------------------------
358void 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//---------------------------------------------------------
395bool 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//---------------------------------------------------------
434CSG_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//---------------------------------------------------------
541double 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//---------------------------------------------------------
554double 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//---------------------------------------------------------
593CSG_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//---------------------------------------------------------
602
603
605// //
607
608//---------------------------------------------------------
609void 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//---------------------------------------------------------
630TSG_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//---------------------------------------------------------
718TSG_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//---------------------------------------------------------
766bool 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//---------------------------------------------------------
826bool 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//---------------------------------------------------------
834double 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//---------------------------------------------------------
842double 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//---------------------------------------------------------
855double 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//---------------------------------------------------------
863double 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//---------------------------------------------------------
876TSG_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//---------------------------------------------------------
889TSG_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//---------------------------------------------------------
932TSG_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//---------------------------------------------------------
938TSG_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//---------------------------------------------------------
950
951//---------------------------------------------------------
952TSG_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//---------------------------------------------------------
984bool CSG_Shape_Polygon::is_OnEdge(const CSG_Point &p, int iPart)
985{
986 return( is_OnEdge(p.x, p.y, iPart) );
987}
988
989//---------------------------------------------------------
990bool 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//---------------------------------------------------------
998bool CSG_Shape_Polygon::is_OnEdge(const CSG_Point &p)
999{
1000 return( is_OnEdge(p.x, p.y) );
1001}
1002
1003//---------------------------------------------------------
1004bool 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//---------------------------------------------------------
1026bool CSG_Shape_Polygon::Contains(const CSG_Point &p, int iPart)
1027{
1028 return( Contains(p.x, p.y, iPart) );
1029}
1030
1031//---------------------------------------------------------
1032bool 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//---------------------------------------------------------
1040bool CSG_Shape_Polygon::Contains(const CSG_Point &p)
1041{
1042 return( Contains(p.x, p.y) );
1043}
1044
1045//---------------------------------------------------------
1046bool 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//---------------------------------------------------------
1081bool 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//---------------------------------------------------------
1138CSG_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//---------------------------------------------------------
1163double 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//---------------------------------------------------------
1176double 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//---------------------------------------------------------
sLong
signed long long sLong
Definition api_core.h:158
CSG_Index
Definition mat_tools.h:200
CSG_Lines
Definition geo_tools.h:217
CSG_Lines::Add
CSG_Points & Add(void)
Definition geo_classes.cpp:437
CSG_Lines::Get_Length
double Get_Length(void) const
Definition geo_classes.cpp:508
CSG_Lines::Get_Count
sLong Get_Count(void) const
Definition geo_tools.h:240
CSG_Point
Definition geo_tools.h:135
CSG_Points
Definition geo_tools.h:185
CSG_Points::Add
bool Add(double x, double y)
Definition geo_classes.cpp:350
CSG_Points::Get_Count
sLong Get_Count(void) const
Definition geo_tools.h:201
CSG_Rect::Get_YCenter
double Get_YCenter(void) const
Definition geo_tools.h:521
CSG_Rect::Intersects
TSG_Intersection Intersects(const CSG_Rect &Rect) const
Definition geo_classes.cpp:881
CSG_Rect::Get_XCenter
double Get_XCenter(void) const
Definition geo_tools.h:520
CSG_Shape_Part::CSG_Shape_Points
friend class CSG_Shape_Points
Definition shapes.h:370
CSG_Shape_Part::m_nPoints
int m_nPoints
Definition shapes.h:457
CSG_Shape_Part::Get_Extent
const CSG_Rect & Get_Extent(void)
Definition shapes.h:381
CSG_Shape_Part::Get_Point
TSG_Point Get_Point(int iPoint, bool bAscending=true) const
Definition shapes.h:385
CSG_Shape_Part::m_Points
TSG_Point * m_Points
Definition shapes.h:461
CSG_Shape_Part::CSG_Shape_Part
CSG_Shape_Part(class CSG_Shape_Points *pOwner)
Definition shape_part.cpp:63
CSG_Shape_Part::Get_Count
int Get_Count(void) const
Definition shapes.h:383
CSG_Shape_Part::_Invalidate
virtual void _Invalidate(void)
Definition shape_part.cpp:391
CSG_Shape_Points::CSG_Shape_Points
CSG_Shape_Points(class CSG_Shapes *pOwner, sLong Index)
Definition shape_points.cpp:63
CSG_Shape_Points::_Invalidate
virtual void _Invalidate(void)
Definition shapes.h:573
CSG_Shape_Points::CSG_Shape_Part
friend class CSG_Shape_Part
Definition shapes.h:485
CSG_Shape_Points::Get_Point
virtual TSG_Point Get_Point(int iPoint=0) const
Definition shape_points.cpp:294
CSG_Shape_Points::m_pParts
CSG_Shape_Part ** m_pParts
Definition shapes.h:566
CSG_Shape_Points::Get_Part_Count
virtual int Get_Part_Count(void) const
Definition shapes.h:495
CSG_Shape_Points::Get_Point_Count
virtual int Get_Point_Count(void) const
Definition shapes.h:493
CSG_Shape_Points::m_nParts
int m_nParts
Definition shapes.h:560
CSG_Shape_Points::Get_Extent
virtual const CSG_Rect & Get_Extent(void)
Definition shapes.h:540
CSG_Shape_Polygon_Part
Definition shapes.h:644
CSG_Shape_Polygon_Part::~CSG_Shape_Polygon_Part
virtual ~CSG_Shape_Polygon_Part(void)
Definition shape_polygon.cpp:83
CSG_Shape_Polygon_Part::m_bClockwise
int m_bClockwise
Definition shapes.h:680
CSG_Shape_Polygon_Part::Get_Point_Relation
TSG_Polygon_Point_Relation Get_Point_Relation(const CSG_Point &p)
Definition shape_polygon.cpp:151
CSG_Shape_Polygon_Part::Contains
bool Contains(const CSG_Point &p)
Definition shape_polygon.cpp:244
CSG_Shape_Polygon_Part::_Invalidate
virtual void _Invalidate(void)
Definition shape_polygon.cpp:92
CSG_Shape_Polygon_Part::m_bLake
int m_bLake
Definition shapes.h:680
CSG_Shape_Polygon_Part::m_Area
double m_Area
Definition shapes.h:682
CSG_Shape_Polygon_Part::Get_Perimeter
double Get_Perimeter(void)
Definition shapes.h:651
CSG_Shape_Polygon_Part::Get_Area
double Get_Area(void)
Definition shapes.h:653
CSG_Shape_Polygon_Part::m_Centroid
TSG_Point m_Centroid
Definition shapes.h:684
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_Part::Get_Centroid
const TSG_Point & Get_Centroid(void)
Definition shapes.h:655
CSG_Shape_Polygon_Part::is_Neighbour
bool is_Neighbour(CSG_Shape_Polygon_Part *pPart, bool bSimpleCheck=true)
Definition shape_polygon.cpp:312
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::m_Perimeter
double m_Perimeter
Definition shapes.h:682
CSG_Shape_Polygon_Part::Get_Distance
double Get_Distance(TSG_Point Point, TSG_Point &Next)
Definition shape_polygon.cpp:554
CSG_Shape_Polygon_Part::is_OnEdge
bool is_OnEdge(const CSG_Point &p)
Definition shape_polygon.cpp:223
CSG_Shape_Polygon_Part::_Update_Area
void _Update_Area(void)
Definition shape_polygon.cpp:101
CSG_Shape_Polygon_Part::is_Clockwise
bool is_Clockwise(void)
Definition shapes.h:649
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::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::CSG_Shape_Polygon_Part
CSG_Shape_Polygon_Part(class CSG_Shape_Points *pOwner)
Definition shape_polygon.cpp:75
CSG_Shape_Polygon::Get_Area
double Get_Area(void)
Definition shape_polygon.cpp:863
CSG_Shape_Polygon::~CSG_Shape_Polygon
virtual ~CSG_Shape_Polygon(void)
Definition shape_polygon.cpp:600
CSG_Shape_Polygon::Get_Perimeter
double Get_Perimeter(void)
Definition shape_polygon.cpp:842
CSG_Shape_Polygon::CSG_Shapes
friend class CSG_Shapes
Definition shapes.h:699
CSG_Shape_Polygon::is_OnEdge
bool is_OnEdge(const CSG_Point &p, int iPart)
Definition shape_polygon.cpp:984
CSG_Shape_Polygon::Get_Polygon_Part
CSG_Shape_Polygon_Part * Get_Polygon_Part(int iPart) const
Definition shapes.h:706
CSG_Shape_Polygon::Contains
bool Contains(const CSG_Point &p, int iPart)
Definition shape_polygon.cpp:1026
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_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_Shared_Edges
CSG_Lines Get_Shared_Edges(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon=0.)
Definition shape_polygon.cpp:1138
CSG_Shape_Polygon::Get_Centroid
TSG_Point Get_Centroid(void)
Definition shape_polygon.cpp:889
CSG_Shape_Polygon::Get_Shared_Length
double Get_Shared_Length(CSG_Shape_Polygon *pPolygon, bool bVertexCheck, double Epsilon=0.)
Definition shape_polygon.cpp:1163
CSG_Shape_Polygon::is_Lake
bool is_Lake(int iPart)
Definition shape_polygon.cpp:766
CSG_Shape_Polygon::_Invalidate
virtual void _Invalidate(void)
Definition shape_polygon.cpp:609
CSG_Shape_Polygon::is_Clockwise
bool is_Clockwise(int iPart)
Definition shape_polygon.cpp:826
CSG_Shape_Polygon::is_Neighbour
bool is_Neighbour(CSG_Shape_Polygon *pPolygon, bool bSimpleCheck=true)
Definition shape_polygon.cpp:1081
CSG_Shape_Polygon::m_bUpdate_Lakes
int m_bUpdate_Lakes
Definition shapes.h:751
CSG_Shape_Polygon::CSG_Shape_Polygon
CSG_Shape_Polygon(class CSG_Shapes *pOwner, sLong Index)
Definition shape_polygon.cpp:593
CSG_Shape_Polygon::On_Intersects
virtual TSG_Intersection On_Intersects(CSG_Shape *pShape)
Definition shape_polygon.cpp:630
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::Get_Part_Count
virtual int Get_Part_Count(void) const =0
CSG_Shape::Get_Point
virtual TSG_Point Get_Point(int iPoint=0) const =0
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
B
#define B
SG_Get_Distance
double SG_Get_Distance(double ax, double ay, double bx, double by, bool bPolar)
Definition geo_functions.cpp:103
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
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
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
A
#define A
C
#define C
TSG_Point
struct SSG_Point TSG_Point
TSG_Intersection
TSG_Intersection
Definition geo_tools.h:101
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
TSG_Rect
struct SSG_Rect TSG_Rect
SG_IS_BETWEEN
#define SG_IS_BETWEEN(a, x, b)
Definition geo_tools.h:90
BOOL3_FALSE
#define BOOL3_FALSE
Definition shape_polygon.cpp:64
BOOL3_NOTSET
#define BOOL3_NOTSET
Definition shape_polygon.cpp:63
BOOL3_TRUE
#define BOOL3_TRUE
Definition shape_polygon.cpp:65
TSG_Polygon_Point_Relation
TSG_Polygon_Point_Relation
Definition shapes.h:634
SG_POLYGON_POINT_Vertex
@ SG_POLYGON_POINT_Vertex
Definition shapes.h:636
SG_POLYGON_POINT_Edge
@ SG_POLYGON_POINT_Edge
Definition shapes.h:637
SG_POLYGON_POINT_Outside
@ SG_POLYGON_POINT_Outside
Definition shapes.h:635
SG_POLYGON_POINT_Interior
@ SG_POLYGON_POINT_Interior
Definition shapes.h:638
SHAPE_TYPE_Polygon
@ SHAPE_TYPE_Polygon
Definition shapes.h:105
SHAPE_TYPE_Line
@ SHAPE_TYPE_Line
Definition shapes.h:104
SHAPE_TYPE_Points
@ SHAPE_TYPE_Points
Definition shapes.h:103
SHAPE_TYPE_Point
@ SHAPE_TYPE_Point
Definition shapes.h:102
SSG_Point::x
double x
Definition geo_tools.h:129
SSG_Point::y
double y
Definition geo_tools.h:129
SSG_Rect::xMin
double xMin
Definition geo_tools.h:468
SSG_Rect::yMin
double yMin
Definition geo_tools.h:468