![]() |
KiCad PCB EDA Suite
|
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 BOX2I & | BBox () 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_LIST > | m_grid |
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:
Definition at line 67 of file poly_grid_partition.h.
|
private |
Definition at line 86 of file poly_grid_partition.h.
|
private |
POLY_GRID_PARTITION::POLY_GRID_PARTITION | ( | const SHAPE_LINE_CHAIN & | aPolyOutline, |
int | gridSize | ||
) |
Definition at line 28 of file poly_grid_partition.cpp.
References build().
|
inline |
|
private |
Definition at line 234 of file poly_grid_partition.cpp.
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().
|
private |
Definition at line 122 of file poly_grid_partition.cpp.
References m_grid, m_gridSize, m_outline, poly2gridX(), poly2gridY(), SHAPE_LINE_CHAIN::Segment(), VECTOR2< T >::x, and VECTOR2< T >::y.
Referenced by ContainsPoint().
int POLY_GRID_PARTITION::ContainsPoint | ( | const VECTOR2I & | aP, |
int | aClearance = 0 |
||
) |
Definition at line 34 of file poly_grid_partition.cpp.
References checkClearance(), and containsPoint().
Referenced by BOOST_AUTO_TEST_CASE().
|
private |
Definition at line 46 of file poly_grid_partition.cpp.
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().
Definition at line 165 of file poly_grid_partition.cpp.
References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetPosition(), BOX2< Vec >::GetWidth(), m_bbox, m_gridSize, rescale_trunc(), VECTOR2< T >::x, and VECTOR2< T >::y.
|
private |
Definition at line 173 of file poly_grid_partition.cpp.
References BOX2< Vec >::GetPosition(), BOX2< Vec >::GetWidth(), m_bbox, m_gridSize, rescale_trunc(), and VECTOR2< T >::x.
Referenced by build(), and scanCell().
|
private |
Definition at line 179 of file poly_grid_partition.cpp.
References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetPosition(), m_bbox, m_gridSize, rescale_trunc(), and VECTOR2< T >::y.
Referenced by build().
|
inlineprivate |
Definition at line 89 of file poly_grid_partition.h.
|
private |
Definition at line 185 of file poly_grid_partition.cpp.
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().
|
private |
Definition at line 206 of file poly_grid_partition.cpp.
References BOX2< Vec >::GetPosition(), BOX2< Vec >::GetWidth(), m_bbox, m_gridSize, rescale_trunc(), and VECTOR2< T >::x.
Referenced by build(), and checkClearance().
|
private |
Definition at line 220 of file poly_grid_partition.cpp.
References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetPosition(), m_bbox, m_gridSize, rescale_trunc(), and VECTOR2< T >::y.
Referenced by build(), and checkClearance().
|
private |
Definition at line 151 of file poly_grid_partition.cpp.
Referenced by build(), grid2poly(), grid2polyX(), grid2polyY(), poly2grid(), poly2gridX(), and poly2gridY().
|
private |
Definition at line 362 of file poly_grid_partition.cpp.
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().
|
private |
Definition at line 156 of file poly_grid_partition.h.
Referenced by BBox(), build(), containsPoint(), grid2poly(), grid2polyX(), grid2polyY(), poly2grid(), poly2gridX(), and poly2gridY().
|
private |
Definition at line 157 of file poly_grid_partition.h.
Referenced by build(), containsPoint(), and scanCell().
|
private |
Definition at line 158 of file poly_grid_partition.h.
Referenced by build(), checkClearance(), and containsPoint().
|
private |
Definition at line 154 of file poly_grid_partition.h.
Referenced by build(), checkClearance(), containsPoint(), grid2poly(), grid2polyX(), grid2polyY(), poly2grid(), poly2gridX(), and poly2gridY().
|
private |
Definition at line 155 of file poly_grid_partition.h.
Referenced by build(), checkClearance(), containsPoint(), and scanCell().