KiCad PCB EDA Suite
polygon_test_point_inside.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2007-2014 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 2007-2014 KiCad Developers, see CHANGELOG.TXT for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
29 #include <cmath>
30 #include <vector>
31 #include <PolyLine.h>
32 
33 /* this algo uses the the Jordan curve theorem to find if a point is inside or outside a polygon:
34  * It run a semi-infinite line horizontally (increasing x, fixed y)
35  * out from the test point, and count how many edges it crosses.
36  * At each crossing, the ray switches between inside and outside.
37  * If odd count, the test point is inside the polygon
38  * This is called the Jordan curve theorem, or sometimes referred to as the "even-odd" test.
39  * Take care to starting and ending points of segments outlines, when the horizontal line crosses a segment outline
40  * exactly on an ending point:
41  * Because the starting point of a segment is also the ending point of the previous, only one must be used.
42  * And we do no use twice the same segment, so we do NOT use both starting and ending points of these 2 segments.
43  * So we must use only one ending point of each segment when calculating intersections
44  * but it cannot be always the starting or the ending point. This depend on relative position of 2 consectutive segments
45  * Here, the ending point above the Y reference position is used
46  * and the ending point below or equal the Y reference position is NOT used
47  * Obviously, others cases are irrelevant because there is not intersection.
48  */
49 
50 #define OUTSIDE false
51 #define INSIDE true
52 
53 bool TestPointInsidePolygon( const CPOLYGONS_LIST& aPolysList,
54  int aIdxstart,
55  int aIdxend,
56  int aRefx,
57  int aRefy)
58 
59 
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 }
118 
119 
120 /* Function TestPointInsidePolygon (overlaid)
121  * same as previous, but use wxPoint and aCount corners
122  */
123 bool TestPointInsidePolygon( const wxPoint *aPolysList, int aCount, const wxPoint &aRefPoint )
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 }
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.
#define OUTSIDE
int GetY(int ic) const
Definition: PolyLine.h:128
int GetX(int ic) const
Definition: PolyLine.h:126
CPOLYGONS_LIST handle a list of contours (polygons corners).
Definition: PolyLine.h:114
#define INSIDE