Aleph-w: Aleph::MonotonePolygonTriangulation::EdgeStatusTree Class Reference

Aleph-w 3.0

A C++ Library for Data Structures and Algorithms

Loading...

Searching...

No Matches

Collaboration diagram for Aleph::MonotonePolygonTriangulation::EdgeStatusTree:

Classes
struct	Node

Public Member Functions
	EdgeStatusTree (const Array< Point > &verts)

	~EdgeStatusTree ()

bool	contains (const size_t edge) const

void	insert (const size_t edge, const Geom_Number &sweep_y)

void	erase (const size_t edge)

size_t	left_edge_of_point (const Point &p, const Geom_Number &sweep_y) const

Private Member Functions
size_t	predecessor_for_insert (const size_t edge, const Geom_Number &sweep_y) const

size_t	successor_for_insert (const size_t edge, const Geom_Number &sweep_y) const

Geom_Number	fresh_label_between (const size_t pred, const size_t succ) const

Static Private Member Functions
static void	split_by_label (Node root, const Geom_Number &label, Node &left, Node *&right)

static Node *	merge (Node a, Node b)

static Node *	insert_by_label (Node root, Node node)

static Node *	erase_by_label (Node root, const Geom_Number &label, Node &removed)

static void	destroy (const Node *n)

Private Attributes
Node *	root_ = nullptr

const Array< Point > &	verts_

std::mt19937	rng_ {0x31415926u}

Array< Node * >	nodes_

Detailed Description

Definition at line 6599 of file geom_algorithms.H.

Constructor & Destructor Documentation

◆ EdgeStatusTree()

Aleph::MonotonePolygonTriangulation::EdgeStatusTree::EdgeStatusTree ( const Array< Point > & verts )

inlineexplicit

Definition at line 6749 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), nodes_, and Aleph::Array< T >::reserve().

◆ ~EdgeStatusTree()

Aleph::MonotonePolygonTriangulation::EdgeStatusTree::~EdgeStatusTree ( )

inline

Definition at line 6756 of file geom_algorithms.H.

References destroy(), and root_.

Member Function Documentation

◆ contains()

bool Aleph::MonotonePolygonTriangulation::EdgeStatusTree::contains ( const size_t edge ) const

inline

Definition at line 6761 of file geom_algorithms.H.

References nodes_.

Referenced by erase(), and insert().

◆ destroy()

static void Aleph::MonotonePolygonTriangulation::EdgeStatusTree::destroy ( const Node * n )

inlinestaticprivate

Definition at line 6695 of file geom_algorithms.H.

References destroy(), Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::left, and Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::right.

Referenced by ~EdgeStatusTree(), and destroy().

◆ erase()

void Aleph::MonotonePolygonTriangulation::EdgeStatusTree::erase ( const size_t edge )

inline

Definition at line 6782 of file geom_algorithms.H.

References contains(), Aleph::divide_and_conquer_partition_dp(), erase_by_label(), nodes_, and root_.

Referenced by Aleph::MonotonePolygonTriangulation::decompose_to_monotone_faces().

◆ erase_by_label()

static Node * Aleph::MonotonePolygonTriangulation::EdgeStatusTree::erase_by_label	(	Node *	root,
		const Geom_Number &	label,
		Node *&	removed
	)

inlinestaticprivate

Definition at line 6672 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), erase_by_label(), Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::left, merge(), and root().

Referenced by erase(), and erase_by_label().

◆ fresh_label_between()

Geom_Number Aleph::MonotonePolygonTriangulation::EdgeStatusTree::fresh_label_between	(	const size_t	pred,
		const size_t	succ
	)		const

inlineprivate

Definition at line 6737 of file geom_algorithms.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), nodes_, and pred.

Referenced by insert().

◆ insert()

void Aleph::MonotonePolygonTriangulation::EdgeStatusTree::insert	(	const size_t	edge,
		const Geom_Number &	sweep_y
	)

inline

Definition at line 6766 of file geom_algorithms.H.

References contains(), Aleph::divide_and_conquer_partition_dp(), fresh_label_between(), insert_by_label(), nodes_, pred, predecessor_for_insert(), rng_, root_, and successor_for_insert().

Referenced by Aleph::MonotonePolygonTriangulation::decompose_to_monotone_faces().

◆ insert_by_label()

static Node * Aleph::MonotonePolygonTriangulation::EdgeStatusTree::insert_by_label	(	Node *	root,
		Node *	node
	)

inlinestaticprivate

Definition at line 6650 of file geom_algorithms.H.

References insert_by_label(), Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::label, Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::left, Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::priority, Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::right, root(), and split_by_label().

Referenced by insert(), and insert_by_label().

◆ left_edge_of_point()

size_t Aleph::MonotonePolygonTriangulation::EdgeStatusTree::left_edge_of_point	(	const Point &	p,
		const Geom_Number &	sweep_y
	)		const

inline

Definition at line 6793 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::MonotonePolygonTriangulation::edge_x_at_y(), Aleph::Point::get_x(), root_, and verts_.

Referenced by Aleph::MonotonePolygonTriangulation::decompose_to_monotone_faces().

◆ merge()

static Node * Aleph::MonotonePolygonTriangulation::EdgeStatusTree::merge	(	Node *	a,
		Node *	b
	)

inlinestaticprivate

Definition at line 6637 of file geom_algorithms.H.

References Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::left, merge(), Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::priority, and Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::right.

Referenced by erase_by_label(), and merge().

◆ predecessor_for_insert()

size_t Aleph::MonotonePolygonTriangulation::EdgeStatusTree::predecessor_for_insert	(	const size_t	edge,
		const Geom_Number &	sweep_y
	)		const

inlineprivate

Definition at line 6704 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::MonotonePolygonTriangulation::edge_status_less(), pred, root_, and verts_.

Referenced by insert().

◆ split_by_label()

static void Aleph::MonotonePolygonTriangulation::EdgeStatusTree::split_by_label	(	Node *	root,
		const Geom_Number &	label,
		Node *&	left,
		Node *&	right
	)

inlinestaticprivate

Definition at line 6615 of file geom_algorithms.H.

References Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::left, root(), and split_by_label().

Referenced by insert_by_label(), and split_by_label().

◆ successor_for_insert()

size_t Aleph::MonotonePolygonTriangulation::EdgeStatusTree::successor_for_insert	(	const size_t	edge,
		const Geom_Number &	sweep_y
	)		const

inlineprivate

Definition at line 6720 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::MonotonePolygonTriangulation::EdgeStatusTree::Node::edge, Aleph::MonotonePolygonTriangulation::edge_status_less(), root_, and verts_.

Referenced by insert().

Member Data Documentation

◆ nodes_

Array<Node *> Aleph::MonotonePolygonTriangulation::EdgeStatusTree::nodes_

private

Definition at line 6613 of file geom_algorithms.H.

Referenced by EdgeStatusTree(), contains(), erase(), fresh_label_between(), and insert().

◆ rng_

std::mt19937 Aleph::MonotonePolygonTriangulation::EdgeStatusTree::rng_ {0x31415926u}

private

Definition at line 6612 of file geom_algorithms.H.

Referenced by insert().

◆ root_

Node* Aleph::MonotonePolygonTriangulation::EdgeStatusTree::root_ = nullptr

private

Definition at line 6610 of file geom_algorithms.H.

Referenced by ~EdgeStatusTree(), erase(), insert(), left_edge_of_point(), predecessor_for_insert(), and successor_for_insert().

◆ verts_

const Array<Point>& Aleph::MonotonePolygonTriangulation::EdgeStatusTree::verts_

private

Definition at line 6611 of file geom_algorithms.H.

Referenced by left_edge_of_point(), predecessor_for_insert(), and successor_for_insert().

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

geom_algorithms.H