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