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

Static 2D range tree for orthogonal range queries. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::RangeTree2D:
[legend]

Classes

struct  DebugNode
 Represents a node in the range tree for debugging. More...
 
struct  DebugSnapshot
 A complete snapshot of the range tree for debugging. More...
 
struct  Node
 Internal node structure containing the y-sorted secondary array. More...
 

Public Member Functions

void build (const DynList< Point > &points)
 Build the range tree from a point set.
 
DynList< Point > query (const Geom_Number &xmin, const Geom_Number &xmax, const Geom_Number &ymin, const Geom_Number &ymax) const
 Query: return all points inside [xmin,xmax] × [ymin,ymax].
 
size_t size () const noexcept
 
bool is_empty () const noexcept
 
DebugSnapshot debug_snapshot () const
 Return structural snapshot for visualization/debug.
 

Private Member Functions

size_t lower_bound_x (const Geom_Number &xval) const
 Binary search: first index i in pts_ where pts_(i).get_x() >= xval.
 
size_t upper_bound_x (const Geom_Number &xval) const
 Binary search: first index i in pts_ where pts_(i).get_x() > xval.
 
void build_node (const size_t node, const size_t lo, const size_t hi)
 
void query_range (const size_t node, const size_t lo, const size_t hi, const size_t qlo, const size_t qhi, const Geom_Number &ymin, const Geom_Number &ymax, DynList< Point > &out) const
 

Static Private Member Functions

static size_t lower_bound_y (const Array< Point > &arr, const Geom_Number &ymin)
 Binary search: first index i in arr where arr(i).get_y() >= ymin.
 
static size_t upper_bound_y (const Array< Point > &arr, const Geom_Number &ymax)
 Binary search: first index i in arr where arr(i).get_y() > ymax.
 

Private Attributes

Array< Point > pts_
 points sorted by x (primary key)
 
Array< Node > tree_
 implicit binary tree (1-indexed)
 
size_t n_ = 0
 
bool built_ = false
 

Detailed Description

Static 2D range tree for orthogonal range queries.

Supports axis-aligned rectangle queries: given [xmin,xmax] × [ymin,ymax], find all points inside.

Complexity

  • Build: O(n log n) time, O(n log n) space
  • Query: O(log² n + k) where k = output size
Example
Array<Point> pts;
pts.append(Point(0,0));
pts.append(Point(2,1));
pts.append(Point(3,3));
RangeTree2D rt;
rt.build(pts);
Array<Point> out;
rt.query(0, 0, 2, 2, out);
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::RangeTree2D
Static 2D range tree for orthogonal range queries.
Definition geom_algorithms.H:8604
Aleph::RangeTree2D::build
void build(const DynList< Point > &points)
Build the range tree from a point set.
Definition geom_algorithms.H:8753
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

Definition at line 8603 of file geom_algorithms.H.

Member Function Documentation

◆ build()

void Aleph::RangeTree2D::build ( const DynList< Point > &  points)
inline

Build the range tree from a point set.

Definition at line 8753 of file geom_algorithms.H.

References Aleph::and, build_node(), built_, Aleph::divide_and_conquer_partition_dp(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::HTList::Iterator::has_curr(), n_, pts_, Aleph::quicksort_op(), and tree_.

Referenced by main(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ build_node()

void Aleph::RangeTree2D::build_node ( const size_t  node,
const size_t  lo,
const size_t  hi 
)
inlineprivate

Definition at line 8696 of file geom_algorithms.H.

References Aleph::and, build_node(), Aleph::divide_and_conquer_partition_dp(), pts_, and tree_.

Referenced by build(), and build_node().

◆ debug_snapshot()

DebugSnapshot Aleph::RangeTree2D::debug_snapshot ( ) const
inline

Return structural snapshot for visualization/debug.

Definition at line 8806 of file geom_algorithms.H.

References built_, Aleph::divide_and_conquer_partition_dp(), Aleph::RangeTree2D::DebugNode::hi, Aleph::RangeTree2D::DebugNode::is_leaf, Aleph::RangeTree2D::DebugNode::left, Aleph::RangeTree2D::DebugNode::lo, n_, pts_, Aleph::RangeTree2D::DebugNode::right, Aleph::RangeTree2D::DebugNode::split_x, tree_, Aleph::RangeTree2D::DebugNode::tree_index, Aleph::RangeTree2D::DebugSnapshot::x_sorted_points, Aleph::RangeTree2D::DebugNode::xmax, Aleph::RangeTree2D::DebugNode::xmin, and Aleph::RangeTree2D::DebugNode::y_sorted_size.

Referenced by TEST_F(), Aleph::visualize_range_tree(), and Aleph::visualize_range_tree_query().

◆ is_empty()

bool Aleph::RangeTree2D::is_empty ( ) const
inlinenoexcept

Definition at line 8803 of file geom_algorithms.H.

References n_.

Referenced by TEST_F().

◆ lower_bound_x()

size_t Aleph::RangeTree2D::lower_bound_x ( const Geom_Number &  xval) const
inlineprivate

Binary search: first index i in pts_ where pts_(i).get_x() >= xval.

Definition at line 8673 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), n_, and pts_.

Referenced by query().

◆ lower_bound_y()

static size_t Aleph::RangeTree2D::lower_bound_y ( const Array< Point > &  arr,
const Geom_Number &  ymin 
)
inlinestaticprivate

Binary search: first index i in arr where arr(i).get_y() >= ymin.

Definition at line 8647 of file geom_algorithms.H.

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

Referenced by query_range().

◆ query()

DynList< Point > Aleph::RangeTree2D::query ( const Geom_Number &  xmin,
const Geom_Number &  xmax,
const Geom_Number &  ymin,
const Geom_Number &  ymax 
) const
inline

Query: return all points inside [xmin,xmax] × [ymin,ymax].

Definition at line 8783 of file geom_algorithms.H.

References built_, Aleph::divide_and_conquer_partition_dp(), lower_bound_x(), n_, query_range(), and upper_bound_x().

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and Aleph::visualize_range_tree_query().

◆ query_range()

void Aleph::RangeTree2D::query_range ( const size_t  node,
const size_t  lo,
const size_t  hi,
const size_t  qlo,
const size_t  qhi,
const Geom_Number &  ymin,
const Geom_Number &  ymax,
DynList< Point > &  out 
) const
inlineprivate

Definition at line 8728 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), lower_bound_y(), query_range(), tree_, and upper_bound_y().

Referenced by query(), and query_range().

◆ size()

size_t Aleph::RangeTree2D::size ( ) const
inlinenoexcept

Definition at line 8801 of file geom_algorithms.H.

References n_.

Referenced by TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ upper_bound_x()

size_t Aleph::RangeTree2D::upper_bound_x ( const Geom_Number &  xval) const
inlineprivate

Binary search: first index i in pts_ where pts_(i).get_x() > xval.

Definition at line 8685 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), n_, and pts_.

Referenced by query().

◆ upper_bound_y()

static size_t Aleph::RangeTree2D::upper_bound_y ( const Array< Point > &  arr,
const Geom_Number &  ymax 
)
inlinestaticprivate

Binary search: first index i in arr where arr(i).get_y() > ymax.

Definition at line 8660 of file geom_algorithms.H.

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

Referenced by query_range().

Member Data Documentation

◆ built_

bool Aleph::RangeTree2D::built_ = false
private

Definition at line 8644 of file geom_algorithms.H.

Referenced by build(), debug_snapshot(), and query().

◆ n_

size_t Aleph::RangeTree2D::n_ = 0
private

Definition at line 8643 of file geom_algorithms.H.

Referenced by build(), debug_snapshot(), is_empty(), lower_bound_x(), query(), size(), and upper_bound_x().

◆ pts_

Array<Point> Aleph::RangeTree2D::pts_
private

points sorted by x (primary key)

Definition at line 8641 of file geom_algorithms.H.

Referenced by build(), build_node(), debug_snapshot(), lower_bound_x(), and upper_bound_x().

◆ tree_

Array<Node> Aleph::RangeTree2D::tree_
private

implicit binary tree (1-indexed)

Definition at line 8642 of file geom_algorithms.H.

Referenced by build(), build_node(), debug_snapshot(), and query_range().

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