KiCad PCB EDA Suite
poly_grid_partition.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) 2016-2017 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
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 
26 #include <math/util.h>
27 
28 POLY_GRID_PARTITION::POLY_GRID_PARTITION( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize )
29 {
30  build( aPolyOutline, gridSize );
31 }
32 
33 
34 int POLY_GRID_PARTITION::ContainsPoint( const VECTOR2I& aP, int aClearance ) // const
35 {
36  if( containsPoint( aP ) )
37  return 1;
38 
39  if( aClearance > 0 )
40  return checkClearance( aP, aClearance );
41 
42  return 0;
43 }
44 
45 
46 int POLY_GRID_PARTITION::containsPoint( const VECTOR2I& aP, bool debug ) const
47 {
48  const auto gridPoint = poly2grid( aP );
49 
50  if( !m_bbox.Contains( aP ) )
51  return 0;
52 
53  SCAN_STATE state;
54  const EDGE_LIST& cell = m_grid[m_gridSize * gridPoint.y + gridPoint.x];
55 
56  scanCell( state, cell, aP, gridPoint.x, gridPoint.y );
57 
58  if( state.nearest < 0 )
59  {
60  state = SCAN_STATE();
61 
62  for( int d = 1; d <= m_gridSize; d++ )
63  {
64  int xl = gridPoint.x - d;
65  int xh = gridPoint.x + d;
66 
67  if( xl >= 0 )
68  {
69  const EDGE_LIST& cell2 = m_grid[m_gridSize * gridPoint.y + xl];
70  scanCell( state, cell2, aP, xl, gridPoint.y );
71 
72  if( state.nearest >= 0 )
73  break;
74  }
75 
76  if( xh < m_gridSize )
77  {
78  const EDGE_LIST& cell2 = m_grid[m_gridSize * gridPoint.y + xh];
79  scanCell( state, cell2, aP, xh, gridPoint.y );
80 
81  if( state.nearest >= 0 )
82  break;
83  }
84  }
85  }
86 
87 #ifdef TOM_EXTRA_VERBOSE
88  printf( "Nearest: %d prev: %d dmax %d\n", state.nearest, state.nearest_prev, state.dist_max );
89 #endif
90 
91  if( state.nearest < 0 )
92  return 0;
93 
94  if( state.dist_max == 0 )
95  return 1;
96 
97 
98  // special case for diagonal 'slits', e.g. two segments that partially overlap each other.
99  // Just love handling degeneracy... As I can't find any reliable way of fixing it for the moment,
100  // let's fall back to the good old O(N) point-in-polygon test
101  if( state.nearest_prev >= 0 && state.dist_max == state.dist_prev )
102  {
103  int d = std::abs( state.nearest_prev - state.nearest );
104 
105  if( ( d == 1 ) && ( ( m_flags[state.nearest_prev] & m_flags[state.nearest] ) == 0 ) )
106  {
107  return m_outline.PointInside( aP );
108  }
109  }
110 
111  if( state.dist_max > 0 )
112  {
113  return m_flags[state.nearest] & LEAD_EDGE ? 1 : 0;
114  }
115  else
116  {
117  return m_flags[state.nearest] & TRAIL_EDGE ? 1 : 0;
118  }
119 }
120 
121 
122 bool POLY_GRID_PARTITION::checkClearance( const VECTOR2I& aP, int aClearance )
123 {
124  int gx0 = poly2gridX( aP.x - aClearance - 1 );
125  int gx1 = poly2gridX( aP.x + aClearance + 1 );
126  int gy0 = poly2gridY( aP.y - aClearance - 1 );
127  int gy1 = poly2gridY( aP.y + aClearance + 1 );
128 
130 
131  ecoord dist = (ecoord) aClearance * aClearance;
132 
133  for( int gx = gx0; gx <= gx1; gx++ )
134  {
135  for( int gy = gy0; gy <= gy1; gy++ )
136  {
137  const auto& cell = m_grid[m_gridSize * gy + gx];
138  for( auto index : cell )
139  {
140  const auto& seg = m_outline.Segment( index );
141 
142  if( seg.SquaredDistance( aP ) <= dist )
143  return true;
144  }
145  }
146  }
147  return false;
148 }
149 
150 
151 int POLY_GRID_PARTITION::rescale_trunc( int aNumerator, int aValue, int aDenominator ) const
152 {
153  int64_t numerator = (int64_t) aNumerator * (int64_t) aValue;
154  return numerator / aDenominator;
155 }
156 
157 
158 // convertes grid cell coordinates to the polygon coordinates
160 {
163  return VECTOR2I( px, py );
164 }
165 
166 
168 {
170 }
171 
172 
174 {
176 }
177 
178 
180 {
183 
184  if( px < 0 )
185  px = 0;
186 
187  if( px >= m_gridSize )
188  px = m_gridSize - 1;
189 
190  if( py < 0 )
191  py = 0;
192 
193  if( py >= m_gridSize )
194  py = m_gridSize - 1;
195 
196  return VECTOR2I( px, py );
197 }
198 
199 
201 {
203 
204  if( px < 0 )
205  px = 0;
206 
207  if( px >= m_gridSize )
208  px = m_gridSize - 1;
209 
210  return px;
211 }
212 
213 
215 {
217 
218  if( py < 0 )
219  py = 0;
220 
221  if( py >= m_gridSize )
222  py = m_gridSize - 1;
223 
224  return py;
225 }
226 
227 
228 void POLY_GRID_PARTITION::build( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize )
229 {
230  m_outline = aPolyOutline;
231 
232  //if (orientation(m_outline) < 0)
233  // m_outline = m_outline.Reverse();
234 
235  m_bbox = m_outline.BBox();
236  m_gridSize = gridSize;
237 
238  m_outline.SetClosed( true );
239 
240  m_grid.reserve( gridSize * gridSize );
241 
242  for( int y = 0; y < gridSize; y++ )
243  {
244  for( int x = 0; x < gridSize; x++ )
245  {
246  m_grid.emplace_back();
247  }
248  }
249 
250  VECTOR2I ref_v( 0, 1 );
251  VECTOR2I ref_h( 0, 1 );
252 
253  m_flags.reserve( m_outline.SegmentCount() );
254 
255  std::unordered_map<SEG, int, segHash, segsEqual> edgeSet;
256 
257  for( int i = 0; i < m_outline.SegmentCount(); i++ )
258  {
259  SEG edge = m_outline.Segment( i );
260 
261  if( edgeSet.find( edge ) == edgeSet.end() )
262  {
263  edgeSet[edge] = 1;
264  }
265  else
266  {
267  edgeSet[edge]++;
268  }
269  }
270 
271  for( int i = 0; i < m_outline.SegmentCount(); i++ )
272  {
273  auto edge = m_outline.Segment( i );
274  auto dir = edge.B - edge.A;
275  int flags = 0;
276 
277 
278  if( dir.y == 0 )
279  {
280  flags = 0;
281  }
282  else if( edgeSet[edge] == 1 )
283  {
284  if( dir.Dot( ref_h ) < 0 )
285  {
286  flags |= LEAD_EDGE;
287  }
288  else if( dir.Dot( ref_h ) > 0 )
289  {
290  flags |= TRAIL_EDGE;
291  }
292  }
293 
294  m_flags.push_back( flags );
295 
296  if( edge.A.y == edge.B.y )
297  continue;
298 
299  std::set<int> indices;
300 
301  indices.insert( m_gridSize * poly2gridY( edge.A.y ) + poly2gridX( edge.A.x ) );
302  indices.insert( m_gridSize * poly2gridY( edge.B.y ) + poly2gridX( edge.B.x ) );
303 
304  if( edge.A.x > edge.B.x )
305  std::swap( edge.A, edge.B );
306 
307  dir = edge.B - edge.A;
308 
309  if( dir.x != 0 )
310  {
311  int gx0 = poly2gridX( edge.A.x );
312  int gx1 = poly2gridX( edge.B.x );
313 
314  for( int x = gx0; x <= gx1; x++ )
315  {
316  int px = grid2polyX( x );
317  int py = ( edge.A.y + rescale_trunc( dir.y, px - edge.A.x, dir.x ) );
318  int yy = poly2gridY( py );
319 
320  indices.insert( m_gridSize * yy + x );
321 
322  if( x > 0 )
323  indices.insert( m_gridSize * yy + x - 1 );
324  }
325  }
326 
327  if( edge.A.y > edge.B.y )
328  std::swap( edge.A, edge.B );
329 
330  dir = edge.B - edge.A;
331 
332  if( dir.y != 0 )
333  {
334  int gy0 = poly2gridY( edge.A.y );
335  int gy1 = poly2gridY( edge.B.y );
336 
337  for( int y = gy0; y <= gy1; y++ )
338  {
339  int py = grid2polyY( y );
340  int px = ( edge.A.x + rescale_trunc( dir.x, py - edge.A.y, dir.y ) );
341  int xx = poly2gridX( px );
342 
343  indices.insert( m_gridSize * y + xx );
344 
345  if( y > 0 )
346  indices.insert( m_gridSize * ( y - 1 ) + xx );
347  }
348  }
349 
350  for( auto idx : indices )
351  m_grid[idx].push_back( i );
352  }
353 }
354 
355 
356 void POLY_GRID_PARTITION::scanCell( SCAN_STATE& state, const EDGE_LIST& cell, const VECTOR2I& aP,
357  int cx, int cy ) const
358 {
359  int cx0 = grid2polyX( cx );
360  int cx1 = grid2polyX( cx + 1 );
361 
362 #ifdef TOM_EXTRA_VERBOSE
363  printf( "Scan %d %d\n", cx, cy );
364 #endif
365 
366  for( auto index : cell )
367  {
368  const SEG& edge = m_outline.CSegment( index );
369 
370 
371  if( m_flags[index] == 0 )
372  {
373  if( aP.y == edge.A.y
374  && inRange( edge.A.x, edge.B.x, aP.x ) ) // we belong to the outline
375  {
376  state.nearest = index;
377  state.dist_max = 0;
378  return;
379  }
380  else
381  {
382  continue;
383  }
384  }
385 
386  if( inRange( edge.A.y, edge.B.y, aP.y ) )
387  {
388 #ifdef TOM_EXTRA_VERBOSE
389  printf( "Test edge: %d [%d %d %d %d] p %d %d flags %d\n", index, edge.A.x, edge.A.y,
390  edge.B.x, edge.B.y, aP.x, aP.y );
391 #endif
392  int dist = 0;
393  int x0;
394  if( edge.A.y == aP.y )
395  {
396  x0 = edge.A.x;
397  }
398  else if( edge.B.y == aP.y )
399  {
400  x0 = edge.B.x;
401  }
402  else
403  {
404  x0 = edge.A.x
405  + rescale( ( edge.B.x - edge.A.x ), ( aP.y - edge.A.y ),
406  ( edge.B.y - edge.A.y ) );
407  }
408 
409 
410  dist = aP.x - x0;
411 
412 #ifdef TOM_EXTRA_VERBOSE
413  printf( " x0 %d dist %d [%s]\n", x0, dist,
414  x0 < cx0 || x0 > cx1 ? "outside" : "inside" );
415 #endif
416 
417  if( x0 < cx0 || x0 > cx1 )
418  {
419  continue;
420  }
421 
422 
423  if( dist == 0 )
424  {
425  if( state.nearest_prev < 0 || state.nearest != index )
426  {
427  state.dist_prev = state.dist_max;
428  state.nearest_prev = state.nearest;
429  }
430 
431  state.nearest = index;
432  state.dist_max = 0;
433  return;
434  }
435 
436  if( dist != 0 && std::abs( dist ) <= std::abs( state.dist_max ) )
437  {
438  if( state.nearest_prev < 0 || state.nearest != index )
439  {
440  state.dist_prev = state.dist_max;
441  state.nearest_prev = state.nearest;
442  }
443 
444  state.dist_max = dist;
445  state.nearest = index;
446  }
447  }
448  }
449 }
450 
451 
452 bool POLY_GRID_PARTITION::inRange( int v1, int v2, int x ) const
453 {
454  if( v1 < v2 )
455  {
456  return x >= v1 && x <= v2;
457  }
458 
459  return x >= v2 && x <= v1;
460 }
const VECTOR2I poly2grid(const VECTOR2I &p) const
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:76
void build(const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)
void scanCell(SCAN_STATE &state, const EDGE_LIST &cell, const VECTOR2I &aP, int cx, int cy) const
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
SHAPE_LINE_CHAIN m_outline
int ContainsPoint(const VECTOR2I &aP, int aClearance=0)
bool inRange(int v1, int v2, int x) const
int grid2polyY(int y) const
std::vector< int > m_flags
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int poly2gridX(int x) const
std::vector< EDGE_LIST > m_grid
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
POLY_GRID_PARTITION(const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)
coord_type GetWidth() const
Definition: box2.h:180
bool Contains(const Vec &aPoint) const
Definition: box2.h:134
VECTOR2I::extended_type ecoord
int containsPoint(const VECTOR2I &aP, bool debug=false) const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
std::vector< int > EDGE_LIST
int grid2polyX(int x) const
int SegmentCount() const
Return the number of segments in this line chain.
const Vec & GetPosition() const
Definition: box2.h:177
Definition: seg.h:40
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
const VECTOR2I grid2poly(const VECTOR2I &p) const
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
VECTOR2I A
Definition: seg.h:48
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:98
coord_type GetHeight() const
Definition: box2.h:181
int poly2gridY(int y) const
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const
bool checkClearance(const VECTOR2I &aP, int aClearance)
VECTOR2I B
Definition: seg.h:49