KiCad PCB EDA Suite
polygon_test_point_inside.cpp File Reference
#include <cmath>
#include <vector>
#include "polygon_test_point_inside.h"

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 52 of file polygon_test_point_inside.cpp.

◆ OUTSIDE

#define OUTSIDE   false

Definition at line 51 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 58 of file polygon_test_point_inside.cpp.

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

References INSIDE, and OUTSIDE.

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