POLY_YSTRIPES_INDEX Class Reference

Y-stripe spatial index for efficient point-in-polygon containment testing. More...

#include <poly_ystripes_index.h>

Classes
struct	EDGE

Public Member Functions
	POLY_YSTRIPES_INDEX ()=default
void	Build (const SHAPE_POLY_SET &aPolySet)
	Build the spatial index from a SHAPE_POLY_SET's outlines and holes.
bool	Contains (const VECTOR2I &aPt, int aAccuracy=0) const
	Test whether a point is inside the indexed polygon set.

Private Member Functions
int	yToStripe (int64_t aY) const

Private Attributes
std::vector< EDGE >	m_edges
std::vector< std::vector< int > >	m_stripes
int64_t	m_yMin = 0
int64_t	m_yMax = 0
int64_t	m_stripeHeight = 1
int	m_stripeCount = 0
int	m_outlineCount = 0

Detailed Description

Y-stripe spatial index for efficient point-in-polygon containment testing.

Inspired by the YStripes indexing strategy from the TG geometry library (https://github.com/tidwall/tg, MIT license, Copyright (c) 2023 Joshua J Baker).

Divides the polygon set's Y extent into uniform horizontal stripes and buckets each non-horizontal edge into every stripe its Y range overlaps. Containment queries ray-cast only against edges in the queried point's stripe, reducing work from O(V) to O(V/sqrt(V)) on average.

The ray-crossing algorithm matches SHAPE_LINE_CHAIN_BASE::PointInside() exactly, including the accuracy semantics where aAccuracy > 1 falls back to edge-distance testing.

Definition at line 52 of file poly_ystripes_index.h.

Constructor & Destructor Documentation

POLY_YSTRIPES_INDEX()

POLY_YSTRIPES_INDEX::POLY_YSTRIPES_INDEX ( )

default

Member Function Documentation

Build()

void POLY_YSTRIPES_INDEX::Build ( const SHAPE_POLY_SET & aPolySet )

inline

Build the spatial index from a SHAPE_POLY_SET's outlines and holes.

Indexes every non-horizontal edge of every outline and hole in the polygon set. Hole edges are indexed with the same outlineIdx as their parent outline so that ray-crossing counts automatically produce even totals for points inside holes. Must be called before Contains().

Definition at line 65 of file poly_ystripes_index.h.

References SHAPE_POLY_SET::CHole(), SHAPE_POLY_SET::COutline(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_POLY_SET::HoleCount(), m_edges, m_outlineCount, m_stripeCount, m_stripeHeight, m_stripes, m_yMax, m_yMin, SHAPE_POLY_SET::OutlineCount(), POLY_YSTRIPES_INDEX::EDGE::p1, POLY_YSTRIPES_INDEX::EDGE::p2, SHAPE_LINE_CHAIN::PointCount(), push_back(), VECTOR2< T >::y, and yToStripe().

Referenced by BOOST_AUTO_TEST_CASE(), and ZONE_FILLER::fillCopperZone().

Contains()

bool POLY_YSTRIPES_INDEX::Contains ( const VECTOR2I & aPt, int aAccuracy = 0 ) const

inline

Test whether a point is inside the indexed polygon set.

Uses the same ray-crossing algorithm as SHAPE_LINE_CHAIN_BASE::PointInside(). When aAccuracy > 1, also checks if the point is within aAccuracy distance of any edge (matching the PointOnEdge fallback behavior).

Parameters

aPt	The point to test.
aAccuracy	Distance threshold for edge-proximity fallback. Values <= 1 skip the edge test for performance.

Returns

true if the point is inside any outline or (when aAccuracy > 1) within aAccuracy distance of any edge.

Definition at line 188 of file poly_ystripes_index.h.

References POLY_YSTRIPES_INDEX::EDGE::isHole, m_edges, m_outlineCount, m_stripeCount, m_stripes, POLY_YSTRIPES_INDEX::EDGE::outlineIdx, POLY_YSTRIPES_INDEX::EDGE::p1, POLY_YSTRIPES_INDEX::EDGE::p2, rescale(), SEG::Square(), SEG::SquaredDistance(), VECTOR2< T >::x, VECTOR2< T >::y, and yToStripe().

Referenced by BOOST_AUTO_TEST_CASE(), and ZONE_FILLER::fillCopperZone().

yToStripe()

int POLY_YSTRIPES_INDEX::yToStripe ( int64_t aY ) const

inlineprivate

Definition at line 260 of file poly_ystripes_index.h.

References m_stripeCount, m_stripeHeight, and m_yMin.

Referenced by Build(), and Contains().

Member Data Documentation

m_edges

std::vector<EDGE> POLY_YSTRIPES_INDEX::m_edges

private

Definition at line 275 of file poly_ystripes_index.h.

Referenced by Build(), and Contains().

m_outlineCount

int POLY_YSTRIPES_INDEX::m_outlineCount = 0

private

Definition at line 281 of file poly_ystripes_index.h.

Referenced by Build(), and Contains().

m_stripeCount

int POLY_YSTRIPES_INDEX::m_stripeCount = 0

private

Definition at line 280 of file poly_ystripes_index.h.

Referenced by Build(), Contains(), and yToStripe().

m_stripeHeight

int64_t POLY_YSTRIPES_INDEX::m_stripeHeight = 1

private

Definition at line 279 of file poly_ystripes_index.h.

Referenced by Build(), and yToStripe().

m_stripes

std::vector<std::vector<int> > POLY_YSTRIPES_INDEX::m_stripes

private

Definition at line 276 of file poly_ystripes_index.h.

Referenced by Build(), and Contains().

m_yMax

int64_t POLY_YSTRIPES_INDEX::m_yMax = 0

private

Definition at line 278 of file poly_ystripes_index.h.

Referenced by Build().

m_yMin

int64_t POLY_YSTRIPES_INDEX::m_yMin = 0

private

Definition at line 277 of file poly_ystripes_index.h.

Referenced by Build(), and yToStripe().

---

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

• poly_ystripes_index.h