Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Static Public Attributes | Static Private Member Functions | List of all members
Aleph::TrapezoidalMapPointLocation Class Reference

O(log n) point location via trapezoidal map with DAG search. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::TrapezoidalMapPointLocation:
[legend]

Classes

struct  DagNode
 A node in the search Directed Acyclic Graph (DAG). More...
 
struct  LocationResult
 Result of a point location query. More...
 
struct  Result
 The trapezoidal map and DAG search structure. More...
 
struct  Trapezoid
 A trapezoid in the decomposition. More...
 

Public Types

enum class  NodeType { X_NODE , Y_NODE , LEAF }
 Types of nodes in the search DAG. More...
 
enum class  LocationType { TRAPEZOID , ON_SEGMENT , ON_POINT }
 Classification of a point location query result. More...
 

Public Member Functions

Result operator() (const Array< Segment > &input_segments) const
 Build a trapezoidal map from a set of non-crossing segments.
 
Result operator() (const Polygon &polygon) const
 Build a trapezoidal map from a closed polygon's edges.
 
Result operator() (const Array< Polygon > &polygons) const
 Build a trapezoidal map from multiple closed polygons.
 

Static Public Attributes

static constexpr size_t NONE = ~static_cast<size_t>(0)
 

Static Private Member Functions

static bool point_above_segment (const Point &p, const Segment &seg)
 Test if point p is above segment seg (left of the directed segment).
 
static size_t dag_locate (const Array< Point > &pts, const Array< Segment > &segs, const Array< DagNode > &dag, const Point &p, size_t root)
 Locate the DAG leaf (trapezoid) containing point p.
 
static size_t make_trapezoid (Array< Trapezoid > &traps, Array< DagNode > &dag, const size_t top, const size_t bottom, const size_t leftp, const size_t rightp)
 Create a new trapezoid and a DAG leaf for it.
 
static void replace_leaf (Array< DagNode > &dag, const size_t leaf_idx, const NodeType type, const size_t index, const size_t left, const size_t right)
 Replace a DAG leaf with an internal node (X or Y).
 
static void update_neighbor (Array< Trapezoid > &traps, const size_t neighbor_idx, const size_t old_ti, const size_t new_ti)
 Update all neighbor pointers that referenced old_ti to point to new_ti.
 
static Array< size_t > find_crossed_trapezoids (const Array< Point > &pts, const Array< Segment > &segs, const Array< Trapezoid > &traps, const size_t seg_idx, const size_t start_trap)
 Find all trapezoids crossed by segment seg_idx, starting from the trapezoid containing the left endpoint.
 
static void split_single_trapezoid (Array< Point > &pts, Array< Segment > &segs, Array< Trapezoid > &traps, Array< DagNode > &dag, const size_t seg_idx, const size_t trap_idx)
 Handle the case where a segment is fully contained in one trapezoid.
 
static void split_multiple_trapezoids (Array< Point > &pts, Array< Segment > &segs, Array< Trapezoid > &traps, Array< DagNode > &dag, const size_t seg_idx, const Array< size_t > &crossed)
 Handle the case where a segment crosses multiple trapezoids.
 

Detailed Description

O(log n) point location via trapezoidal map with DAG search.

Given a set of non-crossing line segments (or polygon edges), builds a trapezoidal decomposition of the plane using randomized incremental construction (Seidel 1991 / de Berg et al.).

  • Construction: O(n log n) expected time.
  • Query: O(log n) expected time per point.

The result structure stores the trapezoidal map and a directed acyclic graph (DAG) used for point location queries.

Usage

// Build from segments
Array<Segment> segs;
segs.append(Segment(Point(0,0), Point(4,2)));
segs.append(Segment(Point(1,3), Point(5,1)));
TrapezoidalMapPointLocation tm;
auto result = tm(segs);
// Query a point
auto loc = result.locate(Point(2, 1));
if (loc.type == TrapezoidalMapPointLocation::LocationType::TRAPEZOID)
std::cout << "In trapezoid " << loc.trapezoid_index << "\n";
// Build from a polygon
Polygon poly;
poly.add_vertex(Point(0,0));
poly.add_vertex(Point(4,0));
poly.add_vertex(Point(4,4));
poly.add_vertex(Point(0,4));
poly.close();
auto result2 = tm(poly);
bool inside = result2.contains(Point(2, 2)); // true
Aleph::Array
Simple dynamic array with automatic resizing and functional operations.
Definition tpl_array.H:139
Aleph::Array::append
T & append(const T &data)
Append a copy of data
Definition tpl_array.H:245
Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:229
Aleph::Polygon
A general (irregular) 2D polygon defined by a sequence of vertices.
Definition polygon.H:246
Aleph::Polygon::add_vertex
void add_vertex(const Point &point)
Add a vertex to the polygon.
Definition polygon.H:677
Aleph::Polygon::close
void close()
Close the polygon.
Definition polygon.H:840
Aleph::Segment
Represents a line segment between two points.
Definition point.H:827
Aleph::TrapezoidalMapPointLocation
O(log n) point location via trapezoidal map with DAG search.
Definition geom_algorithms.H:12969
Aleph::TrapezoidalMapPointLocation::LocationType::TRAPEZOID
@ TRAPEZOID
The point is strictly inside a trapezoid.
Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Fast point location in planar subdivisions using trapezoidal maps.

This class implements a randomized incremental algorithm to build a trapezoidal decomposition of a set of non-crossing line segments. It provides O(log n) expected query time for point location.

Author
Leandro Rabindranath León
Alejandro J. Mujica

Definition at line 12968 of file geom_algorithms.H.

Member Enumeration Documentation

◆ LocationType

enum class Aleph::TrapezoidalMapPointLocation::LocationType
strong

Classification of a point location query result.

Enumerator
TRAPEZOID 

The point is strictly inside a trapezoid.

ON_SEGMENT 

The point lies on a segment boundary.

ON_POINT 

The point coincides with a segment endpoint.

Definition at line 13017 of file geom_algorithms.H.

◆ NodeType

enum class Aleph::TrapezoidalMapPointLocation::NodeType
strong

Types of nodes in the search DAG.

Enumerator
X_NODE 

A node that splits the search space by an X-coordinate.

Y_NODE 

A node that splits the search space by a segment (Y-direction).

LEAF 

A leaf node representing a trapezoid.

Definition at line 12996 of file geom_algorithms.H.

Member Function Documentation

◆ dag_locate()

static size_t Aleph::TrapezoidalMapPointLocation::dag_locate ( const Array< Point > &  pts,
const Array< Segment > &  segs,
const Array< DagNode > &  dag,
const Point &  p,
size_t  root 
)
inlinestaticprivate

Locate the DAG leaf (trapezoid) containing point p.

Definition at line 13151 of file geom_algorithms.H.

References Aleph::area_of_parallelogram(), Aleph::divide_and_conquer_partition_dp(), LEAF, root(), and X_NODE.

Referenced by operator()().

◆ find_crossed_trapezoids()

static Array< size_t > Aleph::TrapezoidalMapPointLocation::find_crossed_trapezoids ( const Array< Point > &  pts,
const Array< Segment > &  segs,
const Array< Trapezoid > &  traps,
const size_t  seg_idx,
const size_t  start_trap 
)
inlinestaticprivate

Find all trapezoids crossed by segment seg_idx, starting from the trapezoid containing the left endpoint.

Definition at line 13226 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_tgt_point(), Aleph::TrapezoidalMapPointLocation::Trapezoid::lower_right, NONE, point_above_segment(), Aleph::TrapezoidalMapPointLocation::Trapezoid::rightp, and Aleph::TrapezoidalMapPointLocation::Trapezoid::upper_right.

Referenced by operator()().

◆ make_trapezoid()

static size_t Aleph::TrapezoidalMapPointLocation::make_trapezoid ( Array< Trapezoid > &  traps,
Array< DagNode > &  dag,
const size_t  top,
const size_t  bottom,
const size_t  leftp,
const size_t  rightp 
)
inlinestaticprivate

Create a new trapezoid and a DAG leaf for it.

Definition at line 13185 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), LEAF, NONE, and Aleph::Array< T >::size().

Referenced by operator()(), split_multiple_trapezoids(), and split_single_trapezoid().

◆ operator()() [1/3]

Result Aleph::TrapezoidalMapPointLocation::operator() ( const Array< Polygon > &  polygons) const
inline

Build a trapezoidal map from multiple closed polygons.

Parameters
polygonsArray of closed simple polygons (must not overlap).
Returns
Result containing the trapezoidal map and DAG.

Definition at line 13826 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::Segment_Iterator::has_curr(), Aleph::Polygon::is_closed(), Aleph::Polygon::size(), and Aleph::Array< T >::size().

◆ operator()() [2/3]

Result Aleph::TrapezoidalMapPointLocation::operator() ( const Array< Segment > &  input_segments) const
inline

Build a trapezoidal map from a set of non-crossing segments.

Parameters
input_segmentsArray of line segments (must not cross each other except at endpoints).
Returns
Result containing the trapezoidal map and DAG.
Exceptions
domain_errorif any segment is degenerate (src == tgt).

Definition at line 13660 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::Array< T >::append(), dag_locate(), Aleph::divide_and_conquer_partition_dp(), find_crossed_trapezoids(), Aleph::Segment::get_src_point(), Aleph::in_place_sort(), make_trapezoid(), Aleph::TrapezoidalMapPointLocation::Result::num_input_segments, Aleph::Array< T >::reserve(), split_multiple_trapezoids(), and split_single_trapezoid().

◆ operator()() [3/3]

Result Aleph::TrapezoidalMapPointLocation::operator() ( const Polygon &  polygon) const
inline

Build a trapezoidal map from a closed polygon's edges.

Parameters
polygonA closed simple polygon.
Returns
Result containing the trapezoidal map and DAG.

Definition at line 13809 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::Segment_Iterator::has_curr(), Aleph::Polygon::is_closed(), and Aleph::Polygon::size().

◆ point_above_segment()

static bool Aleph::TrapezoidalMapPointLocation::point_above_segment ( const Point &  p,
const Segment &  seg 
)
inlinestaticprivate

Test if point p is above segment seg (left of the directed segment).

Definition at line 13143 of file geom_algorithms.H.

References Aleph::area_of_parallelogram(), Aleph::Segment::get_src_point(), and Aleph::Segment::get_tgt_point().

Referenced by find_crossed_trapezoids().

◆ replace_leaf()

static void Aleph::TrapezoidalMapPointLocation::replace_leaf ( Array< DagNode > &  dag,
const size_t  leaf_idx,
const NodeType  type,
const size_t  index,
const size_t  left,
const size_t  right 
)
inlinestaticprivate

Replace a DAG leaf with an internal node (X or Y).

Definition at line 13200 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by split_multiple_trapezoids(), and split_single_trapezoid().

◆ split_multiple_trapezoids()

static void Aleph::TrapezoidalMapPointLocation::split_multiple_trapezoids ( Array< Point > &  pts,
Array< Segment > &  segs,
Array< Trapezoid > &  traps,
Array< DagNode > &  dag,
const size_t  seg_idx,
const Array< size_t > &  crossed 
)
inlinestaticprivate

Handle the case where a segment crosses multiple trapezoids.

Definition at line 13410 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), make_trapezoid(), NONE, replace_leaf(), Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), update_neighbor(), X_NODE, and Y_NODE.

Referenced by operator()().

◆ split_single_trapezoid()

static void Aleph::TrapezoidalMapPointLocation::split_single_trapezoid ( Array< Point > &  pts,
Array< Segment > &  segs,
Array< Trapezoid > &  traps,
Array< DagNode > &  dag,
const size_t  seg_idx,
const size_t  trap_idx 
)
inlinestaticprivate

Handle the case where a segment is fully contained in one trapezoid.

Definition at line 13270 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), make_trapezoid(), NONE, replace_leaf(), Aleph::Array< T >::size(), update_neighbor(), X_NODE, and Y_NODE.

Referenced by operator()().

◆ update_neighbor()

static void Aleph::TrapezoidalMapPointLocation::update_neighbor ( Array< Trapezoid > &  traps,
const size_t  neighbor_idx,
const size_t  old_ti,
const size_t  new_ti 
)
inlinestaticprivate

Update all neighbor pointers that referenced old_ti to point to new_ti.

Definition at line 13211 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and NONE.

Referenced by split_multiple_trapezoids(), and split_single_trapezoid().

Member Data Documentation

◆ NONE

constexpr size_t Aleph::TrapezoidalMapPointLocation::NONE = ~static_cast<size_t>(0)
staticconstexpr

Definition at line 12971 of file geom_algorithms.H.

Referenced by find_crossed_trapezoids(), Aleph::TrapezoidalMapPointLocation::Result::locate(), make_trapezoid(), Aleph::put_trapezoidal_map_result(), split_multiple_trapezoids(), split_single_trapezoid(), and update_neighbor().

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