KiCad PCB EDA Suite
POLY_GRID_PARTITION Class Reference

Class POLY_GRID_PARTITION. More...

#include <poly_grid_partition.h>

Classes

struct  SCAN_STATE
 
struct  segHash
 
struct  segsEqual
 

Public Member Functions

 POLY_GRID_PARTITION (const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)
 
int containsPoint (const VECTOR2I &aP, bool debug=false) const
 
bool checkClearance (const VECTOR2I &aP, int aClearance)
 
int ContainsPoint (const VECTOR2I &aP, int aClearance=0)
 
const BOX2IBBox () const
 

Private Types

enum  HASH_FLAG { LEAD_H = 1, LEAD_V = 2, TRAIL_H = 4, TRAIL_V = 8 }
 
using EDGE_LIST = std::vector< int >
 

Private Member Functions

template<class T >
void hash_combine (std::size_t &seed, const T &v)
 
const VECTOR2I grid2poly (const VECTOR2I &p) const
 
void stupid_test () const
 
int grid2polyX (int x) const
 
int grid2polyY (int y) const
 
const VECTOR2I poly2grid (const VECTOR2I &p) const
 
int poly2gridX (int x) const
 
int poly2gridY (int y) const
 
void build (const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)
 
bool inRange (int v1, int v2, int x) const
 
void scanCell (SCAN_STATE &state, const EDGE_LIST &cell, const VECTOR2I &aP, int cx, int cy) const
 

Private Attributes

int m_gridSize
 
SHAPE_LINE_CHAIN m_outline
 
BOX2I m_bbox
 
std::vector< int > m_flags
 
std::vector< EDGE_LISTm_grid
 

Detailed Description

Class POLY_GRID_PARTITION.

Provides a fast test for point inside polygon by splitting the edges of the polygon into a rectangular grid.

Definition at line 43 of file poly_grid_partition.h.

Member Typedef Documentation

using POLY_GRID_PARTITION::EDGE_LIST = std::vector<int>
private

Definition at line 54 of file poly_grid_partition.h.

Member Enumeration Documentation

Enumerator
LEAD_H 
LEAD_V 
TRAIL_H 
TRAIL_V 

Definition at line 46 of file poly_grid_partition.h.

Constructor & Destructor Documentation

POLY_GRID_PARTITION::POLY_GRID_PARTITION ( const SHAPE_LINE_CHAIN aPolyOutline,
int  gridSize 
)
inline

Definition at line 380 of file poly_grid_partition.h.

References build().

381  {
382  build( aPolyOutline, gridSize );
383  }
void build(const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)

Member Function Documentation

const BOX2I& POLY_GRID_PARTITION::BBox ( ) const
inline

Definition at line 496 of file poly_grid_partition.h.

References m_bbox.

497  {
498  return m_bbox;
499  }
void POLY_GRID_PARTITION::build ( const SHAPE_LINE_CHAIN aPolyOutline,
int  gridSize 
)
inlineprivate

Definition at line 149 of file poly_grid_partition.h.

References SEG::B, SHAPE_LINE_CHAIN::BBox(), SHAPE_LINE_CHAIN::CSegment(), grid2polyX(), grid2polyY(), i, LEAD_H, m_bbox, m_flags, m_grid, m_gridSize, m_outline, poly2gridX(), poly2gridY(), rescale(), SHAPE_LINE_CHAIN::SegmentCount(), SHAPE_LINE_CHAIN::SetClosed(), and TRAIL_H.

Referenced by POLY_GRID_PARTITION().

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  }
SHAPE_LINE_CHAIN m_outline
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
int poly2gridX(int x) const
int grid2polyX(int x) const
std::vector< int > m_flags
std::vector< EDGE_LIST > m_grid
const SEG CSegment(int aIndex) const
Function CSegment()
void SetClosed(bool aClosed)
Function SetClosed()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
int poly2gridY(int y) const
std::vector< int > EDGE_LIST
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
Definition: seg.h:36
size_t i
Definition: json11.cpp:597
VECTOR2I A
Definition: seg.h:46
int grid2polyY(int y) const
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:47
bool POLY_GRID_PARTITION::checkClearance ( const VECTOR2I aP,
int  aClearance 
)
inline

Definition at line 453 of file poly_grid_partition.h.

References SHAPE_LINE_CHAIN::CSegment(), dist, m_grid, m_gridSize, m_outline, poly2gridX(), poly2gridY(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by ContainsPoint().

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  }
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:77
SHAPE_LINE_CHAIN m_outline
static const int dist[10][10]
Definition: ar_matrix.cpp:320
int poly2gridX(int x) const
std::vector< EDGE_LIST > m_grid
const SEG CSegment(int aIndex) const
Function CSegment()
VECTOR2I::extended_type ecoord
int poly2gridY(int y) const
int POLY_GRID_PARTITION::containsPoint ( const VECTOR2I aP,
bool  debug = false 
) const
inline

Definition at line 385 of file poly_grid_partition.h.

References abs, BOX2< Vec >::Contains(), POLY_GRID_PARTITION::SCAN_STATE::dist_max, POLY_GRID_PARTITION::SCAN_STATE::dist_prev, LEAD_H, m_bbox, m_flags, m_grid, m_gridSize, POLY_GRID_PARTITION::SCAN_STATE::nearest, POLY_GRID_PARTITION::SCAN_STATE::nearest_prev, poly2grid(), scanCell(), TRAIL_H, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by ContainsPoint().

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  }
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:149
std::vector< int > m_flags
#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
std::vector< int > EDGE_LIST
int POLY_GRID_PARTITION::ContainsPoint ( const VECTOR2I aP,
int  aClearance = 0 
)
inline

Definition at line 485 of file poly_grid_partition.h.

References checkClearance(), and containsPoint().

486  {
487  if( containsPoint(aP) )
488  return 1;
489 
490  if( aClearance > 0 )
491  return checkClearance ( aP, aClearance );
492 
493  return 0;
494  }
int containsPoint(const VECTOR2I &aP, bool debug=false) const
bool checkClearance(const VECTOR2I &aP, int aClearance)
const VECTOR2I POLY_GRID_PARTITION::grid2poly ( const VECTOR2I p) const
inlineprivate

Definition at line 79 of file poly_grid_partition.h.

References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetPosition(), BOX2< Vec >::GetWidth(), m_bbox, m_gridSize, rescale(), VECTOR2< T >::x, and VECTOR2< T >::y.

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  }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
coord_type GetWidth() const
Definition: box2.h:195
const Vec & GetPosition() const
Definition: box2.h:192
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
coord_type GetHeight() const
Definition: box2.h:196
int POLY_GRID_PARTITION::grid2polyX ( int  x) const
inlineprivate

Definition at line 93 of file poly_grid_partition.h.

References BOX2< Vec >::GetPosition(), BOX2< Vec >::GetWidth(), m_bbox, m_gridSize, rescale(), and VECTOR2< T >::x.

Referenced by build(), scanCell(), and stupid_test().

94  {
95  return rescale( x, m_bbox.GetWidth(), m_gridSize ) + m_bbox.GetPosition().x;
96  }
coord_type GetWidth() const
Definition: box2.h:195
const Vec & GetPosition() const
Definition: box2.h:192
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
int POLY_GRID_PARTITION::grid2polyY ( int  y) const
inlineprivate

Definition at line 98 of file poly_grid_partition.h.

References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetPosition(), m_bbox, m_gridSize, rescale(), and VECTOR2< T >::y.

Referenced by build().

99  {
100  return rescale( y, m_bbox.GetHeight(), m_gridSize ) + m_bbox.GetPosition().y;
101  }
const Vec & GetPosition() const
Definition: box2.h:192
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
coord_type GetHeight() const
Definition: box2.h:196
template<class T >
void POLY_GRID_PARTITION::hash_combine ( std::size_t &  seed,
const T &  v 
)
inlineprivate

Definition at line 57 of file poly_grid_partition.h.

58  {
59  std::hash<T> hasher;
60  seed ^= hasher( v ) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
61  }
bool POLY_GRID_PARTITION::inRange ( int  v1,
int  v2,
int  x 
) const
inlineprivate

Definition at line 278 of file poly_grid_partition.h.

Referenced by scanCell().

279  {
280  if( v1 < v2 )
281  {
282  return x >= v1 && x <= v2;
283  }
284 
285  return x >= v2 && x <= v1;
286  }
const VECTOR2I POLY_GRID_PARTITION::poly2grid ( const VECTOR2I p) const
inlineprivate

Definition at line 103 of file poly_grid_partition.h.

References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetPosition(), BOX2< Vec >::GetWidth(), m_bbox, m_gridSize, rescale(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by containsPoint().

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  }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
coord_type GetWidth() const
Definition: box2.h:195
const Vec & GetPosition() const
Definition: box2.h:192
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
coord_type GetHeight() const
Definition: box2.h:196
int POLY_GRID_PARTITION::poly2gridX ( int  x) const
inlineprivate

Definition at line 123 of file poly_grid_partition.h.

References BOX2< Vec >::GetPosition(), BOX2< Vec >::GetWidth(), m_bbox, m_gridSize, rescale(), and VECTOR2< T >::x.

Referenced by build(), checkClearance(), and stupid_test().

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  }
coord_type GetWidth() const
Definition: box2.h:195
const Vec & GetPosition() const
Definition: box2.h:192
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
int POLY_GRID_PARTITION::poly2gridY ( int  y) const
inlineprivate

Definition at line 136 of file poly_grid_partition.h.

References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetPosition(), m_bbox, m_gridSize, rescale(), and VECTOR2< T >::y.

Referenced by build(), and checkClearance().

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  }
const Vec & GetPosition() const
Definition: box2.h:192
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
coord_type GetHeight() const
Definition: box2.h:196
void POLY_GRID_PARTITION::scanCell ( SCAN_STATE state,
const EDGE_LIST cell,
const VECTOR2I aP,
int  cx,
int  cy 
) const
inlineprivate

Definition at line 304 of file poly_grid_partition.h.

References SEG::A, abs, SEG::B, SHAPE_LINE_CHAIN::CSegment(), dist, POLY_GRID_PARTITION::SCAN_STATE::dist_max, POLY_GRID_PARTITION::SCAN_STATE::dist_prev, grid2polyX(), inRange(), m_flags, m_outline, POLY_GRID_PARTITION::SCAN_STATE::nearest, POLY_GRID_PARTITION::SCAN_STATE::nearest_prev, rescale(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by containsPoint().

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  }
SHAPE_LINE_CHAIN m_outline
static const int dist[10][10]
Definition: ar_matrix.cpp:320
int grid2polyX(int x) const
std::vector< int > m_flags
#define abs(a)
Definition: auxiliary.h:84
const SEG CSegment(int aIndex) const
Function CSegment()
bool inRange(int v1, int v2, int x) const
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
Definition: seg.h:36
VECTOR2I A
Definition: seg.h:46
VECTOR2I B
Definition: seg.h:47
void POLY_GRID_PARTITION::stupid_test ( ) const
inlineprivate

Definition at line 87 of file poly_grid_partition.h.

References grid2polyX(), i, and poly2gridX().

88  {
89  for(int i = 0; i < 16;i++)
90  assert( poly2gridX(grid2polyX(i)) == i);
91  }
int poly2gridX(int x) const
int grid2polyX(int x) const
size_t i
Definition: json11.cpp:597

Member Data Documentation

BOX2I POLY_GRID_PARTITION::m_bbox
private
std::vector<int> POLY_GRID_PARTITION::m_flags
private

Definition at line 505 of file poly_grid_partition.h.

Referenced by build(), containsPoint(), and scanCell().

std::vector<EDGE_LIST> POLY_GRID_PARTITION::m_grid
private

Definition at line 506 of file poly_grid_partition.h.

Referenced by build(), checkClearance(), and containsPoint().

int POLY_GRID_PARTITION::m_gridSize
private
SHAPE_LINE_CHAIN POLY_GRID_PARTITION::m_outline
private

Definition at line 503 of file poly_grid_partition.h.

Referenced by build(), checkClearance(), and scanCell().


The documentation for this class was generated from the following file: