KiCad PCB EDA Suite
POLY_GRID_PARTITION Class Reference

Provide a fast test for point inside polygon. 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, int aClearance=0)
 
const BOX2IBBox () const
 

Private Types

enum  HASH_FLAG { LEAD_EDGE = 1, TRAIL_EDGE = 2 }
 
using EDGE_LIST = std::vector< int >
 

Private Member Functions

template<class T >
void hash_combine (std::size_t &seed, const T &v)
 
int containsPoint (const VECTOR2I &aP, bool debug=false) const
 
bool checkClearance (const VECTOR2I &aP, int aClearance)
 
int rescale_trunc (int aNumerator, int aValue, int aDenominator) const
 
const VECTOR2I grid2poly (const VECTOR2I &p) 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

Provide a fast test for point inside polygon.

Takes a large poly and splits it into a grid of rectangular cells, forming a spatial hash table. Each cell contains only the edges that 'touch it' (any point of the edge belongs to the cell). Edges can be marked as leading or trailing. Leading edge indicates that space to the left of it (x-wise) is outside the polygon. Trailing edge, conversely, means space to the right is outside the polygon.

The point inside check for point (p) works as follows:

  • determine the cell coordinates of (p) (poly2grid)
  • find the matching grid cell ( O(0), if the cell coordinates are outside the range, the point is not in the polygon ).
  • if the cell contains edges, find the first edge to the left or right of the point, whichever comes first.
  • if the edge to the left is the 'lead edge', the point is inside. if it's a trailing edge, the point is outside.
  • idem for the edge to the right of (p), just reverse the edge types.
  • if the cell doesn't contain any edges, scan horizontal cells to the left and right (switching sides with each iteration) until an edge if found.
Note
: The rescale_trunc() function is used for grid<->world coordinate conversion because it rounds towards 0 (not to nearest). It's important as rounding to nearest (which the standard rescale() function does) will shift the grid by half a cell.

Definition at line 67 of file poly_grid_partition.h.

Member Typedef Documentation

◆ EDGE_LIST

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

Definition at line 86 of file poly_grid_partition.h.

Member Enumeration Documentation

◆ HASH_FLAG

Enumerator
LEAD_EDGE 
TRAIL_EDGE 

Definition at line 80 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 
)

Definition at line 28 of file poly_grid_partition.cpp.

29 {
30  build( aPolyOutline, gridSize );
31 }
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 74 of file poly_grid_partition.h.

75  {
76  return m_bbox;
77  }

References m_bbox.

◆ build()

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

Definition at line 228 of file poly_grid_partition.cpp.

229 {
230  m_outline = aPolyOutline;
231 
232  //if (orientation(m_outline) < 0)
233  // m_outline = m_outline.Reverse();
234 
235  m_bbox = m_outline.BBox();
236  m_gridSize = gridSize;
237 
238  m_outline.SetClosed( true );
239 
240  m_grid.reserve( gridSize * gridSize );
241 
242  for( int y = 0; y < gridSize; y++ )
243  {
244  for( int x = 0; x < gridSize; x++ )
245  {
246  m_grid.emplace_back();
247  }
248  }
249 
250  VECTOR2I ref_v( 0, 1 );
251  VECTOR2I ref_h( 0, 1 );
252 
253  m_flags.reserve( m_outline.SegmentCount() );
254 
255  std::unordered_map<SEG, int, segHash, segsEqual> edgeSet;
256 
257  for( int i = 0; i < m_outline.SegmentCount(); i++ )
258  {
259  SEG edge = m_outline.Segment( i );
260 
261  if( edgeSet.find( edge ) == edgeSet.end() )
262  {
263  edgeSet[edge] = 1;
264  }
265  else
266  {
267  edgeSet[edge]++;
268  }
269  }
270 
271  for( int i = 0; i < m_outline.SegmentCount(); i++ )
272  {
273  auto edge = m_outline.Segment( i );
274  auto dir = edge.B - edge.A;
275  int flags = 0;
276 
277 
278  if( dir.y == 0 )
279  {
280  flags = 0;
281  }
282  else if( edgeSet[edge] == 1 )
283  {
284  if( dir.Dot( ref_h ) < 0 )
285  {
286  flags |= LEAD_EDGE;
287  }
288  else if( dir.Dot( ref_h ) > 0 )
289  {
290  flags |= TRAIL_EDGE;
291  }
292  }
293 
294  m_flags.push_back( flags );
295 
296  if( edge.A.y == edge.B.y )
297  continue;
298 
299  std::set<int> indices;
300 
301  indices.insert( m_gridSize * poly2gridY( edge.A.y ) + poly2gridX( edge.A.x ) );
302  indices.insert( m_gridSize * poly2gridY( edge.B.y ) + poly2gridX( edge.B.x ) );
303 
304  if( edge.A.x > edge.B.x )
305  std::swap( edge.A, edge.B );
306 
307  dir = edge.B - edge.A;
308 
309  if( dir.x != 0 )
310  {
311  int gx0 = poly2gridX( edge.A.x );
312  int gx1 = poly2gridX( edge.B.x );
313 
314  for( int x = gx0; x <= gx1; x++ )
315  {
316  int px = grid2polyX( x );
317  int py = ( edge.A.y + rescale_trunc( dir.y, px - edge.A.x, dir.x ) );
318  int yy = poly2gridY( py );
319 
320  indices.insert( m_gridSize * yy + x );
321 
322  if( x > 0 )
323  indices.insert( m_gridSize * yy + x - 1 );
324  }
325  }
326 
327  if( edge.A.y > edge.B.y )
328  std::swap( edge.A, edge.B );
329 
330  dir = edge.B - edge.A;
331 
332  if( dir.y != 0 )
333  {
334  int gy0 = poly2gridY( edge.A.y );
335  int gy1 = poly2gridY( edge.B.y );
336 
337  for( int y = gy0; y <= gy1; y++ )
338  {
339  int py = grid2polyY( y );
340  int px = ( edge.A.x + rescale_trunc( dir.x, py - edge.A.y, dir.y ) );
341  int xx = poly2gridX( px );
342 
343  indices.insert( m_gridSize * y + xx );
344 
345  if( y > 0 )
346  indices.insert( m_gridSize * ( y - 1 ) + xx );
347  }
348  }
349 
350  for( auto idx : indices )
351  m_grid[idx].push_back( i );
352  }
353 }
SHAPE_LINE_CHAIN m_outline
Define 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)
Mark the line chain as closed (i.e.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
int grid2polyX(int x) const
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
VECTOR2I A
Definition: seg.h:48
int poly2gridY(int y) const
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const
VECTOR2I B
Definition: seg.h:49

References SEG::B, SHAPE_LINE_CHAIN::BBox(), grid2polyX(), grid2polyY(), LEAD_EDGE, m_bbox, m_flags, m_grid, m_gridSize, m_outline, poly2gridX(), poly2gridY(), rescale_trunc(), SHAPE_LINE_CHAIN::Segment(), SHAPE_LINE_CHAIN::SegmentCount(), SHAPE_LINE_CHAIN::SetClosed(), and TRAIL_EDGE.

Referenced by POLY_GRID_PARTITION().

◆ checkClearance()

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

Definition at line 122 of file poly_grid_partition.cpp.

123 {
124  int gx0 = poly2gridX( aP.x - aClearance - 1 );
125  int gx1 = poly2gridX( aP.x + aClearance + 1 );
126  int gy0 = poly2gridY( aP.y - aClearance - 1 );
127  int gy1 = poly2gridY( aP.y + aClearance + 1 );
128 
130 
131  ecoord dist = (ecoord) aClearance * aClearance;
132 
133  for( int gx = gx0; gx <= gx1; gx++ )
134  {
135  for( int gy = gy0; gy <= gy1; gy++ )
136  {
137  const auto& cell = m_grid[m_gridSize * gy + gx];
138  for( auto index : cell )
139  {
140  const auto& seg = m_outline.Segment( index );
141 
142  if( seg.SquaredDistance( aP ) <= dist )
143  return true;
144  }
145  }
146  }
147  return false;
148 }
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:76
SHAPE_LINE_CHAIN m_outline
int poly2gridX(int x) const
std::vector< EDGE_LIST > m_grid
VECTOR2I::extended_type ecoord
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
int poly2gridY(int y) const

References 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,
int  aClearance = 0 
)

Definition at line 34 of file poly_grid_partition.cpp.

35 {
36  if( containsPoint( aP ) )
37  return 1;
38 
39  if( aClearance > 0 )
40  return checkClearance( aP, aClearance );
41 
42  return 0;
43 }
int containsPoint(const VECTOR2I &aP, bool debug=false) const
bool checkClearance(const VECTOR2I &aP, int aClearance)

References checkClearance(), and containsPoint().

Referenced by BOOST_AUTO_TEST_CASE().

◆ containsPoint()

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

Definition at line 46 of file poly_grid_partition.cpp.

47 {
48  const auto gridPoint = poly2grid( aP );
49 
50  if( !m_bbox.Contains( aP ) )
51  return 0;
52 
53  SCAN_STATE state;
54  const EDGE_LIST& cell = m_grid[m_gridSize * gridPoint.y + gridPoint.x];
55 
56  scanCell( state, cell, aP, gridPoint.x, gridPoint.y );
57 
58  if( state.nearest < 0 )
59  {
60  state = SCAN_STATE();
61 
62  for( int d = 1; d <= m_gridSize; d++ )
63  {
64  int xl = gridPoint.x - d;
65  int xh = gridPoint.x + d;
66 
67  if( xl >= 0 )
68  {
69  const EDGE_LIST& cell2 = m_grid[m_gridSize * gridPoint.y + xl];
70  scanCell( state, cell2, aP, xl, gridPoint.y );
71 
72  if( state.nearest >= 0 )
73  break;
74  }
75 
76  if( xh < m_gridSize )
77  {
78  const EDGE_LIST& cell2 = m_grid[m_gridSize * gridPoint.y + xh];
79  scanCell( state, cell2, aP, xh, gridPoint.y );
80 
81  if( state.nearest >= 0 )
82  break;
83  }
84  }
85  }
86 
87 #ifdef TOM_EXTRA_VERBOSE
88  printf( "Nearest: %d prev: %d dmax %d\n", state.nearest, state.nearest_prev, state.dist_max );
89 #endif
90 
91  if( state.nearest < 0 )
92  return 0;
93 
94  if( state.dist_max == 0 )
95  return 1;
96 
97 
98  // special case for diagonal 'slits', e.g. two segments that partially overlap each other.
99  // Just love handling degeneracy... As I can't find any reliable way of fixing it for the moment,
100  // let's fall back to the good old O(N) point-in-polygon test
101  if( state.nearest_prev >= 0 && state.dist_max == state.dist_prev )
102  {
103  int d = std::abs( state.nearest_prev - state.nearest );
104 
105  if( ( d == 1 ) && ( ( m_flags[state.nearest_prev] & m_flags[state.nearest] ) == 0 ) )
106  {
107  return m_outline.PointInside( aP );
108  }
109  }
110 
111  if( state.dist_max > 0 )
112  {
113  return m_flags[state.nearest] & LEAD_EDGE ? 1 : 0;
114  }
115  else
116  {
117  return m_flags[state.nearest] & TRAIL_EDGE ? 1 : 0;
118  }
119 }
const VECTOR2I poly2grid(const VECTOR2I &p) const
void scanCell(SCAN_STATE &state, const EDGE_LIST &cell, const VECTOR2I &aP, int cx, int cy) const
SHAPE_LINE_CHAIN m_outline
std::vector< int > m_flags
std::vector< EDGE_LIST > m_grid
bool Contains(const Vec &aPoint) const
Definition: box2.h:134
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
std::vector< int > EDGE_LIST

References BOX2< Vec >::Contains(), POLY_GRID_PARTITION::SCAN_STATE::dist_max, POLY_GRID_PARTITION::SCAN_STATE::dist_prev, LEAD_EDGE, m_bbox, m_flags, m_grid, m_gridSize, m_outline, POLY_GRID_PARTITION::SCAN_STATE::nearest, POLY_GRID_PARTITION::SCAN_STATE::nearest_prev, SHAPE_LINE_CHAIN_BASE::PointInside(), poly2grid(), scanCell(), TRAIL_EDGE, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by ContainsPoint().

◆ grid2poly()

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

Definition at line 159 of file poly_grid_partition.cpp.

160 {
163  return VECTOR2I( px, py );
164 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
coord_type GetWidth() const
Definition: box2.h:180
const Vec & GetPosition() const
Definition: box2.h:177
coord_type GetHeight() const
Definition: box2.h:181
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const

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

◆ grid2polyX()

int POLY_GRID_PARTITION::grid2polyX ( int  x) const
private

Definition at line 167 of file poly_grid_partition.cpp.

168 {
170 }
coord_type GetWidth() const
Definition: box2.h:180
const Vec & GetPosition() const
Definition: box2.h:177
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const

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

Referenced by build(), and scanCell().

◆ grid2polyY()

int POLY_GRID_PARTITION::grid2polyY ( int  y) const
private

Definition at line 173 of file poly_grid_partition.cpp.

174 {
176 }
const Vec & GetPosition() const
Definition: box2.h:177
coord_type GetHeight() const
Definition: box2.h:181
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const

References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetPosition(), m_bbox, m_gridSize, rescale_trunc(), 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 89 of file poly_grid_partition.h.

90  {
91  std::hash<T> hasher;
92  seed ^= hasher( v ) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
93  }

◆ inRange()

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

Definition at line 452 of file poly_grid_partition.cpp.

453 {
454  if( v1 < v2 )
455  {
456  return x >= v1 && x <= v2;
457  }
458 
459  return x >= v2 && x <= v1;
460 }
VECTOR2I v2(1, 0)
Test suite for KiCad math code.

References v2.

Referenced by scanCell().

◆ poly2grid()

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

Definition at line 179 of file poly_grid_partition.cpp.

180 {
183 
184  if( px < 0 )
185  px = 0;
186 
187  if( px >= m_gridSize )
188  px = m_gridSize - 1;
189 
190  if( py < 0 )
191  py = 0;
192 
193  if( py >= m_gridSize )
194  py = m_gridSize - 1;
195 
196  return VECTOR2I( px, py );
197 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
coord_type GetWidth() const
Definition: box2.h:180
const Vec & GetPosition() const
Definition: box2.h:177
coord_type GetHeight() const
Definition: box2.h:181
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const

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

Referenced by containsPoint().

◆ poly2gridX()

int POLY_GRID_PARTITION::poly2gridX ( int  x) const
private

Definition at line 200 of file poly_grid_partition.cpp.

201 {
203 
204  if( px < 0 )
205  px = 0;
206 
207  if( px >= m_gridSize )
208  px = m_gridSize - 1;
209 
210  return px;
211 }
coord_type GetWidth() const
Definition: box2.h:180
const Vec & GetPosition() const
Definition: box2.h:177
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const

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

Referenced by build(), and checkClearance().

◆ poly2gridY()

int POLY_GRID_PARTITION::poly2gridY ( int  y) const
private

Definition at line 214 of file poly_grid_partition.cpp.

215 {
217 
218  if( py < 0 )
219  py = 0;
220 
221  if( py >= m_gridSize )
222  py = m_gridSize - 1;
223 
224  return py;
225 }
const Vec & GetPosition() const
Definition: box2.h:177
coord_type GetHeight() const
Definition: box2.h:181
int rescale_trunc(int aNumerator, int aValue, int aDenominator) const

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

Referenced by build(), and checkClearance().

◆ rescale_trunc()

int POLY_GRID_PARTITION::rescale_trunc ( int  aNumerator,
int  aValue,
int  aDenominator 
) const
private

Definition at line 151 of file poly_grid_partition.cpp.

152 {
153  int64_t numerator = (int64_t) aNumerator * (int64_t) aValue;
154  return numerator / aDenominator;
155 }

Referenced by build(), grid2poly(), grid2polyX(), grid2polyY(), poly2grid(), poly2gridX(), and poly2gridY().

◆ scanCell()

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

Definition at line 356 of file poly_grid_partition.cpp.

358 {
359  int cx0 = grid2polyX( cx );
360  int cx1 = grid2polyX( cx + 1 );
361 
362 #ifdef TOM_EXTRA_VERBOSE
363  printf( "Scan %d %d\n", cx, cy );
364 #endif
365 
366  for( auto index : cell )
367  {
368  const SEG& edge = m_outline.CSegment( index );
369 
370 
371  if( m_flags[index] == 0 )
372  {
373  if( aP.y == edge.A.y
374  && inRange( edge.A.x, edge.B.x, aP.x ) ) // we belong to the outline
375  {
376  state.nearest = index;
377  state.dist_max = 0;
378  return;
379  }
380  else
381  {
382  continue;
383  }
384  }
385 
386  if( inRange( edge.A.y, edge.B.y, aP.y ) )
387  {
388 #ifdef TOM_EXTRA_VERBOSE
389  printf( "Test edge: %d [%d %d %d %d] p %d %d flags %d\n", index, edge.A.x, edge.A.y,
390  edge.B.x, edge.B.y, aP.x, aP.y );
391 #endif
392  int dist = 0;
393  int x0;
394  if( edge.A.y == aP.y )
395  {
396  x0 = edge.A.x;
397  }
398  else if( edge.B.y == aP.y )
399  {
400  x0 = edge.B.x;
401  }
402  else
403  {
404  x0 = edge.A.x
405  + rescale( ( edge.B.x - edge.A.x ), ( aP.y - edge.A.y ),
406  ( edge.B.y - edge.A.y ) );
407  }
408 
409 
410  dist = aP.x - x0;
411 
412 #ifdef TOM_EXTRA_VERBOSE
413  printf( " x0 %d dist %d [%s]\n", x0, dist,
414  x0 < cx0 || x0 > cx1 ? "outside" : "inside" );
415 #endif
416 
417  if( x0 < cx0 || x0 > cx1 )
418  {
419  continue;
420  }
421 
422 
423  if( dist == 0 )
424  {
425  if( state.nearest_prev < 0 || state.nearest != index )
426  {
427  state.dist_prev = state.dist_max;
428  state.nearest_prev = state.nearest;
429  }
430 
431  state.nearest = index;
432  state.dist_max = 0;
433  return;
434  }
435 
436  if( dist != 0 && std::abs( dist ) <= std::abs( state.dist_max ) )
437  {
438  if( state.nearest_prev < 0 || state.nearest != index )
439  {
440  state.dist_prev = state.dist_max;
441  state.nearest_prev = state.nearest;
442  }
443 
444  state.dist_max = dist;
445  state.nearest = index;
446  }
447  }
448  }
449 }
SHAPE_LINE_CHAIN m_outline
bool inRange(int v1, int v2, int x) const
std::vector< int > m_flags
int grid2polyX(int x) const
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
VECTOR2I A
Definition: seg.h:48
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:98
VECTOR2I B
Definition: seg.h:49

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

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 157 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 158 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 155 of file poly_grid_partition.h.

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


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