The trapezoidal map and DAG search structure. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::TrapezoidalMapPointLocation::Result:

Public Member Functions
LocationResult	locate (const Point &p) const
	Locate a point in the trapezoidal map.

bool	contains (const Point &p) const
	Check if point is inside any input polygon.

Public Attributes
Array< Point >	points
	Unique endpoints of all segments.

Array< Segment >	segments
	Input segments.

Array< Trapezoid >	trapezoids
	All trapezoids created during construction.

Array< DagNode >	dag
	The search directed acyclic graph.

size_t	dag_root
	Index of the DAG root node.

size_t	num_input_segments
	Number of segments originally provided.

size_t	num_input_points
	Number of unique points derived from segments.

Detailed Description

The trapezoidal map and DAG search structure.

Definition at line 13007 of file geom_algorithms.H.

Member Function Documentation

◆ contains()

bool Aleph::TrapezoidalMapPointLocation::Result::contains ( const Point & p ) const

inline

Check if point is inside any input polygon.

Uses vertical ray casting over the input segments. This only works when the map was built from closed polygons (via the polygon overloads).

Parameters

p	The query point.

Returns: true if p is inside or on the boundary of an input polygon.

Definition at line 13075 of file geom_algorithms.H.

References Aleph::blossom_maximum_cardinality_matching(), contains(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::Point::get_x(), Aleph::Point::get_y(), num_input_points, num_input_segments, points, and segments.

Referenced by contains().

◆ locate()

LocationResult Aleph::TrapezoidalMapPointLocation::Result::locate ( const Point & p ) const

inline

Locate a point in the trapezoidal map.

Walks the DAG from the root.

At X-nodes: compare query point with stored point.
At Y-nodes: test above/below the stored segment.
At leaves: return the trapezoid.

Parameters

p	The query point.

Returns: LocationResult with type and indices.

Definition at line 13028 of file geom_algorithms.H.

References Aleph::area_of_parallelogram(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Segment::contains(), dag, dag_root, Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::TrapezoidalMapPointLocation::LEAF, Aleph::TrapezoidalMapPointLocation::NONE, Aleph::TrapezoidalMapPointLocation::ON_POINT, Aleph::TrapezoidalMapPointLocation::ON_SEGMENT, points, segments, Aleph::TrapezoidalMapPointLocation::TRAPEZOID, and Aleph::TrapezoidalMapPointLocation::X_NODE.

Member Data Documentation

◆ dag

Array<DagNode> Aleph::TrapezoidalMapPointLocation::Result::dag

The search directed acyclic graph.

Definition at line 13012 of file geom_algorithms.H.

Referenced by locate().

◆ dag_root

size_t Aleph::TrapezoidalMapPointLocation::Result::dag_root

Index of the DAG root node.

Definition at line 13013 of file geom_algorithms.H.

Referenced by locate().

◆ num_input_points

size_t Aleph::TrapezoidalMapPointLocation::Result::num_input_points

Number of unique points derived from segments.

Definition at line 13015 of file geom_algorithms.H.

Referenced by contains().

◆ num_input_segments

size_t Aleph::TrapezoidalMapPointLocation::Result::num_input_segments

Number of segments originally provided.

Definition at line 13014 of file geom_algorithms.H.

Referenced by contains(), and Aleph::TrapezoidalMapPointLocation::operator()().

◆ points

Array<Point> Aleph::TrapezoidalMapPointLocation::Result::points

Unique endpoints of all segments.

Definition at line 13009 of file geom_algorithms.H.

Referenced by contains(), and locate().

◆ segments

Array<Segment> Aleph::TrapezoidalMapPointLocation::Result::segments

Input segments.

Definition at line 13010 of file geom_algorithms.H.

Referenced by contains(), and locate().

◆ trapezoids

Array<Trapezoid> Aleph::TrapezoidalMapPointLocation::Result::trapezoids

All trapezoids created during construction.

Definition at line 13011 of file geom_algorithms.H.

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

geom_algorithms.H

Public Member Functions

Public Attributes