KiCad PCB EDA Suite
polygon_test_point_inside.cpp File Reference

Go to the source code of this file.

Macros

#define OUTSIDE   false
 
#define INSIDE   true
 

Functions

bool TestPointInsidePolygon (const wxPoint *aPolysList, int aCount, const wxPoint &aRefPoint)
 Function TestPointInsidePolygon (overlaid) same as previous, but mainly use wxPoint. More...
 

Macro Definition Documentation

◆ INSIDE

#define INSIDE   true

Definition at line 49 of file polygon_test_point_inside.cpp.

◆ OUTSIDE

#define OUTSIDE   false

Definition at line 48 of file polygon_test_point_inside.cpp.

Function Documentation

◆ TestPointInsidePolygon()

bool TestPointInsidePolygon ( const wxPoint aPolysList,
int  aCount,
const wxPoint aRefPoint 
)

Function TestPointInsidePolygon (overlaid) same as previous, but mainly use wxPoint.

Parameters
aPolysListthe list of polygons
aCountcorners count in aPolysList.
aRefPointthe point coordinate to test
Returns
true if the point is inside, false for outside

Definition at line 55 of file polygon_test_point_inside.cpp.

56 {
57  // count intersection points to right of (refx,refy). If odd number, point (refx,refy) is inside polyline
58  int ics, ice;
59  int count = 0;
60  // find all intersection points of line with polyline sides
61  for( ics = 0, ice = aCount-1; ics < aCount; ice = ics++ )
62  {
63  int seg_startX = aPolysList[ics].x;
64  int seg_startY = aPolysList[ics].y;
65  int seg_endX = aPolysList[ice].x;
66  int seg_endY = aPolysList[ice].y;
67 
68  /* Trivial cases: skip if ref above or below the segment to test */
69  if( ( seg_startY > aRefPoint.y ) && (seg_endY > aRefPoint.y ) )
70  continue;
71 
72  // segment below ref point, or one of its ends has the same Y pos as the ref point: skip
73  // So we eliminate one end point of 2 consecutive segments.
74  // Note: also we skip horizontal segments if ref point is on this horizontal line
75  // So reference points on horizontal segments outlines always are seen as outside the polygon
76  if( ( seg_startY <= aRefPoint.y ) && (seg_endY <= aRefPoint.y ) )
77  continue;
78 
79  /* refy is between seg_startY and seg_endY.
80  * note: here: horizontal segments (seg_startY == seg_endY) are skipped,
81  * either by the first test or by the second test
82  * see if an horizontal semi infinite line from refx is intersecting the segment
83  */
84 
85  // calculate the x position of the intersection of this segment and the semi infinite line
86  // this is more easier if we move the X,Y axis origin to the segment start point:
87  seg_endX -= seg_startX;
88  seg_endY -= seg_startY;
89  double newrefx = (double) (aRefPoint.x - seg_startX);
90  double newrefy = (double) (aRefPoint.y - seg_startY);
91 
92  // Now calculate the x intersection coordinate of the line from (0,0) to (seg_endX,seg_endY)
93  // with the horizontal line at the new refy position
94  // the line slope = seg_endY/seg_endX;
95  // and the x pos relative to the new origin is intersec_x = refy/slope
96  // Note: because horizontal segments are skipped, 1/slope exists (seg_endY never == O)
97  double intersec_x = (newrefy * seg_endX) / seg_endY;
98  if( newrefx < intersec_x ) // Intersection found with the semi-infinite line from refx to infinite
99  count++;
100  }
101 
102  return count & 1 ? INSIDE : OUTSIDE;
103 }
#define OUTSIDE
#define INSIDE

References INSIDE, OUTSIDE, wxPoint::x, and wxPoint::y.

Referenced by D_PAD::HitTest(), poly2polyDRC(), and poly2segmentDRC().