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 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

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

enum POLY_GRID_PARTITION::HASH_FLAG

private

Enumerator
LEAD_EDGE
TRAIL_EDGE

Definition at line 80 of file poly_grid_partition.h.

 {
 LEAD_EDGE = 1,
 TRAIL_EDGE = 2,
 };

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.

{
 build( aPolyOutline, 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.

 {
 return m_bbox;
 }

References m_bbox.

build()

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

private

Definition at line 234 of file poly_grid_partition.cpp.

{
 m_outline = aPolyOutline;

 //if (orientation(m_outline) < 0)
 // m_outline = m_outline.Reverse();

 m_bbox = m_outline.BBox();
 m_gridSize = gridSize;

 m_outline.SetClosed( true );

 m_grid.reserve( gridSize * gridSize );

 for( int y = 0; y < gridSize; y++ )
 {
 for( int x = 0; x < gridSize; x++ )
 {
 m_grid.emplace_back();
 }
 }

 VECTOR2I ref_v( 0, 1 );
 VECTOR2I ref_h( 0, 1 );

 m_flags.reserve( m_outline.SegmentCount() );

 std::unordered_map<SEG, int, segHash, segsEqual> edgeSet;

 for( int i = 0; i < m_outline.SegmentCount(); i++ )
 {
 SEG edge = m_outline.Segment( i );

 if( edgeSet.find( edge ) == edgeSet.end() )
 {
 edgeSet[edge] = 1;
 }
 else
 {
 edgeSet[edge]++;
 }
 }

 for( int i = 0; i < m_outline.SegmentCount(); i++ )
 {
 auto edge = m_outline.Segment( i );
 auto dir = edge.B - edge.A;
 int flags = 0;


 if( dir.y == 0 )
 {
 flags = 0;
 }
 else if( edgeSet[edge] == 1 )
 {
 if( dir.Dot( ref_h ) < 0 )
 {
 flags |= LEAD_EDGE;
 }
 else if( dir.Dot( ref_h ) > 0 )
 {
 flags |= TRAIL_EDGE;
 }
 }

 m_flags.push_back( flags );

 if( edge.A.y == edge.B.y )
 continue;

 std::set<int> indices;

 indices.insert( m_gridSize * poly2gridY( edge.A.y ) + poly2gridX( edge.A.x ) );
 indices.insert( m_gridSize * poly2gridY( edge.B.y ) + poly2gridX( edge.B.x ) );

 if( edge.A.x > edge.B.x )
 std::swap( edge.A, edge.B );

 dir = edge.B - edge.A;

 if( dir.x != 0 )
 {
 int gx0 = poly2gridX( edge.A.x );
 int gx1 = poly2gridX( edge.B.x );

 for( int x = gx0; x <= gx1; x++ )
 {
 int px = grid2polyX( x );
 int py = ( edge.A.y + rescale_trunc( dir.y, px - edge.A.x, dir.x ) );
 int yy = poly2gridY( py );

 indices.insert( m_gridSize * yy + x );

 if( x > 0 )
 indices.insert( m_gridSize * yy + x - 1 );
 }
 }

 if( edge.A.y > edge.B.y )
 std::swap( edge.A, edge.B );

 dir = edge.B - edge.A;

 if( dir.y != 0 )
 {
 int gy0 = poly2gridY( edge.A.y );
 int gy1 = poly2gridY( edge.B.y );

 for( int y = gy0; y <= gy1; y++ )
 {
 int py = grid2polyY( y );
 int px = ( edge.A.x + rescale_trunc( dir.x, py - edge.A.y, dir.y ) );
 int xx = poly2gridX( px );

 indices.insert( m_gridSize * y + xx );

 if( y > 0 )
 indices.insert( m_gridSize * ( y - 1 ) + xx );
 }
 }

 for( auto idx : indices )
 m_grid[idx].push_back( i );
 }
}

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.

{
 int gx0 = poly2gridX( aP.x - aClearance - 1 );
 int gx1 = poly2gridX( aP.x + aClearance + 1 );
 int gy0 = poly2gridY( aP.y - aClearance - 1 );
 int gy1 = poly2gridY( aP.y + aClearance + 1 );

 using ecoord = VECTOR2I::extended_type;

 ecoord dist = (ecoord) aClearance * aClearance;

 for( int gx = gx0; gx <= gx1; gx++ )
 {
 for( int gy = gy0; gy <= gy1; gy++ )
 {
 const auto& cell = m_grid[m_gridSize * gy + gx];
 for( auto index : cell )
 {
 const auto& seg = m_outline.Segment( index );

 if( seg.SquaredDistance( aP ) <= dist )
 return true;
 }
 }
 }
 return false;
}

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.

{
 if( containsPoint( aP ) )
 return 1;

 if( aClearance > 0 )
 return checkClearance( aP, aClearance );

 return 0;
}

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.

{
 const auto gridPoint = poly2grid( aP );

 if( !m_bbox.Contains( aP ) )
 return 0;

 SCAN_STATE state;
 const EDGE_LIST& cell = m_grid[m_gridSize * gridPoint.y + gridPoint.x];

 scanCell( state, cell, aP, gridPoint.x, gridPoint.y );

 if( state.nearest < 0 )
 {
 state = SCAN_STATE();

 for( int d = 1; d <= m_gridSize; d++ )
 {
 int xl = gridPoint.x - d;
 int xh = gridPoint.x + d;

 if( xl >= 0 )
 {
 const EDGE_LIST& cell2 = m_grid[m_gridSize * gridPoint.y + xl];
 scanCell( state, cell2, aP, xl, gridPoint.y );

 if( state.nearest >= 0 )
 break;
 }

 if( xh < m_gridSize )
 {
 const EDGE_LIST& cell2 = m_grid[m_gridSize * gridPoint.y + xh];
 scanCell( state, cell2, aP, xh, gridPoint.y );

 if( state.nearest >= 0 )
 break;
 }
 }
 }

#ifdef TOM_EXTRA_VERBOSE
 printf( "Nearest: %d prev: %d dmax %d\n", state.nearest, state.nearest_prev, state.dist_max );
#endif

 if( state.nearest < 0 )
 return 0;

 if( state.dist_max == 0 )
 return 1;


 // special case for diagonal 'slits', e.g. two segments that partially overlap each other.
 // Just love handling degeneracy... As I can't find any reliable way of fixing it for the moment,
 // let's fall back to the good old O(N) point-in-polygon test
 if( state.nearest_prev >= 0 && state.dist_max == state.dist_prev )
 {
 int d = std::abs( state.nearest_prev - state.nearest );

 if( ( d == 1 ) && ( ( m_flags[state.nearest_prev] & m_flags[state.nearest] ) == 0 ) )
 {
 return m_outline.PointInside( aP );
 }
 }

 if( state.dist_max > 0 )
 {
 return m_flags[state.nearest] & LEAD_EDGE ? 1 : 0;
 }
 else
 {
 return m_flags[state.nearest] & TRAIL_EDGE ? 1 : 0;
 }
}

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 165 of file poly_grid_partition.cpp.

{
 int px = rescale_trunc( p.x, m_bbox.GetWidth(), m_gridSize ) + m_bbox.GetPosition().x;
 int py = rescale_trunc( p.y, m_bbox.GetHeight(), m_gridSize ) + m_bbox.GetPosition().y;
 return VECTOR2I( px, py );
}

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 173 of file poly_grid_partition.cpp.

{
 return rescale_trunc( x, m_bbox.GetWidth(), m_gridSize ) + m_bbox.GetPosition().x;
}

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 179 of file poly_grid_partition.cpp.

{
 return rescale_trunc( y, m_bbox.GetHeight(), m_gridSize ) + m_bbox.GetPosition().y;
}

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.

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

inRange()

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

private

Definition at line 458 of file poly_grid_partition.cpp.

{
 if( v1 < v2 )
 {
 return x >= v1 && x <= v2;
 }

 return x >= v2 && x <= v1;
}

References v2.

Referenced by scanCell().

poly2grid()

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

private

Definition at line 185 of file poly_grid_partition.cpp.

{
 int px = rescale_trunc( p.x - m_bbox.GetPosition().x, m_gridSize, m_bbox.GetWidth() );
 int py = rescale_trunc( p.y - m_bbox.GetPosition().y, m_gridSize, m_bbox.GetHeight() );

 if( px < 0 )
 px = 0;

 if( px >= m_gridSize )
 px = m_gridSize - 1;

 if( py < 0 )
 py = 0;

 if( py >= m_gridSize )
 py = m_gridSize - 1;

 return VECTOR2I( px, py );
}

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 206 of file poly_grid_partition.cpp.

{
 int px = rescale_trunc( x - m_bbox.GetPosition().x, m_gridSize, m_bbox.GetWidth() );

 if( px < 0 )
 px = 0;

 if( px >= m_gridSize )
 px = m_gridSize - 1;

 return px;
}

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 220 of file poly_grid_partition.cpp.

{
 int py = rescale_trunc( y - m_bbox.GetPosition().y, m_gridSize, m_bbox.GetHeight() );

 if( py < 0 )
 py = 0;

 if( py >= m_gridSize )
 py = m_gridSize - 1;

 return py;
}

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.

{
 int64_t numerator = (int64_t) aNumerator * (int64_t) aValue;

 wxASSERT( aDenominator != 0 );

 if( aDenominator == 0 ) // Avoid crash when divide by 0
 aDenominator = 1;

 return numerator / aDenominator;
}

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 362 of file poly_grid_partition.cpp.

{
 int cx0 = grid2polyX( cx );
 int cx1 = grid2polyX( cx + 1 );

#ifdef TOM_EXTRA_VERBOSE
 printf( "Scan %d %d\n", cx, cy );
#endif

 for( auto index : cell )
 {
 const SEG& edge = m_outline.CSegment( index );


 if( m_flags[index] == 0 )
 {
 if( aP.y == edge.A.y
 && inRange( edge.A.x, edge.B.x, aP.x ) ) // we belong to the outline
 {
 state.nearest = index;
 state.dist_max = 0;
 return;
 }
 else
 {
 continue;
 }
 }

 if( inRange( edge.A.y, edge.B.y, aP.y ) )
 {
#ifdef TOM_EXTRA_VERBOSE
 printf( "Test edge: %d [%d %d %d %d] p %d %d flags %d\n", index, edge.A.x, edge.A.y,
 edge.B.x, edge.B.y, aP.x, aP.y );
#endif
 int dist = 0;
 int x0;
 if( edge.A.y == aP.y )
 {
 x0 = edge.A.x;
 }
 else if( edge.B.y == aP.y )
 {
 x0 = edge.B.x;
 }
 else
 {
 x0 = edge.A.x
 + rescale( ( edge.B.x - edge.A.x ), ( aP.y - edge.A.y ),
 ( edge.B.y - edge.A.y ) );
 }


 dist = aP.x - x0;

#ifdef TOM_EXTRA_VERBOSE
 printf( " x0 %d dist %d [%s]\n", x0, dist,
 x0 < cx0 || x0 > cx1 ? "outside" : "inside" );
#endif

 if( x0 < cx0 || x0 > cx1 )
 {
 continue;
 }


 if( dist == 0 )
 {
 if( state.nearest_prev < 0 || state.nearest != index )
 {
 state.dist_prev = state.dist_max;
 state.nearest_prev = state.nearest;
 }

 state.nearest = index;
 state.dist_max = 0;
 return;
 }

 if( dist != 0 && std::abs( dist ) <= std::abs( state.dist_max ) )
 {
 if( state.nearest_prev < 0 || state.nearest != index )
 {
 state.dist_prev = state.dist_max;
 state.nearest_prev = state.nearest;
 }

 state.dist_max = dist;
 state.nearest = index;
 }
 }
 }
}

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

Definition at line 156 of file poly_grid_partition.h.

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

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

Definition at line 154 of file poly_grid_partition.h.

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

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:

• poly_grid_partition.h
• poly_grid_partition.cpp