POLY_GRID_PARTITION Class Reference

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

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.

---

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

• 3rd_party/router/kimath/include/geometry/poly_grid_partition.h
• 3rd_party/router/kimath/src/geometry/poly_grid_partition.cpp