KiCad PCB EDA Suite
poly_grid_partition.h
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 
25 #ifndef __POLY_GRID_PARTITION_H
26 #define __POLY_GRID_PARTITION_H
27 
28 
29 #include <algorithm>
30 #include <functional>
31 #include <set>
32 #include <unordered_map>
33 #include <vector>
34 
35 #include <geometry/seg.h>
37 #include <geometry/shape_rect.h>
38 #include <math/util.h>
39 #include <math/vector2d.h>
40 
48 {
49 private:
51  {
52  LEAD_H = 1,
53  LEAD_V = 2,
54  TRAIL_H = 4,
55  TRAIL_V = 8
56  };
57 
58  using EDGE_LIST = std::vector<int>;
59 
60  template <class T>
61  inline void hash_combine( std::size_t& seed, const T& v )
62  {
63  std::hash<T> hasher;
64  seed ^= hasher( v ) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
65  }
66 
67  struct segsEqual
68  {
69  bool operator()( const SEG& a, const SEG& b ) const
70  {
71  return (a.A == b.A && a.B == b.B) || (a.A == b.B && a.B == b.A);
72  }
73  };
74 
75  struct segHash
76  {
77  std::size_t operator()( const SEG& a ) const
78  {
79  return a.A.x + a.B.x + a.A.y + a.B.y;
80  }
81  };
82 
83  const VECTOR2I grid2poly( const VECTOR2I& p ) const
84  {
85  int px = rescale( p.x, m_bbox.GetWidth(), m_gridSize ) + m_bbox.GetPosition().x;
86  int py = rescale( p.y, m_bbox.GetHeight(), m_gridSize ) + m_bbox.GetPosition().y; // (int) floor( (double) p.y / m_gridSize * (double) m_bbox.GetHeight() + m_bbox.GetPosition().y );
87 
88  return VECTOR2I( px, py );
89  }
90 
91  void stupid_test() const
92  {
93  for(int i = 0; i < 16;i++)
94  assert( poly2gridX(grid2polyX(i)) == i);
95  }
96 
97  int grid2polyX( int x ) const
98  {
99  return rescale( x, m_bbox.GetWidth(), m_gridSize ) + m_bbox.GetPosition().x;
100  }
101 
102  int grid2polyY( int y ) const
103  {
104  return rescale( y, m_bbox.GetHeight(), m_gridSize ) + m_bbox.GetPosition().y;
105  }
106 
107  const VECTOR2I poly2grid( const VECTOR2I& p ) const
108  {
109  int px = rescale( p.x - m_bbox.GetPosition().x, m_gridSize, m_bbox.GetWidth() );
110  int py = rescale( p.y - m_bbox.GetPosition().y, m_gridSize, m_bbox.GetHeight() );
111 
112  if( px < 0 )
113  px = 0;
114 
115  if( px >= m_gridSize )
116  px = m_gridSize - 1;
117 
118  if( py < 0 )
119  py = 0;
120 
121  if( py >= m_gridSize )
122  py = m_gridSize - 1;
123 
124  return VECTOR2I( px, py );
125  }
126 
127  int poly2gridX( int x ) const
128  {
129  int px = rescale( x - m_bbox.GetPosition().x, m_gridSize, m_bbox.GetWidth() );
130 
131  if( px < 0 )
132  px = 0;
133 
134  if( px >= m_gridSize )
135  px = m_gridSize - 1;
136 
137  return px;
138  }
139 
140  int poly2gridY( int y ) const
141  {
142  int py = rescale( y - m_bbox.GetPosition().y, m_gridSize, m_bbox.GetHeight() );
143 
144  if( py < 0 )
145  py = 0;
146 
147  if( py >= m_gridSize )
148  py = m_gridSize - 1;
149 
150  return py;
151  }
152 
153  void build( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize )
154  {
155  m_outline = aPolyOutline;
156 
157  //if (orientation(m_outline) < 0)
158  // m_outline = m_outline.Reverse();
159 
160  m_bbox = m_outline.BBox();
161  m_gridSize = gridSize;
162 
163  m_outline.SetClosed( true );
164 
165  m_grid.reserve( gridSize * gridSize );
166 
167  for( int y = 0; y < gridSize; y++ )
168  {
169  for( int x = 0; x < gridSize; x++ )
170  {
171  m_grid.emplace_back( );
172  }
173  }
174 
175  VECTOR2I ref_v( 0, 1 );
176  VECTOR2I ref_h( 0, 1 );
177 
178  m_flags.reserve( m_outline.SegmentCount() );
179 
180  std::unordered_map<SEG, int, segHash, segsEqual> edgeSet;
181 
182  for( int i = 0; i<m_outline.SegmentCount(); i++ )
183  {
184  SEG edge = m_outline.Segment( i );
185 
186  if( edgeSet.find( edge ) == edgeSet.end() )
187  {
188  edgeSet[edge] = 1;
189  }
190  else
191  {
192  edgeSet[edge]++;
193  }
194  }
195 
196  for( int i = 0; i<m_outline.SegmentCount(); i++ )
197  {
198  auto edge = m_outline.Segment( i );
199  auto dir = edge.B - edge.A;
200  int flags = 0;
201 
202 
203  if ( dir.y == 0 )
204  {
205  flags = 0;
206  }
207  else if( edgeSet[edge] == 1 )
208  {
209  if( dir.Dot( ref_h ) < 0 )
210  {
211  flags |= LEAD_H;
212  }
213  else if( dir.Dot( ref_h ) > 0 )
214  {
215  flags |= TRAIL_H;
216  }
217 
218  }
219 
220  m_flags.push_back( flags );
221 
222  if( edge.A.y == edge.B.y )
223  continue;
224 
225  std::set<int> indices;
226 
227  indices.insert( m_gridSize * poly2gridY( edge.A.y ) + poly2gridX( edge.A.x ) );
228  indices.insert( m_gridSize * poly2gridY( edge.B.y ) + poly2gridX( edge.B.x ) );
229 
230  if( edge.A.x > edge.B.x )
231  std::swap( edge.A, edge.B );
232 
233  dir = edge.B - edge.A;
234 
235  if( dir.x != 0 )
236  {
237  int gx0 = poly2gridX( edge.A.x );
238  int gx1 = poly2gridX( edge.B.x );
239 
240  for( int x = gx0; x <= gx1; x++ )
241  {
242  int px = grid2polyX( x );
243  int py = ( edge.A.y + rescale( dir.y, px - edge.A.x, dir.x ) );
244  int yy = poly2gridY( py );
245 
246  indices.insert( m_gridSize * yy + x );
247  if( x > 0 )
248  indices.insert( m_gridSize * yy + x - 1 );
249 
250  }
251  }
252 
253  if( edge.A.y > edge.B.y )
254  std::swap( edge.A, edge.B );
255 
256  dir = edge.B - edge.A;
257 
258  if( dir.y != 0 )
259  {
260  int gy0 = poly2gridY( edge.A.y );
261  int gy1 = poly2gridY( edge.B.y );
262 
263  for( int y = gy0; y <= gy1; y++ )
264  {
265  int py = grid2polyY( y );
266  int px = ( edge.A.x + rescale( dir.x, py - edge.A.y, dir.y ) );
267  int xx = poly2gridX( px );
268 
269  indices.insert( m_gridSize * y + xx );
270  if( y > 0 )
271  indices.insert( m_gridSize * (y - 1) + xx );
272  }
273  }
274 
275  for( auto idx : indices )
276  m_grid[idx].push_back( i );
277  }
278 
279  }
280 
281 
282  bool inRange( int v1, int v2, int x ) const
283  {
284  if( v1 < v2 )
285  {
286  return x >= v1 && x <= v2;
287  }
288 
289  return x >= v2 && x <= v1;
290  }
291 
292  struct SCAN_STATE
293  {
295  {
296  dist_prev = INT_MAX;
297  dist_max = INT_MAX;
298  nearest = -1;
299  nearest_prev = -1;
300  };
301 
302  int dist_prev;
303  int dist_max;
305  int nearest;
306  };
307 
308  void scanCell( SCAN_STATE& state, const EDGE_LIST& cell, const VECTOR2I& aP, int cx, int cy ) const
309  {
310  int cx0 = grid2polyX(cx);
311  int cx1 = grid2polyX(cx + 1);
312 
313  for( auto index : cell )
314  {
315  const SEG& edge = m_outline.CSegment( index );
316 
317 
318  if( m_flags[index] == 0 )
319  {
320  if ( aP.y == edge.A.y && inRange( edge.A.x, edge.B.x, aP.x ) ) // we belong to the outline
321  {
322  state.nearest = index;
323  state.dist_max = 0;
324  return;
325  } else {
326  continue;
327  }
328  }
329 
330  if( inRange( edge.A.y, edge.B.y, aP.y ) )
331  {
332  int dist = 0;
333  int x0;
334  if( edge.A.y == aP.y )
335  {
336  x0 = edge.A.x;
337  }
338  else if( edge.B.y == aP.y )
339  {
340  x0 = edge.B.x;
341  }
342  else
343  {
344  x0 = edge.A.x + rescale( ( edge.B.x - edge.A.x ), (aP.y - edge.A.y), (edge.B.y - edge.A.y ) );
345  }
346 
347  if( x0 < cx0 || x0 > cx1 )
348  {
349  continue;
350  }
351 
352  dist = aP.x - x0;
353 
354  if( dist == 0 )
355  {
356  if( state.nearest_prev < 0 || state.nearest != index )
357  {
358  state.dist_prev = state.dist_max;
359  state.nearest_prev = state.nearest;
360  }
361 
362  state.nearest = index;
363  state.dist_max = 0;
364  return;
365  }
366 
367  if( dist != 0 && std::abs( dist ) <= std::abs( state.dist_max ) )
368  {
369  if( state.nearest_prev < 0 || state.nearest != index )
370  {
371  state.dist_prev = state.dist_max;
372  state.nearest_prev = state.nearest;
373  }
374 
375  state.dist_max = dist;
376  state.nearest = index;
377  }
378  }
379  }
380  }
381 
382 public:
383 
384  POLY_GRID_PARTITION( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize )
385  {
386  build( aPolyOutline, gridSize );
387  }
388 
389  int containsPoint( const VECTOR2I& aP, bool debug = false ) const
390  {
391  const auto gridPoint = poly2grid( aP );
392 
393  if( !m_bbox.Contains( aP ) )
394  return 0;
395 
396  SCAN_STATE state;
397  const EDGE_LIST& cell = m_grid[ m_gridSize * gridPoint.y + gridPoint.x ];
398 
399  scanCell( state, cell, aP, gridPoint.x, gridPoint.y );
400 
401  if( state.nearest < 0 )
402  {
403  state = SCAN_STATE();
404 
405  for( int d = 1; d <= m_gridSize; d++ )
406  {
407  int xl = gridPoint.x - d;
408  int xh = gridPoint.x + d;
409 
410  if( xl >= 0 )
411  {
412  const EDGE_LIST& cell2 = m_grid[ m_gridSize * gridPoint.y + xl ];
413  scanCell( state, cell2, aP, xl, gridPoint.y );
414 
415  if( state.nearest >= 0 )
416  break;
417  }
418 
419  if( xh < m_gridSize )
420  {
421  const EDGE_LIST& cell2 = m_grid[ m_gridSize * gridPoint.y + xh ];
422  scanCell( state, cell2, aP, xh, gridPoint.y );
423 
424  if( state.nearest >= 0 )
425  break;
426  }
427  }
428  }
429 
430  if( state.nearest < 0 )
431  return 0;
432 
433  if( state.dist_max == 0 )
434  return 1;
435 
436  // special case for diagonal 'slits', e.g. two segments that partially overlap each other.
437  if( state.nearest_prev >= 0 && state.dist_max == state.dist_prev )
438  {
439  int d = std::abs( state.nearest_prev - state.nearest );
440 
441  if( (d == 1) && ( (m_flags[state.nearest_prev] & m_flags[state.nearest]) == 0 ) )
442  {
443  return 0;
444  }
445  }
446 
447  if( state.dist_max > 0 )
448  {
449  return m_flags[state.nearest] & LEAD_H ? 1 : 0;
450  }
451  else
452  {
453  return m_flags[state.nearest] & TRAIL_H ? 1 : 0;
454  }
455  }
456 
457  bool checkClearance( const VECTOR2I& aP, int aClearance )
458  {
459  int gx0 = poly2gridX( aP.x - aClearance - 1);
460  int gx1 = poly2gridX( aP.x + aClearance + 1);
461  int gy0 = poly2gridY( aP.y - aClearance - 1);
462  int gy1 = poly2gridY( aP.y + aClearance + 1);
463 
465 
466  ecoord dist = (ecoord) aClearance * aClearance;
467 
468  for ( int gx = gx0; gx <= gx1; gx++ )
469  {
470  for ( int gy = gy0; gy <= gy1; gy++ )
471  {
472  const auto& cell = m_grid [ m_gridSize * gy + gx];
473  for ( auto index : cell )
474  {
475  const auto& seg = m_outline.Segment( index );
476 
477  if ( seg.SquaredDistance(aP) <= dist )
478  return true;
479 
480  }
481  }
482 
483  }
484  return false;
485  }
486 
487 
488 
489  int ContainsPoint( const VECTOR2I& aP, int aClearance = 0 ) // const
490  {
491  if( containsPoint(aP) )
492  return 1;
493 
494  if( aClearance > 0 )
495  return checkClearance ( aP, aClearance );
496 
497  return 0;
498  }
499 
500  const BOX2I& BBox() const
501  {
502  return m_bbox;
503  }
504 
505 private:
509  std::vector<int> m_flags;
510  std::vector<EDGE_LIST> m_grid;
511 };
512 
513 #endif
const VECTOR2I poly2grid(const VECTOR2I &p) const
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:77
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
SHAPE_LINE_CHAIN m_outline
int ContainsPoint(const VECTOR2I &aP, int aClearance=0)
std::size_t operator()(const SEG &a) const
bool inRange(int v1, int v2, int x) const
int grid2polyY(int y) const
T
enum T contains all this lexer's tokens.
std::vector< int > m_flags
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
int poly2gridX(int x) const
std::vector< EDGE_LIST > m_grid
void SetClosed(bool aClosed)
Function SetClosed()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
const BOX2I & BBox() const
POLY_GRID_PARTITION(const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)
coord_type GetWidth() const
Definition: box2.h:197
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:151
VECTOR2I::extended_type ecoord
int containsPoint(const VECTOR2I &aP, bool debug=false) const
bool operator()(const SEG &a, const SEG &b) const
std::vector< int > EDGE_LIST
int grid2polyX(int x) const
int SegmentCount() const
Function SegmentCount()
const Vec & GetPosition() const
Definition: box2.h:194
Definition: seg.h:39
void hash_combine(std::size_t &seed, const T &v)
SEG Segment(int aIndex)
Function Segment()
const VECTOR2I grid2poly(const VECTOR2I &p) const
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
coord_type GetHeight() const
Definition: box2.h:198
int poly2gridY(int y) const
POLY_GRID_PARTITION.
bool checkClearance(const VECTOR2I &aP, int aClearance)
VECTOR2I B
Definition: seg.h:48