KiCad PCB EDA Suite
POLY_GRID_PARTITION Class Reference

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

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 47 of file poly_grid_partition.h.

Member Typedef Documentation

◆ EDGE_LIST

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

Definition at line 58 of file poly_grid_partition.h.

Member Enumeration Documentation

◆ HASH_FLAG

Enumerator
LEAD_H 
LEAD_V 
TRAIL_H 
TRAIL_V 

Definition at line 50 of file poly_grid_partition.h.

Constructor & Destructor Documentation

◆ POLY_GRID_PARTITION()

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

Definition at line 384 of file poly_grid_partition.h.

385  {
386  build( aPolyOutline, gridSize );
387  }
void build(const SHAPE_LINE_CHAIN &aPolyOutline, int gridSize)

References build().

Member Function Documentation

◆ BBox()

const BOX2I& POLY_GRID_PARTITION::BBox ( ) const
inline

Definition at line 500 of file poly_grid_partition.h.

501  {
502  return m_bbox;
503  }

References m_bbox.

◆ build()

void POLY_GRID_PARTITION::build ( const SHAPE_LINE_CHAIN aPolyOutline,
int  gridSize 
)
inlineprivate

Definition at line 153 of file poly_grid_partition.h.

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  }
SHAPE_LINE_CHAIN m_outline
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
int grid2polyY(int y) const
std::vector< int > m_flags
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()
int grid2polyX(int x) const
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:39
SEG Segment(int aIndex)
Function Segment()
VECTOR2I A
Definition: seg.h:47
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
int poly2gridY(int y) const
VECTOR2I B
Definition: seg.h:48

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

Referenced by POLY_GRID_PARTITION().

◆ checkClearance()

bool POLY_GRID_PARTITION::checkClearance ( const VECTOR2I aP,
int  aClearance 
)
inline

Definition at line 457 of file poly_grid_partition.h.

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  }
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:77
SHAPE_LINE_CHAIN m_outline
int poly2gridX(int x) const
std::vector< EDGE_LIST > m_grid
double dist(const double ax, const double ay, const double bx, const double by)
Definition: delauney.h:168
VECTOR2I::extended_type ecoord
SEG Segment(int aIndex)
Function Segment()
int poly2gridY(int y) const

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

Referenced by ContainsPoint().

◆ containsPoint()

int POLY_GRID_PARTITION::containsPoint ( const VECTOR2I aP,
bool  debug = false 
) const
inline

Definition at line 389 of file poly_grid_partition.h.

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  }
const VECTOR2I poly2grid(const VECTOR2I &p) const
void scanCell(SCAN_STATE &state, const EDGE_LIST &cell, const VECTOR2I &aP, int cx, int cy) const
std::vector< int > m_flags
std::vector< EDGE_LIST > m_grid
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:150
std::vector< int > EDGE_LIST

References 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().

◆ ContainsPoint()

int POLY_GRID_PARTITION::ContainsPoint ( const VECTOR2I aP,
int  aClearance = 0 
)
inline

Definition at line 489 of file poly_grid_partition.h.

490  {
491  if( containsPoint(aP) )
492  return 1;
493 
494  if( aClearance > 0 )
495  return checkClearance ( aP, aClearance );
496 
497  return 0;
498  }
int containsPoint(const VECTOR2I &aP, bool debug=false) const
bool checkClearance(const VECTOR2I &aP, int aClearance)

References checkClearance(), and containsPoint().

◆ grid2poly()

const VECTOR2I POLY_GRID_PARTITION::grid2poly ( const VECTOR2I p) const
inlineprivate

Definition at line 83 of file poly_grid_partition.h.

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  }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
coord_type GetWidth() const
Definition: box2.h:196
const Vec & GetPosition() const
Definition: box2.h:193
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
coord_type GetHeight() const
Definition: box2.h:197

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

◆ grid2polyX()

int POLY_GRID_PARTITION::grid2polyX ( int  x) const
inlineprivate

Definition at line 97 of file poly_grid_partition.h.

98  {
99  return rescale( x, m_bbox.GetWidth(), m_gridSize ) + m_bbox.GetPosition().x;
100  }
coord_type GetWidth() const
Definition: box2.h:196
const Vec & GetPosition() const
Definition: box2.h:193
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95

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

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

◆ grid2polyY()

int POLY_GRID_PARTITION::grid2polyY ( int  y) const
inlineprivate

Definition at line 102 of file poly_grid_partition.h.

103  {
104  return rescale( y, m_bbox.GetHeight(), m_gridSize ) + m_bbox.GetPosition().y;
105  }
const Vec & GetPosition() const
Definition: box2.h:193
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
coord_type GetHeight() const
Definition: box2.h:197

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

Referenced by build().

◆ hash_combine()

template<class T >
void POLY_GRID_PARTITION::hash_combine ( std::size_t &  seed,
const T &  v 
)
inlineprivate

Definition at line 61 of file poly_grid_partition.h.

62  {
63  std::hash<T> hasher;
64  seed ^= hasher( v ) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
65  }

◆ inRange()

bool POLY_GRID_PARTITION::inRange ( int  v1,
int  v2,
int  x 
) const
inlineprivate

Definition at line 282 of file poly_grid_partition.h.

283  {
284  if( v1 < v2 )
285  {
286  return x >= v1 && x <= v2;
287  }
288 
289  return x >= v2 && x <= v1;
290  }

Referenced by scanCell().

◆ poly2grid()

const VECTOR2I POLY_GRID_PARTITION::poly2grid ( const VECTOR2I p) const
inlineprivate

Definition at line 107 of file poly_grid_partition.h.

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  }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
coord_type GetWidth() const
Definition: box2.h:196
const Vec & GetPosition() const
Definition: box2.h:193
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
coord_type GetHeight() const
Definition: box2.h:197

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().

◆ poly2gridX()

int POLY_GRID_PARTITION::poly2gridX ( int  x) const
inlineprivate

Definition at line 127 of file poly_grid_partition.h.

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  }
coord_type GetWidth() const
Definition: box2.h:196
const Vec & GetPosition() const
Definition: box2.h:193
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95

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

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

◆ poly2gridY()

int POLY_GRID_PARTITION::poly2gridY ( int  y) const
inlineprivate

Definition at line 140 of file poly_grid_partition.h.

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  }
const Vec & GetPosition() const
Definition: box2.h:193
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
coord_type GetHeight() const
Definition: box2.h:197

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

Referenced by build(), and checkClearance().

◆ scanCell()

void POLY_GRID_PARTITION::scanCell ( SCAN_STATE state,
const EDGE_LIST cell,
const VECTOR2I aP,
int  cx,
int  cy 
) const
inlineprivate

Definition at line 308 of file poly_grid_partition.h.

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  }
SHAPE_LINE_CHAIN m_outline
bool inRange(int v1, int v2, int x) const
std::vector< int > m_flags
double dist(const double ax, const double ay, const double bx, const double by)
Definition: delauney.h:168
int grid2polyX(int x) const
Definition: seg.h:39
const SEG CSegment(int aIndex) const
Function CSegment()
VECTOR2I A
Definition: seg.h:47
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
VECTOR2I B
Definition: seg.h:48

References SEG::A, 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().

◆ stupid_test()

void POLY_GRID_PARTITION::stupid_test ( ) const
inlineprivate

Definition at line 91 of file poly_grid_partition.h.

92  {
93  for(int i = 0; i < 16;i++)
94  assert( poly2gridX(grid2polyX(i)) == i);
95  }
int poly2gridX(int x) const
int grid2polyX(int x) const

References grid2polyX(), and poly2gridX().

Member Data Documentation

◆ m_bbox

BOX2I POLY_GRID_PARTITION::m_bbox
private

◆ m_flags

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

Definition at line 509 of file poly_grid_partition.h.

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

◆ m_grid

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

Definition at line 510 of file poly_grid_partition.h.

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

◆ m_gridSize

int POLY_GRID_PARTITION::m_gridSize
private

◆ m_outline

SHAPE_LINE_CHAIN POLY_GRID_PARTITION::m_outline
private

Definition at line 507 of file poly_grid_partition.h.

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


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