Horizon
|
Provide a fast test for point inside polygon. More...
#include <poly_grid_partition.h>
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 |
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: