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