1 /**********************************************************
2 * Version $Id$
3 *********************************************************/
4
5 ///////////////////////////////////////////////////////////
6 // //
7 // SAGA //
8 // //
9 // System for Automated Geoscientific Analyses //
10 // //
11 // Application Programming Interface //
12 // //
13 // Library: SAGA_API //
14 // //
15 //-------------------------------------------------------//
16 // //
17 // shape_polygon.cpp //
18 // //
19 // Copyright (C) 2005 by Olaf Conrad //
20 // //
21 //-------------------------------------------------------//
22 // //
23 // This file is part of 'SAGA - System for Automated //
24 // Geoscientific Analyses'. //
25 // //
26 // This library is free software; you can redistribute //
27 // it and/or modify it under the terms of the GNU Lesser //
28 // General Public License as published by the Free //
29 // Software Foundation, either version 2.1 of the //
30 // License, or (at your option) any later version. //
31 // //
32 // This library is distributed in the hope that it will //
33 // be useful, but WITHOUT ANY WARRANTY; without even the //
34 // implied warranty of MERCHANTABILITY or FITNESS FOR A //
35 // PARTICULAR PURPOSE. See the GNU Lesser General Public //
36 // License for more details. //
37 // //
38 // You should have received a copy of the GNU Lesser //
39 // General Public License along with this program; if //
40 // not, see <http://www.gnu.org/licenses/>. //
41 // //
42 //-------------------------------------------------------//
43 // //
44 // contact: Olaf Conrad //
45 // Institute of Geography //
46 // University of Goettingen //
47 // Goldschmidtstr. 5 //
48 // 37077 Goettingen //
49 // Germany //
50 // //
51 // e-mail: oconrad@saga-gis.org //
52 // //
53 ///////////////////////////////////////////////////////////
54
55 //---------------------------------------------------------
56
57
58 ///////////////////////////////////////////////////////////
59 // //
60 // //
61 // //
62 ///////////////////////////////////////////////////////////
63
64 //---------------------------------------------------------
65 #include "shapes.h"
66
67
68 ///////////////////////////////////////////////////////////
69 // //
70 // //
71 // //
72 ///////////////////////////////////////////////////////////
73
74 //---------------------------------------------------------
75 #define BOOL3_NOTSET -1
76 #define BOOL3_FALSE 0
77 #define BOOL3_TRUE 1
78
79
80 ///////////////////////////////////////////////////////////
81 // //
82 // //
83 // //
84 ///////////////////////////////////////////////////////////
85
86 //---------------------------------------------------------
CSG_Shape_Polygon_Part(CSG_Shape_Points * pOwner)87 CSG_Shape_Polygon_Part::CSG_Shape_Polygon_Part(CSG_Shape_Points *pOwner)
88 : CSG_Shape_Part(pOwner)
89 {
90 m_bLake = BOOL3_NOTSET;
91 m_bClockwise = BOOL3_NOTSET;
92 }
93
94 //---------------------------------------------------------
~CSG_Shape_Polygon_Part(void)95 CSG_Shape_Polygon_Part::~CSG_Shape_Polygon_Part(void)
96 {}
97
98
99 ///////////////////////////////////////////////////////////
100 // //
101 ///////////////////////////////////////////////////////////
102
103 //---------------------------------------------------------
_Invalidate(void)104 void CSG_Shape_Polygon_Part::_Invalidate(void)
105 {
106 CSG_Shape_Part::_Invalidate();
107
108 m_bLake = BOOL3_NOTSET;
109 m_bClockwise = BOOL3_NOTSET;
110 }
111
112 //---------------------------------------------------------
_Update_Area(void)113 void CSG_Shape_Polygon_Part::_Update_Area(void)
114 {
115 if( m_nPoints > 2 && m_bClockwise == BOOL3_NOTSET )
116 {
117 TSG_Point *pPoint, A, B;
118
119 m_Area = 0.0;
120 m_Perimeter = 0.0;
121
122 m_Centroid.x = 0.0;
123 m_Centroid.y = 0.0;
124
125 pPoint = m_Points + m_nPoints - 1;
126 B.x = pPoint->x - Get_Extent().Get_XCenter();
127 B.y = pPoint->y - Get_Extent().Get_YCenter();
128 pPoint = m_Points;
129
130 for(int iPoint=0; iPoint<m_nPoints; iPoint++, pPoint++, B=A)
131 {
132 A.x = pPoint->x - Get_Extent().Get_XCenter();
133 A.y = pPoint->y - Get_Extent().Get_YCenter();
134
135 double d = B.x * A.y - A.x * B.y;
136
137 m_Centroid.x += d * (A.x + B.x);
138 m_Centroid.y += d * (A.y + B.y);
139
140 m_Area += d;
141
142 m_Perimeter += SG_Get_Distance(A, B);
143 }
144
145 if( m_Area != 0.0 )
146 {
147 m_Centroid.x /= (3.0 * m_Area); m_Centroid.x += Get_Extent().Get_XCenter();
148 m_Centroid.y /= (3.0 * m_Area); m_Centroid.y += Get_Extent().Get_YCenter();
149 }
150
151 m_bClockwise = m_Area < 0.0 ? BOOL3_TRUE : BOOL3_FALSE;
152
153 m_Area = fabs(m_Area) / 2.0;
154 }
155 }
156
157
158 ///////////////////////////////////////////////////////////
159 // //
160 ///////////////////////////////////////////////////////////
161
162 //---------------------------------------------------------
Get_Point_Relation(const TSG_Point & p)163 TSG_Polygon_Point_Relation CSG_Shape_Polygon_Part::Get_Point_Relation(const TSG_Point &p)
164 {
165 return( Get_Point_Relation(p.x, p.y) );
166 }
167
168 //---------------------------------------------------------
Get_Point_Relation(double x,double y)169 TSG_Polygon_Point_Relation CSG_Shape_Polygon_Part::Get_Point_Relation(double x, double y)
170 {
171 if( m_nPoints > 2 && Get_Extent().Contains(x, y) )
172 {
173 TSG_Point *pA = m_Points;
174 TSG_Point *pB = m_Points + m_nPoints - 1;
175
176 if( x == pB->x && y == pB->y ) // for performance reason check vertex first
177 {
178 return( SG_POLYGON_POINT_Vertex );
179 }
180
181 double dy = pB->y - pA->y; // indicates the direction that we come from
182
183 if( dy == 0.0 )
184 {
185 for(int iPoint=m_nPoints-2; dy==0.0 && iPoint>0; iPoint--)
186 {
187 dy = m_Points[iPoint].y - pA->y;
188 }
189 }
190
191 int nCrossings = 0;
192
193 for(int iPoint=0; iPoint<m_nPoints; iPoint++, pB=pA++)
194 {
195 if( x == pA->x && y == pA->y ) // for performance reason check vertex first
196 {
197 return( SG_POLYGON_POINT_Vertex );
198 }
199
200 if( pA->x == pB->x && pA->y == pB->y ) // ignore doubles
201 {
202 continue;
203 }
204
205 if( y < pA->y ) // pA above y
206 {
207 if( y > pB->y ) // pB below y
208 {
209 double cx = pB->x + (y - pB->y) * (pA->x - pB->x) / (pA->y - pB->y);
210
211 if( cx == x )
212 {
213 return( SG_POLYGON_POINT_Edge );
214 }
215
216 if( cx < x )
217 {
218 nCrossings++;
219 }
220 }
221 else if( y == pB->y && pB->x < x && dy < 0.0 )
222 {
223 nCrossings++;
224 }
225 }
226 else if( y > pA->y ) // pA below y
227 {
228 if( y < pB->y ) // pB above y
229 {
230 double cx = pB->x + (y - pB->y) * (pA->x - pB->x) / (pA->y - pB->y);
231
232 if( cx == x )
233 {
234 return( SG_POLYGON_POINT_Edge );
235 }
236
237 if( cx < x )
238 {
239 nCrossings++;
240 }
241 }
242 else if( y == pB->y && pB->x < x && dy > 0.0 )
243 {
244 nCrossings++;
245 }
246 }
247 else // pA on line y
248 {
249 if( y == pB->y ) // pB on line y
250 {
251 if( (pA->x < x && x < pB->x)
252 || (pA->x > x && x > pB->x) )
253 {
254 return( SG_POLYGON_POINT_Edge );
255 }
256 }
257 }
258
259 if( pA->y != pB->y )
260 {
261 dy = pB->y - pA->y;
262 }
263 }
264
265 if( nCrossings % 2 != 0 )
266 {
267 return( SG_POLYGON_POINT_Interior );
268 }
269 }
270
271 return( SG_POLYGON_POINT_Outside );
272 }
273
274
275 ///////////////////////////////////////////////////////////
276 // //
277 ///////////////////////////////////////////////////////////
278
279 //---------------------------------------------------------
is_OnEdge(const TSG_Point & p)280 bool CSG_Shape_Polygon_Part::is_OnEdge(const TSG_Point &p)
281 {
282 return( is_OnEdge(p.x, p.y) );
283 }
284
285 //---------------------------------------------------------
is_OnEdge(double x,double y)286 bool CSG_Shape_Polygon_Part::is_OnEdge(double x, double y)
287 {
288 TSG_Polygon_Point_Relation r = Get_Point_Relation(x, y);
289
290 return( r == SG_POLYGON_POINT_Vertex
291 || r == SG_POLYGON_POINT_Edge
292 );
293 }
294
295
296 ///////////////////////////////////////////////////////////
297 // //
298 ///////////////////////////////////////////////////////////
299
300 //---------------------------------------------------------
Contains(const TSG_Point & p)301 bool CSG_Shape_Polygon_Part::Contains(const TSG_Point &p)
302 {
303 return( Contains(p.x, p.y) );
304 }
305
306 //---------------------------------------------------------
Contains(double x,double y)307 bool CSG_Shape_Polygon_Part::Contains(double x, double y)
308 {
309 TSG_Polygon_Point_Relation r = Get_Point_Relation(x, y);
310
311 return( r == SG_POLYGON_POINT_Interior
312 || r == SG_POLYGON_POINT_Vertex
313 || r == SG_POLYGON_POINT_Edge
314 );
315
316 //-----------------------------------------------------
317 if( m_nPoints > 2 && Get_Extent().Contains(x, y) )
318 {
319 int nCrossings = 0;
320
321 TSG_Point *pA = m_Points;
322 TSG_Point *pB = m_Points + m_nPoints - 1;
323
324 for(int iPoint=0; iPoint<m_nPoints; iPoint++, pB=pA++)
325 {
326 if( y <= pA->y ) // pA on or above ray
327 {
328 if( pB->y <= y ) // pB on or below ray
329 {
330 if( ((y - pB->y) * (pA->x - pB->x)) >= ((x - pB->x) * (pA->y - pB->y)) )
331 {
332 nCrossings++;
333 }
334 }
335 }
336 else // pA below ray
337 {
338 if( pB->y >= y ) // pB above ray
339 {
340 if( ((y - pB->y) * (pA->x - pB->x)) <= ((x - pB->x) * (pA->y - pB->y)) )
341 {
342 nCrossings++;
343 }
344 }
345 }
346 }
347
348 return( nCrossings % 2 != 0 );
349 }
350
351 return( false );
352 }
353
354
355 ///////////////////////////////////////////////////////////
356 // //
357 ///////////////////////////////////////////////////////////
358
359 //---------------------------------------------------------
360 /**
361 * Returns true if this polygon part touches that defined by pPart, i.e. the
362 * polygons share vertices or have vertices placed on the edge
363 * of the other. If bSimpleCheck is true the check is only
364 * performed until one shared vertex is found, which is
365 * sufficient if it can be expected that the polygons do not
366 * overlap.
367 */
368 //---------------------------------------------------------
is_Neighbour(CSG_Shape_Polygon_Part * pPart,bool bSimpleCheck)369 bool CSG_Shape_Polygon_Part::is_Neighbour(CSG_Shape_Polygon_Part *pPart, bool bSimpleCheck)
370 {
371 if( !Get_Extent().Intersects(pPart->Get_Extent()) )
372 {
373 return( false );
374 }
375
376 int iPoint; bool bNeighbour = false;
377
378 //---------------------------------------------------------
379 for(iPoint=0; iPoint<pPart->Get_Count(); iPoint++)
380 {
381 switch( Get_Point_Relation(pPart->Get_Point(iPoint)) )
382 {
383 case SG_POLYGON_POINT_Outside : break;
384 case SG_POLYGON_POINT_Interior: return( false );
385 case SG_POLYGON_POINT_Vertex :
386 case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
387 bNeighbour = true;
388 break;
389 }
390 }
391
392 //---------------------------------------------------------
393 for(iPoint=0; iPoint<Get_Count(); iPoint++)
394 {
395 switch( pPart->Get_Point_Relation(Get_Point(iPoint)) )
396 {
397 case SG_POLYGON_POINT_Outside : break;
398 case SG_POLYGON_POINT_Interior: return( false );
399 case SG_POLYGON_POINT_Vertex :
400 case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
401 bNeighbour = true;
402 break;
403 }
404 }
405
406 return( bNeighbour );
407 }
408
409
410 ///////////////////////////////////////////////////////////
411 // //
412 ///////////////////////////////////////////////////////////
413
414 //---------------------------------------------------------
Get_Distance(TSG_Point Point,TSG_Point & Next)415 double CSG_Shape_Polygon_Part::Get_Distance(TSG_Point Point, TSG_Point &Next)
416 {
417 if( m_nPoints < 1 )
418 {
419 return( -1.0 );
420 }
421
422 if( Contains(Point) )
423 {
424 return( 0.0 );
425 }
426
427 TSG_Point *pB = m_Points + m_nPoints - 1;
428 TSG_Point *pA = m_Points, C;
429
430 double Distance = SG_Get_Nearest_Point_On_Line(Point, *pA, *pB, Next);
431
432 for(int iPoint=0; iPoint<m_nPoints && Distance>0.0; iPoint++, pB=pA++)
433 {
434 double d = SG_Get_Nearest_Point_On_Line(Point, *pA, *pB, C);
435
436 if( d >= 0.0 && d < Distance )
437 {
438 Distance = d;
439 Next = C;
440 }
441 }
442
443 return( Distance );
444 }
445
446
447 ///////////////////////////////////////////////////////////
448 // //
449 // //
450 // //
451 ///////////////////////////////////////////////////////////
452
453 //---------------------------------------------------------
CSG_Shape_Polygon(CSG_Shapes * pOwner,int Index)454 CSG_Shape_Polygon::CSG_Shape_Polygon(CSG_Shapes *pOwner, int Index)
455 : CSG_Shape_Points(pOwner, Index)
456 {}
457
458 //---------------------------------------------------------
~CSG_Shape_Polygon(void)459 CSG_Shape_Polygon::~CSG_Shape_Polygon(void)
460 {}
461
462
463 ///////////////////////////////////////////////////////////
464 // //
465 ///////////////////////////////////////////////////////////
466
467 //---------------------------------------------------------
_Invalidate(void)468 void CSG_Shape_Polygon::_Invalidate(void)
469 {
470 CSG_Shape_Points::_Invalidate();
471
472 if( m_bUpdate_Lakes )
473 {
474 m_bUpdate_Lakes = false;
475
476 for(int i=0; i<m_nParts; i++)
477 {
478 Get_Polygon_Part(i)->m_bLake = BOOL3_NOTSET;
479 }
480 }
481 }
482
483
484 ///////////////////////////////////////////////////////////
485 // //
486 ///////////////////////////////////////////////////////////
487
488 //---------------------------------------------------------
On_Intersects(CSG_Shape * pShape)489 TSG_Intersection CSG_Shape_Polygon::On_Intersects(CSG_Shape *pShape)
490 {
491 //-----------------------------------------------------
492 int iPart;
493
494 bool bIn = false;
495 bool bOut = false;
496
497 for(iPart=0; iPart<pShape->Get_Part_Count(); iPart++)
498 {
499 for(int iPoint=0; iPoint<pShape->Get_Point_Count(iPart); iPoint++)
500 {
501 if( Contains(pShape->Get_Point(iPoint, iPart)) )
502 {
503 bIn = true;
504 }
505 else
506 {
507 bOut = true;
508 }
509
510 if( bIn && bOut ) // some vertices are in, some are out
511 {
512 return( INTERSECTION_Overlaps );
513 }
514 }
515 }
516
517 //-----------------------------------------------------
518 if( pShape->Get_Type() == SHAPE_TYPE_Point || pShape->Get_Type() == SHAPE_TYPE_Points )
519 {
520 return( bIn ? INTERSECTION_Contains : INTERSECTION_None ); // there are no other options for points
521 }
522
523 //-----------------------------------------------------
524 for(iPart=0; iPart<Get_Part_Count(); iPart++)
525 {
526 if( Get_Point_Count(iPart) < 3 )
527 {
528 continue;
529 }
530
531 TSG_Point A[2], B[2], C; A[0] = Get_Point(0, iPart, false);
532
533 for(int iPoint=0; iPoint<Get_Point_Count(iPart); iPoint++)
534 {
535 A[1] = A[0]; A[0] = Get_Point(iPoint, iPart);
536
537 for(int jPart=0; jPart<pShape->Get_Part_Count(); jPart++)
538 {
539 //-----------------------------------------
540 if( pShape->Get_Type() == SHAPE_TYPE_Line && pShape->Get_Point_Count(jPart) >= 2 )
541 {
542 B[0] = pShape->Get_Point(0, jPart);
543
544 for(int jPoint=1; jPoint<pShape->Get_Point_Count(jPart); jPoint++)
545 {
546 B[1] = B[0]; B[0] = pShape->Get_Point(jPoint, jPart);
547
548 if( SG_Get_Crossing(C, A[0], A[1], B[0], B[1]) )
549 {
550 return( INTERSECTION_Overlaps );
551 }
552 }
553 }
554
555 //-----------------------------------------
556 if( pShape->Get_Type() == SHAPE_TYPE_Polygon && pShape->Get_Point_Count(jPart) >= 3 )
557 {
558 B[0] = pShape->Get_Point(0, jPart, false);
559
560 for(int jPoint=0; jPoint<pShape->Get_Point_Count(jPart); jPoint++)
561 {
562 B[1] = B[0]; B[0] = pShape->Get_Point(jPoint, jPart);
563
564 if( SG_Get_Crossing(C, A[0], A[1], B[0], B[1]) )
565 {
566 return( INTERSECTION_Overlaps );
567 }
568 }
569 }
570 }
571 }
572 }
573
574 //-----------------------------------------------------
575 return( bIn ? INTERSECTION_Contains : INTERSECTION_None );
576 }
577
578 //---------------------------------------------------------
On_Intersects(TSG_Rect Region)579 TSG_Intersection CSG_Shape_Polygon::On_Intersects(TSG_Rect Region)
580 {
581 // called if polygon's bounding box contains or overlaps with region.
582 // now let's figure out how region intersects with polygon itself
583
584 //-----------------------------------------------------
585 for(int iPart=0; iPart<m_nParts; iPart++)
586 {
587 CSG_Shape_Part *pPart = m_pParts[iPart];
588
589 switch( pPart->Get_Extent().Intersects(Region) )
590 {
591 case INTERSECTION_None: // region and polygon part are distinct
592 break;
593
594 case INTERSECTION_Identical: // region contains polygon part
595 case INTERSECTION_Contained:
596 return( Get_Extent().Intersects(Region) );
597
598 case INTERSECTION_Contains:
599 case INTERSECTION_Overlaps: // region at least partly contained by polygon part's extent, now let's look at the polygon part itself!
600 if( pPart->Get_Count() > 2 )
601 {
602 TSG_Point *pB = pPart->m_Points + pPart->m_nPoints - 1;
603 TSG_Point *pA = pPart->m_Points, C;
604
605 for(int iPoint=0; iPoint<pPart->m_nPoints; iPoint++, pB=pA++)
606 {
607 if( SG_Get_Crossing_InRegion(C, *pA, *pB, Region) )
608 {
609 return( INTERSECTION_Overlaps );
610 }
611 }
612 }
613 break;
614 }
615 }
616
617 //-----------------------------------------------------
618 return( Contains(Region.xMin, Region.yMin) ? INTERSECTION_Contains : INTERSECTION_None );
619 }
620
621
622 ///////////////////////////////////////////////////////////
623 // //
624 ///////////////////////////////////////////////////////////
625
626 //---------------------------------------------------------
is_Lake(int iPart)627 bool CSG_Shape_Polygon::is_Lake(int iPart)
628 {
629 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
630
631 if( !pPart )
632 {
633 return( false );
634 }
635
636 if( pPart->m_bLake == BOOL3_NOTSET )
637 {
638 if( pPart->m_nPoints < 1 || m_nParts <= 1 )
639 {
640 pPart->m_bLake = BOOL3_FALSE;
641 }
642 else
643 {
644 m_bUpdate_Lakes = true;
645
646 pPart->m_bLake = BOOL3_FALSE;
647
648 for(int iPoint=0; iPoint<pPart->m_nPoints; iPoint++) // find a point that is not on vertex/edge
649 {
650 TSG_Point p = pPart->Get_Point(iPoint);
651 bool bEdge = false;
652 int nContained = 0;
653
654 for(iPart=0; !bEdge && iPart<m_nParts; iPart++)
655 {
656 if( pPart != m_pParts[iPart] )
657 {
658 switch( Get_Polygon_Part(iPart)->Get_Point_Relation(p) )
659 {
660 case SG_POLYGON_POINT_Outside : break;
661 case SG_POLYGON_POINT_Interior: nContained++; break;
662 case SG_POLYGON_POINT_Vertex :
663 case SG_POLYGON_POINT_Edge : bEdge = true; break;
664 }
665 }
666 }
667
668 if( !bEdge )
669 {
670 pPart->m_bLake = nContained % 2 ? BOOL3_TRUE : BOOL3_FALSE;
671
672 break;
673 }
674 }
675 }
676 }
677
678 return( pPart->m_bLake == BOOL3_TRUE );
679 }
680
681
682 ///////////////////////////////////////////////////////////
683 // //
684 ///////////////////////////////////////////////////////////
685
686 //---------------------------------------------------------
is_Clockwise(int iPart)687 bool CSG_Shape_Polygon::is_Clockwise(int iPart)
688 {
689 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
690
691 return( pPart && pPart->is_Clockwise() );
692 }
693
694 //---------------------------------------------------------
Get_Perimeter(int iPart)695 double CSG_Shape_Polygon::Get_Perimeter(int iPart)
696 {
697 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
698
699 return( pPart ? pPart->Get_Perimeter() : 0.0 );
700 }
701
702 //---------------------------------------------------------
Get_Perimeter(void)703 double CSG_Shape_Polygon::Get_Perimeter(void)
704 {
705 double Perimeter = 0.0;
706
707 for(int iPart=0; iPart<m_nParts; iPart++)
708 {
709 Perimeter += Get_Perimeter(iPart);
710 }
711
712 return( Perimeter );
713 }
714
715 //---------------------------------------------------------
Get_Area(int iPart)716 double CSG_Shape_Polygon::Get_Area(int iPart)
717 {
718 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
719
720 return( pPart ? pPart->Get_Area() : 0.0 );
721 }
722
723 //---------------------------------------------------------
Get_Area(void)724 double CSG_Shape_Polygon::Get_Area(void)
725 {
726 double Area = 0.0;
727
728 for(int iPart=0; iPart<m_nParts; iPart++)
729 {
730 Area += is_Lake(iPart) ? -Get_Area(iPart) : Get_Area(iPart);
731 }
732
733 return( Area );
734 }
735
736 //---------------------------------------------------------
Get_Centroid(int iPart)737 TSG_Point CSG_Shape_Polygon::Get_Centroid(int iPart)
738 {
739 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
740
741 if( pPart )
742 {
743 return( pPart->Get_Centroid() );
744 }
745
746 return( CSG_Point(0.0, 0.0) );
747 }
748
749 //---------------------------------------------------------
Get_Centroid(void)750 TSG_Point CSG_Shape_Polygon::Get_Centroid(void)
751 {
752 if( m_nParts == 1 )
753 {
754 return( Get_Centroid(0) );
755 }
756
757 int iPart;
758 double Weights;
759 TSG_Point Centroid;
760
761 Centroid.x = 0.0;
762 Centroid.y = 0.0;
763
764 for(iPart=0, Weights=0.0; iPart<m_nParts; iPart++)
765 {
766 if( !is_Lake(iPart) )
767 {
768 TSG_Point p = Get_Centroid(iPart);
769 double w = Get_Area (iPart);
770
771 Centroid.x += w * p.x;
772 Centroid.y += w * p.y;
773
774 Weights += w;
775 }
776 }
777
778 if( Weights > 0.0 )
779 {
780 Centroid.x /= Weights;
781 Centroid.y /= Weights;
782 }
783
784 return( Centroid );
785 }
786
787
788 ///////////////////////////////////////////////////////////
789 // //
790 ///////////////////////////////////////////////////////////
791
792 //---------------------------------------------------------
Get_Point_Relation(const TSG_Point & p,int iPart)793 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(const TSG_Point &p, int iPart)
794 {
795 return( Get_Point_Relation(p.x, p.y, iPart) );
796 }
797
798 //---------------------------------------------------------
Get_Point_Relation(double x,double y,int iPart)799 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(double x, double y, int iPart)
800 {
801 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
802
803 return( pPart ? pPart->Get_Point_Relation(x, y) : SG_POLYGON_POINT_Outside );
804 }
805
806 //---------------------------------------------------------
Get_Point_Relation(const TSG_Point & p)807 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(const TSG_Point &p)
808 {
809 return( Get_Point_Relation(p.x, p.y) );
810 }
811
812 //---------------------------------------------------------
Get_Point_Relation(double x,double y)813 TSG_Polygon_Point_Relation CSG_Shape_Polygon::Get_Point_Relation(double x, double y)
814 {
815 if( Get_Extent().Contains(x, y) )
816 {
817 int nContained = 0;
818
819 for(int iPart=0; iPart<m_nParts; iPart++)
820 {
821 switch( Get_Polygon_Part(iPart)->Get_Point_Relation(x, y) )
822 {
823 case SG_POLYGON_POINT_Outside : break;
824 case SG_POLYGON_POINT_Interior: nContained++; break;
825 case SG_POLYGON_POINT_Vertex : return( SG_POLYGON_POINT_Vertex );
826 case SG_POLYGON_POINT_Edge : return( SG_POLYGON_POINT_Edge );
827 }
828 }
829
830 if( nContained % 2 != 0 )
831 {
832 return( SG_POLYGON_POINT_Interior );
833 }
834 }
835
836 return( SG_POLYGON_POINT_Outside );
837 }
838
839
840 ///////////////////////////////////////////////////////////
841 // //
842 ///////////////////////////////////////////////////////////
843
844 //---------------------------------------------------------
is_OnEdge(const TSG_Point & p,int iPart)845 bool CSG_Shape_Polygon::is_OnEdge(const TSG_Point &p, int iPart)
846 {
847 return( is_OnEdge(p.x, p.y, iPart) );
848 }
849
850 //---------------------------------------------------------
is_OnEdge(double x,double y,int iPart)851 bool CSG_Shape_Polygon::is_OnEdge(double x, double y, int iPart)
852 {
853 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
854
855 return( pPart && pPart->is_OnEdge(x, y) );
856 }
857
858 //---------------------------------------------------------
is_OnEdge(const TSG_Point & p)859 bool CSG_Shape_Polygon::is_OnEdge(const TSG_Point &p)
860 {
861 return( is_OnEdge(p.x, p.y) );
862 }
863
864 //---------------------------------------------------------
is_OnEdge(double x,double y)865 bool CSG_Shape_Polygon::is_OnEdge(double x, double y)
866 {
867 if( Get_Extent().Contains(x, y) )
868 {
869 for(int iPart=0; iPart<m_nParts; iPart++)
870 {
871 if( Get_Polygon_Part(iPart)->is_OnEdge(x, y) )
872 {
873 return( true );
874 }
875 }
876 }
877
878 return( false );
879 }
880
881
882 ///////////////////////////////////////////////////////////
883 // //
884 ///////////////////////////////////////////////////////////
885
886 //---------------------------------------------------------
Contains(const TSG_Point & p,int iPart)887 bool CSG_Shape_Polygon::Contains(const TSG_Point &p, int iPart)
888 {
889 return( Contains(p.x, p.y, iPart) );
890 }
891
892 //---------------------------------------------------------
Contains(double x,double y,int iPart)893 bool CSG_Shape_Polygon::Contains(double x, double y, int iPart)
894 {
895 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
896
897 return( pPart && pPart->Contains(x, y) );
898 }
899
900 //---------------------------------------------------------
Contains(const TSG_Point & p)901 bool CSG_Shape_Polygon::Contains(const TSG_Point &p)
902 {
903 return( Contains(p.x, p.y) );
904 }
905
906 //---------------------------------------------------------
Contains(double x,double y)907 bool CSG_Shape_Polygon::Contains(double x, double y)
908 {
909 if( Get_Extent().Contains(x, y) )
910 {
911 int nContained = 0;
912
913 for(int iPart=0; iPart<m_nParts; iPart++)
914 {
915 if( Get_Polygon_Part(iPart)->Contains(x, y) )
916 {
917 nContained++;
918 }
919 }
920
921 return( nContained % 2 != 0 );
922 }
923
924 return( false );
925 }
926
927
928 ///////////////////////////////////////////////////////////
929 // //
930 ///////////////////////////////////////////////////////////
931
932 //---------------------------------------------------------
933 /**
934 * Returns true if this polygon touches pPolyogon, i.e. the
935 * polygons share vertices or have vertices placed on the edge
936 * of the other. If bSimpleCheck is true the check is only
937 * performed until one shared vertex is found, which is
938 * sufficient if it can be expected that the polygons do not
939 * overlap.
940 */
941 //---------------------------------------------------------
is_Neighbour(CSG_Shape_Polygon * pPolygon,bool bSimpleCheck)942 bool CSG_Shape_Polygon::is_Neighbour(CSG_Shape_Polygon *pPolygon, bool bSimpleCheck)
943 {
944 if( !Get_Extent().Intersects(pPolygon->Get_Extent()) )
945 {
946 return( false );
947 }
948
949 int iPoint; bool bNeighbour = false;
950
951 //---------------------------------------------------------
952 for(iPoint=0; iPoint<pPolygon->Get_Point_Count(); iPoint++)
953 {
954 switch( Get_Point_Relation(pPolygon->Get_Point(iPoint)) )
955 {
956 case SG_POLYGON_POINT_Outside : break;
957 case SG_POLYGON_POINT_Interior: return( false );
958 case SG_POLYGON_POINT_Vertex :
959 case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
960 bNeighbour = true;
961 break;
962 }
963 }
964
965 //---------------------------------------------------------
966 for(iPoint=0; iPoint<Get_Point_Count(); iPoint++)
967 {
968 switch( pPolygon->Get_Point_Relation(Get_Point(iPoint)) )
969 {
970 case SG_POLYGON_POINT_Outside : break;
971 case SG_POLYGON_POINT_Interior: return( false );
972 case SG_POLYGON_POINT_Vertex :
973 case SG_POLYGON_POINT_Edge : if( bSimpleCheck ) { return( true ); }
974 bNeighbour = true;
975 break;
976 }
977 }
978
979 return( bNeighbour );
980 }
981
982
983 ///////////////////////////////////////////////////////////
984 // //
985 ///////////////////////////////////////////////////////////
986
987 //---------------------------------------------------------
Get_Distance(TSG_Point Point,TSG_Point & Next,int iPart)988 double CSG_Shape_Polygon::Get_Distance(TSG_Point Point, TSG_Point &Next, int iPart)
989 {
990 CSG_Shape_Polygon_Part *pPart = Get_Polygon_Part(iPart);
991
992 return( pPart ? pPart->Get_Distance(Point, Next) : -1.0 );
993 }
994
995
996 ///////////////////////////////////////////////////////////
997 // //
998 // //
999 // //
1000 ///////////////////////////////////////////////////////////
1001
1002 //---------------------------------------------------------
1003