POLY_CONTAINMENT_INDEX Class Reference

Spatial index for efficient point-in-polygon containment testing. More...

#include <poly_containment_index.h>

Classes
struct	EDGE

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

Private Attributes
std::vector< EDGE >	m_segments
KIRTREE::PACKED_RTREE< intptr_t, int, 2 >	m_tree
int	m_outlineCount = 0

Detailed Description

Spatial index for efficient point-in-polygon containment testing.

Standard SHAPE_LINE_CHAIN::PointInside() is O(V) per query, ray-casting against every edge. For large polygons with many containment queries (e.g. testing thousands of via positions against zone fills with tens of thousands of vertices), this becomes a bottleneck.

This class builds an R-tree of polygon edges so containment queries become O(log V + K) where K is the number of edges the horizontal ray actually crosses. 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 49 of file poly_containment_index.h.

Constructor & Destructor Documentation

POLY_CONTAINMENT_INDEX()

POLY_CONTAINMENT_INDEX::POLY_CONTAINMENT_INDEX ( )

default

Member Function Documentation

Build()

void POLY_CONTAINMENT_INDEX::Build ( const SHAPE_POLY_SET & aPolySet )

inline

Build the spatial index from a SHAPE_POLY_SET's outlines.

Indexes every edge of every outline in the polygon set. Must be called before Contains(). Only indexes outlines, not holes (zone fills are fractured and have no holes).

Definition at line 60 of file poly_containment_index.h.

References KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Add(), KIRTREE::PACKED_RTREE< DATATYPE, ELEMTYPE, NUMDIMS, FANOUT >::Builder::Build(), SHAPE_POLY_SET::COutline(), SHAPE_LINE_CHAIN::CPoint(), m_outlineCount, m_segments, m_tree, SHAPE_POLY_SET::OutlineCount(), SHAPE_LINE_CHAIN::PointCount(), VECTOR2< T >::x, and VECTOR2< T >::y.

Contains()

bool POLY_CONTAINMENT_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 104 of file poly_containment_index.h.

References m_outlineCount, m_segments, m_tree, POLY_CONTAINMENT_INDEX::EDGE::outlineIdx, POLY_CONTAINMENT_INDEX::EDGE::p1, POLY_CONTAINMENT_INDEX::EDGE::p2, rescale(), SEG::Square(), SEG::SquaredDistance(), VECTOR2< T >::x, and VECTOR2< T >::y.

Member Data Documentation

m_outlineCount

int POLY_CONTAINMENT_INDEX::m_outlineCount = 0

private

Definition at line 190 of file poly_containment_index.h.

Referenced by Build(), and Contains().

m_segments

std::vector<EDGE> POLY_CONTAINMENT_INDEX::m_segments

private

Definition at line 188 of file poly_containment_index.h.

Referenced by Build(), and Contains().

m_tree

KIRTREE::PACKED_RTREE<intptr_t, int, 2> POLY_CONTAINMENT_INDEX::m_tree

private

Definition at line 189 of file poly_containment_index.h.

Referenced by Build(), and Contains().

---

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

• poly_containment_index.h