KiCad PCB EDA Suite
polygon_test_point_inside.h File Reference

Go to the source code of this file.

Classes

class  wxPoint
 

Functions

bool TestPointInsidePolygon (const CPOLYGONS_LIST &aPolysList, int aIdxstart, int aIdxend, int aRefx, int aRefy)
 Function TestPointInsidePolygon test if a point is inside or outside a polygon. More...
 
bool TestPointInsidePolygon (const wxPoint *aPolysList, int aCount, const wxPoint &aRefPoint)
 Function TestPointInsidePolygon (overlaid) same as previous, but mainly use wxPoint. More...
 

Function Documentation

bool TestPointInsidePolygon ( const CPOLYGONS_LIST aPolysList,
int  aIdxstart,
int  aIdxend,
int  aRefx,
int  aRefy 
)

Function TestPointInsidePolygon test if a point is inside or outside a polygon.

Parameters
aPolysListthe list of polygons
aIdxstartthe starting point of a given polygon in m_FilledPolysList.
aIdxendthe ending point of the polygon in m_FilledPolysList.
aRefx,aRefythe point coordinate to test
Returns
true if the point is inside, false for outside

the polygon must have only lines (not arcs) for outlines.

Parameters
aPolysListthe list of polygons
aIdxstartthe starting point of a given polygon in m_FilledPolysList.
aIdxendthe ending point of this polygon in m_FilledPolysList.
aRefx,aRefythe point coordinate to test
Returns
true if the point is inside, false for outside

Definition at line 53 of file polygon_test_point_inside.cpp.

References CPOLYGONS_LIST::GetX(), CPOLYGONS_LIST::GetY(), INSIDE, and OUTSIDE.

Referenced by convex2pointDRC(), WS_DRAW_ITEM_POLYGON::HitTest(), D_PAD::HitTest(), poly2polyDRC(), poly2segmentDRC(), and CPolyLine::TestPointInside().

69 {
70  // count intersection points to right of (refx,refy). If odd number, point (refx,refy) is inside polyline
71  int ics, ice;
72  int count = 0;
73 
74  // find all intersection points of line with polyline sides
75  for( ics = aIdxstart, ice = aIdxend; ics <= aIdxend; ice = ics++ )
76  {
77  int seg_startX = aPolysList.GetX( ics );
78  int seg_startY = aPolysList.GetY( ics );
79  int seg_endX = aPolysList.GetX( ice );
80  int seg_endY = aPolysList.GetY( ice );
81 
82  /* Trivial cases: skip if ref above or below the segment to test */
83  if( ( seg_startY > aRefy ) && (seg_endY > aRefy ) )
84  continue;
85 
86  // segment below ref point, or one of its ends has the same Y pos as the ref point: skip
87  // So we eliminate one end point of 2 consecutive segments.
88  // Note: also we skip horizontal segments if ref point is on this horizontal line
89  // So reference points on horizontal segments outlines always are seen as outside the polygon
90  if( ( seg_startY <= aRefy ) && (seg_endY <= aRefy ) )
91  continue;
92 
93  /* refy is between seg_startY and seg_endY.
94  * note: here: horizontal segments (seg_startY == seg_endY) are skipped,
95  * either by the first test or by the second test
96  * see if an horizontal semi infinite line from refx is intersecting the segment
97  */
98 
99  // calculate the x position of the intersection of this segment and the semi infinite line
100  // this is more easier if we move the X,Y axis origin to the segment start point:
101  seg_endX -= seg_startX;
102  seg_endY -= seg_startY;
103  double newrefx = (double) (aRefx - seg_startX);
104  double newrefy = (double) (aRefy - seg_startY);
105 
106  // Now calculate the x intersection coordinate of the line from (0,0) to (seg_endX,seg_endY)
107  // with the horizontal line at the new refy position
108  // the line slope = seg_endY/seg_endX;
109  // and the x pos relative to the new origin is intersec_x = refy/slope
110  // Note: because horizontal segments are skipped, 1/slope exists (seg_endY never == O)
111  double intersec_x = (newrefy * seg_endX) / seg_endY;
112  if( newrefx < intersec_x ) // Intersection found with the semi-infinite line from refx to infinite
113  count++;
114  }
115 
116  return count & 1 ? INSIDE : OUTSIDE;
117 }
#define OUTSIDE
int GetY(int ic) const
Definition: PolyLine.h:128
int GetX(int ic) const
Definition: PolyLine.h:126
#define INSIDE
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 123 of file polygon_test_point_inside.cpp.

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

124 {
125  // count intersection points to right of (refx,refy). If odd number, point (refx,refy) is inside polyline
126  int ics, ice;
127  int count = 0;
128  // find all intersection points of line with polyline sides
129  for( ics = 0, ice = aCount-1; ics < aCount; ice = ics++ )
130  {
131  int seg_startX = aPolysList[ics].x;
132  int seg_startY = aPolysList[ics].y;
133  int seg_endX = aPolysList[ice].x;
134  int seg_endY = aPolysList[ice].y;
135 
136  /* Trivial cases: skip if ref above or below the segment to test */
137  if( ( seg_startY > aRefPoint.y ) && (seg_endY > aRefPoint.y ) )
138  continue;
139 
140  // segment below ref point, or one of its ends has the same Y pos as the ref point: skip
141  // So we eliminate one end point of 2 consecutive segments.
142  // Note: also we skip horizontal segments if ref point is on this horizontal line
143  // So reference points on horizontal segments outlines always are seen as outside the polygon
144  if( ( seg_startY <= aRefPoint.y ) && (seg_endY <= aRefPoint.y ) )
145  continue;
146 
147  /* refy is between seg_startY and seg_endY.
148  * note: here: horizontal segments (seg_startY == seg_endY) are skipped,
149  * either by the first test or by the second test
150  * see if an horizontal semi infinite line from refx is intersecting the segment
151  */
152 
153  // calculate the x position of the intersection of this segment and the semi infinite line
154  // this is more easier if we move the X,Y axis origin to the segment start point:
155  seg_endX -= seg_startX;
156  seg_endY -= seg_startY;
157  double newrefx = (double) (aRefPoint.x - seg_startX);
158  double newrefy = (double) (aRefPoint.y - seg_startY);
159 
160  // Now calculate the x intersection coordinate of the line from (0,0) to (seg_endX,seg_endY)
161  // with the horizontal line at the new refy position
162  // the line slope = seg_endY/seg_endX;
163  // and the x pos relative to the new origin is intersec_x = refy/slope
164  // Note: because horizontal segments are skipped, 1/slope exists (seg_endY never == O)
165  double intersec_x = (newrefy * seg_endX) / seg_endY;
166  if( newrefx < intersec_x ) // Intersection found with the semi-infinite line from refx to infinite
167  count++;
168  }
169 
170  return count & 1 ? INSIDE : OUTSIDE;
171 }
#define OUTSIDE
#define INSIDE