Horizon
poly_grid_partition.h
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>
29 #include <geometry/shape_line_chain.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:
46  enum HASH_FLAG
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  std::size_t seed = 0;
76 
77  return a.A.x + a.B.x + a.A.y + a.B.y;
78 
79  return seed;
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.push_back( EDGE_LIST() );
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.CSegment( 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.CSegment( i );
199  auto dir = edge.B - edge.A;
200  int flags = 0;
201 
202  if( edgeSet[edge] == 1 )
203  {
204  if( dir.Dot( ref_h ) < 0 )
205  {
206  flags |= LEAD_H;
207  }
208  else if( dir.Dot( ref_h ) > 0 )
209  {
210  flags |= TRAIL_H;
211  }
212 
213  }
214 
215  m_flags.push_back( flags );
216 
217  std::set<int> indices;
218 
219  indices.insert( m_gridSize * poly2gridY( edge.A.y ) + poly2gridX( edge.A.x ) );
220  indices.insert( m_gridSize * poly2gridY( edge.B.y ) + poly2gridX( edge.B.x ) );
221 
222  if( edge.A.x > edge.B.x )
223  std::swap( edge.A, edge.B );
224 
225  dir = edge.B - edge.A;
226 
227  if( dir.x != 0 )
228  {
229  int gx0 = poly2gridX( edge.A.x );
230  int gx1 = poly2gridX( edge.B.x );
231 
232  for( int x = gx0; x <= gx1; x++ )
233  {
234  int px = grid2polyX( x );
235  int py = ( edge.A.y + rescale( dir.y, px - edge.A.x, dir.x ) );
236  int yy = poly2gridY( py );
237 
238  indices.insert( m_gridSize * yy + x );
239  if( x > 0 )
240  indices.insert( m_gridSize * yy + x - 1 );
241 
242  }
243  }
244 
245  if( edge.A.y > edge.B.y )
246  std::swap( edge.A, edge.B );
247 
248  dir = edge.B - edge.A;
249 
250  if( dir.y != 0 )
251  {
252  int gy0 = poly2gridY( edge.A.y );
253  int gy1 = poly2gridY( edge.B.y );
254 
255  for( int y = gy0; y <= gy1; y++ )
256  {
257  int py = grid2polyY( y );
258  int px = ( edge.A.x + rescale( dir.x, py - edge.A.y, dir.y ) );
259  int xx = poly2gridX( px );
260 
261  indices.insert( m_gridSize * y + xx );
262  if( y > 0 )
263  indices.insert( m_gridSize * (y - 1) + xx );
264  }
265  }
266 
267  for( auto idx : indices )
268  m_grid[idx].push_back( i );
269  }
270 
271  }
272 
273 
274  bool inRange( int v1, int v2, int x ) const
275  {
276  if( v1 < v2 )
277  {
278  return x >= v1 && x <= v2;
279  }
280 
281  return x >= v2 && x <= v1;
282  }
283 
284  struct SCAN_STATE
285  {
286  SCAN_STATE()
287  {
288  dist_max = INT_MAX;
289  nearest = -1;
290  nearest_prev = -1;
291  };
292 
293  int dist_prev;
294  int dist_max;
295  int nearest_prev;
296  int nearest;
297  };
298 
299  void scanCell( SCAN_STATE& state, const EDGE_LIST& cell, const VECTOR2I& aP, int cx, int cy ) const
300  {
301  int cx0 = grid2polyX(cx);
302  int cx1 = grid2polyX(cx + 1);
303 
304  for( auto index : cell )
305  {
306  const SEG& edge = m_outline.CSegment( index );
307 
308 
309  if( m_flags[index] == 0 )
310  {
311  if ( aP.y == edge.A.y && inRange( edge.A.x, edge.B.x, aP.x ) ) // we belong to the outline
312  {
313  state.nearest = index;
314  state.dist_max = 0;
315  return;
316  } else {
317  continue;
318  }
319  }
320 
321  if( inRange( edge.A.y, edge.B.y, aP.y ) )
322  {
323  int dist = 0;
324  int x0;
325  if( edge.A.y == aP.y )
326  {
327  x0 = edge.A.x;
328  }
329  else if( edge.B.y == aP.y )
330  {
331  x0 = edge.B.x;
332  }
333  else
334  {
335  x0 = edge.A.x + rescale( ( edge.B.x - edge.A.x ), (aP.y - edge.A.y), (edge.B.y - edge.A.y ) );
336  }
337 
338  if( x0 < cx0 || x0 > cx1 )
339  {
340  continue;
341  }
342 
343  dist = aP.x - x0;
344 
345  if( dist == 0 )
346  {
347  if( state.nearest_prev < 0 || state.nearest != index )
348  {
349  state.dist_prev = state.dist_max;
350  state.nearest_prev = state.nearest;
351  }
352 
353  state.nearest = index;
354  state.dist_max = 0;
355  return;
356  }
357 
358  if( dist != 0 && std::abs( dist ) <= std::abs( state.dist_max ) )
359  {
360  if( state.nearest_prev < 0 || state.nearest != index )
361  {
362  state.dist_prev = state.dist_max;
363  state.nearest_prev = state.nearest;
364  }
365 
366  state.dist_max = dist;
367  state.nearest = index;
368  }
369  }
370  }
371  }
372 
373 public:
374 
375  POLY_GRID_PARTITION( const SHAPE_LINE_CHAIN& aPolyOutline, int gridSize )
376  {
377  build( aPolyOutline, gridSize );
378  }
379 
380  int containsPoint( const VECTOR2I& aP ) // const
381  {
382  const auto gridPoint = poly2grid( aP );
383 
384  if( !m_bbox.Contains( aP ) )
385  return false;
386 
387  SCAN_STATE state;
388  const EDGE_LIST& cell = m_grid[ m_gridSize * gridPoint.y + gridPoint.x ];
389 
390  scanCell( state, cell, aP, gridPoint.x, gridPoint.y );
391 
392  if( state.nearest < 0 )
393  {
394  state = SCAN_STATE();
395 
396  for( int d = 1; d <= m_gridSize; d++ )
397  {
398  int xl = gridPoint.x - d;
399  int xh = gridPoint.x + d;
400 
401  if( xl >= 0 )
402  {
403  const EDGE_LIST& cell2 = m_grid[ m_gridSize * gridPoint.y + xl ];
404  scanCell( state, cell2, aP, xl, gridPoint.y );
405 
406  if( state.nearest >= 0 )
407  break;
408  }
409 
410  if( xh < m_gridSize )
411  {
412  const EDGE_LIST& cell2 = m_grid[ m_gridSize * gridPoint.y + xh ];
413  scanCell( state, cell2, aP, xh, gridPoint.y );
414 
415  if( state.nearest >= 0 )
416  break;
417  }
418  }
419  }
420 
421  if( state.nearest < 0 )
422  return 0;
423 
424  if( state.dist_max == 0 )
425  return 1;
426 
427  if( state.nearest_prev >= 0 && state.dist_max == state.dist_prev )
428  {
429  int d = std::abs( state.nearest_prev - state.nearest );
430 
431  if( (d == 1) && ( (m_flags[state.nearest_prev] & m_flags[state.nearest]) == 0 ) )
432  {
433  return 0;
434  }
435  else if( d > 1 )
436  {
437  return 1;
438  }
439  }
440 
441  if( state.dist_max > 0 )
442  {
443  return m_flags[state.nearest] & LEAD_H ? 1 : 0;
444  }
445  else
446  {
447  return m_flags[state.nearest] & TRAIL_H ? 1 : 0;
448  }
449  }
450 
451  bool checkClearance( const VECTOR2I& aP, int aClearance )
452  {
453  int gx0 = poly2gridX( aP.x - aClearance - 1);
454  int gx1 = poly2gridX( aP.x + aClearance + 1);
455  int gy0 = poly2gridY( aP.y - aClearance - 1);
456  int gy1 = poly2gridY( aP.y + aClearance + 1);
457 
458  using ecoord = VECTOR2I::extended_type;
459 
460  ecoord dist = (ecoord) aClearance * aClearance;
461 
462  for ( int gx = gx0; gx <= gx1; gx++ )
463  {
464  for ( int gy = gy0; gy <= gy1; gy++ )
465  {
466  const auto& cell = m_grid [ m_gridSize * gy + gx];
467  for ( auto index : cell )
468  {
469  const auto& seg = m_outline.CSegment(index);
470 
471  if ( seg.SquaredDistance(aP) <= dist )
472  return true;
473 
474  }
475  }
476 
477  }
478  return false;
479  }
480 
481 
482 
483  int ContainsPoint( const VECTOR2I& aP, int aClearance = 0 ) // const
484  {
485  if( containsPoint(aP) )
486  return 1;
487 
488  if( aClearance > 0 )
489  return checkClearance ( aP, aClearance );
490 
491  return 0;
492  }
493 
494  const BOX2I& BBox() const
495  {
496  return m_bbox;
497  }
498 
499 private:
500  int m_gridSize;
501  SHAPE_LINE_CHAIN m_outline;
502  BOX2I m_bbox;
503  std::vector<int> m_flags;
504  std::vector<EDGE_LIST> m_grid;
505 };
506 
507 #endif
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_line_chain.h:264
Definition: seg.h:37
Class SHAPE_LINE_CHAIN.
Definition: shape_line_chain.h:47
Class POLY_GRID_PARTITION.
Definition: poly_grid_partition.h:43