Namespaces
namespace	detail

Classes
class	ClockTreeVisualizer
	Visualizes clock trees in SVG format. More...

class	DelayCalculator
	Abstract base class for delay calculation models. More...

class	DMEAlgorithm
	Implements the Deferred Merge Embedding (DME) algorithm for clock tree synthesis. More...

class	ElmoreDelayCalculator
	Implements the Elmore delay model for RC trees. More...

class	GlobalRouter
	Manages the global routing process, constructing a GlobalRoutingTree. More...

class	GlobalRoutingTree
	Represents the entire global routing tree. More...

struct	HSegment
	Horizontal Line Segment. More...

class	Interval
	Interval. More...

class	LinearDelayCalculator
	Implements a simple linear delay model. More...

class	ManhattanArc
	Merging Object (for deferred-merge embedding (DME) algorithm) More...

class	Point
	Point. More...

class	Polygon
	Polygon. More...

struct	Rectangle
	Rectangle (Rectilinear) More...

class	RoutingNode
	Represents a node in the global routing tree. More...

class	RPolygon

class	RPolygonVertexIterator
	Rectilinear Polygon. More...

class	Sink
	Represents a clock sink in the clock tree network. More...

struct	SkewAnalysis
	Stores the results of the clock skew analysis for a clock tree. More...

struct	TappingResult
	Result of a tapping-point calculation. More...

class	Tree
	Arena-allocated tree of `TreeNode`s. More...

struct	TreeComparisonData

class	TreeNode
	A node in the clock tree, stored in a `Tree` arena. More...

struct	TreeStatistics
	Provides detailed statistics about the generated clock tree. More...

class	Vector2
	2D vector template class. More...

struct	VSegment
	Vertical Line Segment. More...

Typedefs
using	NodeIdx = std::size_t
	Node index type used throughout the DME algorithm.

Enumerations
enum class	NodeType { Steiner , Terminal , Source }
	Defines the type of a routing node. More...

Functions
TreeStatistics	get_tree_statistics (const Tree &tree, NodeIdx root)
	Extracts detailed statistics from a constructed clock tree.

void	example_dme_usage ()
	Example usage function demonstrating the DME algorithm with different delay models.

template<typename T >
constexpr auto	my_abs (const T &value) -> T
	Compute the absolute value of a number.

template<typename U1 , typename U2 >
constexpr auto	overlap (const U1 &lhs, const U2 &rhs) -> bool
	Checks if two objects overlap.

template<typename U1 , typename U2 >
constexpr auto	contain (const U1 &lhs, const U2 &rhs) -> bool
	Check if one object contains another object.

template<typename U1 , typename U2 >
constexpr auto	intersection (const U1 &lhs, const U2 &rhs)
	Computes the intersection of two objects.

template<typename U1 , typename U2 >
constexpr auto	min_dist (const U1 &lhs, const U2 &rhs)
	Calculates the minimum distance between two objects `lhs` and `rhs`.

template<typename U1 , typename U2 >
constexpr auto	min_dist_change (U1 &lhs, U2 &rhs)
	Calculates the minimum distance between two objects `lhs` and `rhs`, with the ability to handle a change in the objects.

template<typename U1 , typename U2 >
constexpr auto	nearest (const U1 &lhs, const U2 &rhs)
	Returns the nearest point on `lhs` to `rhs`.

template<typename U >
constexpr auto	measure_of (const U &obj)
	Calculates the measure (length, area, etc.) of an object.

template<typename U >
constexpr auto	center (const U &obj)
	Calculates the center of an object.

template<typename U >
constexpr auto	lower (const U &obj)
	Calculates the lower corner of an object.

template<typename U >
constexpr auto	upper (const U &obj)
	Calculates the upper corner of an object.

std::string	to_string (const NodeType routing_node_type)
	Converts a NodeType enum value to its string representation.

template<typename IntPoint >
std::string	visualize_routing_tree_svg (const GlobalRoutingTree< IntPoint > &tree, std::optional< std::vector< typename GlobalRoutingTree< IntPoint >::Keepout > > keepouts=std::nullopt, const int width=800, const int height=600, const int margin=50)

template<typename IntPoint >
void	save_routing_tree_svg (const GlobalRoutingTree< IntPoint > &tree, std::optional< std::vector< typename GlobalRoutingTree< IntPoint >::Keepout > > keepouts=std::nullopt, const std::string &filename="routing_tree.svg", const int width=800, const int height=600)

template<typename IntPoint >
std::string	visualize_routing_tree3d_svg (const GlobalRoutingTree< IntPoint > &tree, std::optional< std::vector< typename GlobalRoutingTree< IntPoint >::Keepout > > keepouts=std::nullopt, const int scale_z=100, const int width=800, const int height=600, const int margin=50)

template<typename IntPoint >
void	save_routing_tree3d_svg (const GlobalRoutingTree< IntPoint > &tree, std::optional< std::vector< typename GlobalRoutingTree< IntPoint >::Keepout > > keepouts=std::nullopt, const int scale_z=100, const std::string &filename="routing_tree3d.svg", const int width=800, const int height=600)

template<typename U1 , typename U2 >
constexpr auto	hull (const U1 &left, const U2 &right)
	Computes the hull of two objects.

template<typename U1 , typename U2 >
constexpr auto	enlarge (const U1 &left, const U2 &right)
	Enlarges an interval or scalar value by adding and subtracting a given value.

void	log_with_spdlog (const std::string &message)
	Log a message using spdlog.

template<typename FwIter >
auto	create_xmono_polygon (FwIter first, FwIter last) -> void
	Create a xmono Polygon object.

template<typename FwIter >
auto	create_ymono_polygon (FwIter first, FwIter last) -> void
	Create a ymono Polygon object.

template<typename T , typename DirFunc >
auto	polygon_is_monotone (std::span< const Point< T > > pointset, const DirFunc &dir) -> bool
	Check if a polygon is monotone with respect to a given direction function.

template<typename T >
auto	polygon_is_xmonotone (std::span< const Point< T > > pointset) -> bool
	Check if a polygon is x-monotone.

template<typename T >
auto	polygon_is_ymonotone (std::span< const Point< T > > pointset) -> bool
	Check if a polygon is y-monotone.

template<typename T >
auto	point_in_polygon (std::span< const Point< T > > pointset, const Point< T > &ptq) -> bool
	Determine if a point is within a polygon.

template<typename T >
auto	polygon_is_anticlockwise (std::span< const Point< T > > pointset) -> bool
	Determines if a polygon represented by a range of points is oriented anticlockwise.

template<typename Container >
constexpr auto	detect_overlap (const Container &rectangles) -> std::optional< std::pair< typename Container::value_type, typename Container::value_type > >
	Detect if any pair of rectangles overlap using the line sweep algorithm.

template<typename FwIter , typename KeyFn , typename CmpFn >
auto	create_mono_rpolygon (FwIter &&first, FwIter &&last, const KeyFn &dir, const CmpFn &cmp) -> bool
	Create a x-monotone rectilinear polygon (RPolygon) object.

template<typename FwIter >
auto	create_xmono_rpolygon (FwIter &&first, FwIter &&last) -> bool
	Create a x-monotone rectilinear polygon (RPolygon) object.

template<typename FwIter >
auto	create_ymono_rpolygon (FwIter &&first, FwIter &&last) -> bool
	Create a y-monotone rectilinear polygon (RPolygon) object.

template<typename FwIter >
void	create_test_rpolygon_old (FwIter &&first, FwIter &&last)
	Create a test rectilinear polygon (RPolygon) object.

template<typename FwIter >
auto	create_test_rpolygon (FwIter first, FwIter last) -> std::vector< typename std::iterator_traits< FwIter >::value_type >
	Create a test rectilinear polygon (RPolygon) object.

template<typename T >
auto	rpolygon_is_xmonotone (std::span< const Point< T > > pointset) -> bool
	Check if a polygon is x-monotone.

template<typename T >
auto	rpolygon_is_ymonotone (std::span< const Point< T > > pointset) -> bool
	Check if a polygon is y-monotone.

template<typename T >
auto	rpolygon_is_convex (std::span< const Point< T > > pointset) -> bool
	Check if a polygon is convex.

template<typename T >
auto	point_in_rpolygon (std::span< const Point< T > > pointset, const Point< T > &query_point) -> bool
	Determine if a point is within a rectilinear polygon.

template<typename T >
auto	rpolygon_is_anticlockwise (std::span< const Point< T > > pointset) -> bool
	Determine if a rectilinear polygon is oriented clockwise.

template<typename T , typename Cmp >
auto	rpolygon_cut_convex_recur (Dllink< size_t > *v1, std::vector< Point< T > > &lst, const Cmp &cmp, RDllist &rdll) -> std::vector< std::vector< size_t > >
	Recursive function for convex decomposition.

template<typename T , typename Cmp >
auto	rpolygon_cut_explicit_recur (Dllink< size_t > *v1, std::vector< Point< T > > &lst, const Cmp &cmp, RDllist &rdll) -> std::vector< std::vector< size_t > >
	Recursive function for explicit decomposition.

template<typename T , typename Cmp >
auto	rpolygon_cut_implicit_recur (Dllink< size_t > *v1, std::vector< Point< T > > &lst, const Cmp &cmp, RDllist &rdll) -> std::vector< std::vector< size_t > >
	Recursive function for implicit decomposition.

template<typename T >
auto	rpolygon_cut_convex (std::span< const Point< T > > pointset, bool is_anticlockwise) -> std::vector< std::vector< Point< T > > >
	Cut a rectilinear polygon into convex pieces.

template<typename T >
auto	rpolygon_cut_explicit (std::span< const Point< T > > pointset, bool is_anticlockwise) -> std::vector< std::vector< Point< T > > >
	Cut a polygon into explicit pieces.

template<typename T >
auto	rpolygon_cut_implicit (std::span< const Point< T > > pointset, bool is_anticlockwise) -> std::vector< std::vector< Point< T > > >
	Cut a convex polygon into pieces according to the implicit vertices.

template<typename T >
auto	rpolygon_cut_rectangle (std::span< const Point< T > > pointset, bool is_anticlockwise) -> std::vector< std::vector< Point< T > > >
	Cut a convex polygon into rectangle pieces.

template<typename T >
auto	rpolygon_make_monotone_hull (std::span< const Point< T > > pointset, bool is_anticlockwise, const std::function< std::pair< T, T >(const Point< T > &)> &dir) -> std::vector< Point< T > >
	Create a monotone hull from a rectilinear polygon with custom direction.

template<typename T >
auto	rpolygon_make_xmonotone_hull (std::span< const Point< T > > pointset, bool is_anticlockwise) -> std::vector< Point< T > >
	Create an x-monotone hull from a rectilinear polygon.

template<typename T >
auto	rpolygon_make_ymonotone_hull (std::span< const Point< T > > pointset, bool is_anticlockwise) -> std::vector< Point< T > >
	Create a y-monotone hull from a rectilinear polygon.

template<typename T >
auto	rpolygon_make_convex_hull (std::span< const Point< T > > pointset, bool is_anticlockwise) -> std::vector< Point< T > >
	Create a convex hull from a rectilinear polygon.

template<typename T >
constexpr auto	to_polygon (const RPolygon< T > &rpoly) -> Polygon< T >
	Converts a rectilinear polygon to a general polygon.

std::string	create_interactive_svg (const Tree &tree, NodeIdx root, const std::vector< Sink > &sinks, const SkewAnalysis *analysis=nullptr, const std::string &filename="clock_tree_interactive.svg", int width=1000, int height=700)

std::string	create_comparison_visualization (const std::vector< TreeComparisonData > &trees_data, const std::string &filename="clock_tree_comparison.svg", int width=1200, int height=800)

std::string	create_delay_model_comparison (const TreeComparisonData &linear_tree_data, const TreeComparisonData &elmore_tree_data, const std::string &filename="delay_model_comparison.svg")

void	visualize_example_tree ()

Typedef Documentation

◆ NodeIdx

using recti::NodeIdx = typedef std::size_t

Node index type used throughout the DME algorithm.

Nodes are stored in an arena-allocated Tree and referenced by NodeIdx (like Rust's usize). SIZE_MAX serves as the null sentinel (equivalent to Rust's None).

Enumeration Type Documentation

◆ NodeType

enum class recti::NodeType

strong

Defines the type of a routing node.

Enumerator
Steiner	A Steiner point, an intermediate point added to optimize routing.
Terminal	A terminal point, representing a pin or a component connection.
Source	The source point of the routing tree.

Function Documentation

◆ center()

template<typename U >

constexpr auto recti::center ( const U & obj )

constexpr

Calculates the center of an object.

This function returns the center of obj. If obj has a get_center member function, it is used. Otherwise, it assumes obj is a scalar and returns it directly.

Template Parameters

U	Type of the object.

Parameters

[in] obj The object to find the center of.

Returns: The center of the object.

◆ contain()

template<typename U1 , typename U2 >

constexpr auto recti::contain	(	const U1 &	lhs,
		const U2 &	rhs
	)		-> bool

constexpr

Check if one object contains another object.

This function checks if the first object lhs contains the second object rhs. It first checks if lhs has a contains member function that can be called with rhs as an argument, and returns the result of that call. If lhs does not have a contains member function, it checks if rhs has a contains member function that can be called with lhs as an argument, and returns false if that is the case (since rhs contains lhs implies that lhs does not contain rhs). If neither object has a contains member function, the function simply checks if the two objects are equal and returns the result.

*     .---------------------.
*     |            .--.     |
*     | .  | ----  |  |     |
*     |            `--'     |
*     `---------------------'
*

Template Parameters

U1	The type of the first object.
U2	The type of the second object.

Parameters

lhs	The first object to check for containment.
rhs	The second object to check for containment.

Returns: true if the first object contains the second object, false otherwise.

◆ create_comparison_visualization()

std::string recti::create_comparison_visualization	(	const std::vector< TreeComparisonData > &	trees_data,
		const std::string &	filename = `"clock_tree_comparison.svg"`,
		int	width = `1200`,
		int	height = `800`
	)

◆ create_delay_model_comparison()

std::string recti::create_delay_model_comparison	(	const TreeComparisonData &	linear_tree_data,
		const TreeComparisonData &	elmore_tree_data,
		const std::string &	filename = `"delay_model_comparison.svg"`
	)

◆ create_interactive_svg()

std::string recti::create_interactive_svg	(	const Tree &	tree,
		NodeIdx	root,
		const std::vector< Sink > &	sinks,
		const SkewAnalysis *	analysis = `nullptr`,
		const std::string &	filename = `"clock_tree_interactive.svg"`,
		int	width = `1000`,
		int	height = `700`
	)

◆ create_mono_rpolygon()

template<typename FwIter , typename KeyFn , typename CmpFn >

auto recti::create_mono_rpolygon	(	FwIter &&	first,
		FwIter &&	last,
		const KeyFn &	dir,
		const CmpFn &	cmp
	)		-> bool

Create a x-monotone rectilinear polygon (RPolygon) object.

This function takes a range of points represented by iterators first and last, and a key function dir that extracts the x and y coordinates of each point. It then creates an monotone RPolygon object from the given points.

Template Parameters

FwIter	The iterator type for the range of points.
KeyFn	The type of the key function that extracts the x and y coordinates of each point.
CmpFn	The type of the comparison function for the y-coordinates.

Parameters

[in]	first	The beginning of the range of points.
[in]	last	The end of the range of points.
[in]	dir	The key function that extracts the x and y coordinates of each point.
[in]	cmp	The comparison function for the y-coordinates.

Returns: true if the resulting RPolygon is anti-clockwise, false otherwise.

◆ create_test_rpolygon()

template<typename FwIter >

auto recti::create_test_rpolygon	(	FwIter	first,
		FwIter	last
	)		-> std::vector< typename std::iterator_traits< FwIter >::value_type >

Create a test rectilinear polygon (RPolygon) object.

This function takes a range of points represented by iterators first and last, and creates a test RPolygon object from the given points. The resulting RPolygon is either clockwise or anti-clockwise depending on the relative positions of the points.

Template Parameters

FwIter The iterator type for the range of points.

Parameters

[in]	first	The beginning of the range of points.
[in]	last	The end of the range of points.

Returns: A vector of points representing the test rectilinear polygon.

◆ create_test_rpolygon_old()

template<typename FwIter >

void recti::create_test_rpolygon_old	(	FwIter &&	first,
		FwIter &&	last
	)

Create a test rectilinear polygon (RPolygon) object.

This function takes a range of points represented by iterators first and last, and creates a test RPolygon object from the given points. The resulting RPolygon is either clockwise or anti-clockwise depending on the relative positions of the points.

Template Parameters

FwIter The iterator type for the range of points.

Parameters

[in]	first	The beginning of the range of points.
[in]	last	The end of the range of points.

◆ create_xmono_polygon()

template<typename FwIter >

auto recti::create_xmono_polygon	(	FwIter	first,
		FwIter	last
	)		-> void

Create a xmono Polygon object.

This function creates a monotone polygon from a range of points represented by the iterators first and last. It uses a comparison function that compares the points based on their x and y coordinates.

Template Parameters

FwIter The type of the forward iterator over the points.

Parameters

[in]	first	The beginning of the range of points.
[in]	last	The end of the range of points.

◆ create_xmono_rpolygon()

template<typename FwIter >

auto recti::create_xmono_rpolygon	(	FwIter &&	first,
		FwIter &&	last
	)		-> bool

Create a x-monotone rectilinear polygon (RPolygon) object.

This function takes a range of points represented by iterators first and last, and creates an x-monotone RPolygon object from the given points.

Template Parameters

FwIter The iterator type for the range of points.

Parameters

[in]	first	The beginning of the range of points.
[in]	last	The end of the range of points.

Returns: true if the resulting RPolygon is anti-clockwise, false otherwise.

◆ create_ymono_polygon()

template<typename FwIter >

auto recti::create_ymono_polygon	(	FwIter	first,
		FwIter	last
	)		-> void

Create a ymono Polygon object.

This function creates a monotone polygon from a range of points represented by the iterators first and last. It uses a comparison function that compares the points based on their y and x coordinates.

Template Parameters

FwIter The type of the forward iterator over the points.

Parameters

[in]	first	The beginning of the range of points.
[in]	last	The end of the range of points.

◆ create_ymono_rpolygon()

template<typename FwIter >

auto recti::create_ymono_rpolygon	(	FwIter &&	first,
		FwIter &&	last
	)		-> bool

Create a y-monotone rectilinear polygon (RPolygon) object.

This function takes a range of points represented by iterators first and last, and creates an y-monotone RPolygon object from the given points.

Template Parameters

FwIter The iterator type for the range of points.

Parameters

[in]	first	The beginning of the range of points.
[in]	last	The end of the range of points.

Returns: true if the resulting RPolygon is clockwise, false otherwise.

◆ detect_overlap()

template<typename Container >

constexpr auto recti::detect_overlap ( const Container & rectangles ) -> std::optional< std::pair<typename Container::value_type, typename Container::value_type>>

constexpr

Detect if any pair of rectangles overlap using the line sweep algorithm.

The algorithm uses a sweep line approach:

Create events for left and right edges of each rectangle
Sort events by x-coordinate
Sweep from left to right, maintaining active rectangles
Check y-overlap when a new rectangle becomes active

Template Parameters

Container A container of Rectangle objects (e.g., std::vector<Rectangle<int>>)

Parameters

rectangles The list of rectangles to check for overlaps

Returns: A pair of overlapping rectangles if found, otherwise std::nullopt

◆ enlarge()

template<typename U1 , typename U2 >

constexpr auto recti::enlarge	(	const U1 &	left,
		const U2 &	right
	)

constexpr

Enlarges an interval or scalar value by adding and subtracting a given value.

This function takes two parameters, left and right, and returns a new interval that is enlarged by the value of right. If left has an enlarge_with member function, it is used to enlarge the interval. Otherwise, a new interval is created with the lower bound as left - right and the upper bound as left + right.

Template Parameters

U1	The type of the first parameter `left`.
U2	The type of the second parameter `right`.

Parameters

left	The interval or scalar value to be enlarged.
right	The value to enlarge the interval or scalar value by.

Returns: The enlarged interval or scalar value.

◆ example_dme_usage()

void recti::example_dme_usage ( )

extern

Example usage function demonstrating the DME algorithm with different delay models.

Sets up a sample clock tree synthesis problem with multiple sinks, applies the DME algorithm using both Linear and Elmore delay models, and prints the skew analysis results for each.

◆ get_tree_statistics()

TreeStatistics recti::get_tree_statistics	(	const Tree &	tree,
		NodeIdx	root
	)

Extracts detailed statistics from a constructed clock tree.

Traverses the clock tree and gathers comprehensive information about its nodes, wires, and overall structure, populating a TreeStatistics object.

Parameters

tree	The arena-allocated tree.
root	The root node index.

◆ hull()

template<typename U1 , typename U2 >

constexpr auto recti::hull	(	const U1 &	left,
		const U2 &	right
	)

constexpr

Computes the hull of two objects.

This function computes the hull of the two input objects left and right. It first checks if left has an hull_with member function that can be called with right as an argument, and returns the result of that call. If left does not have an hull_with member function, it checks if right has an hull_with member function that can be called with left as an argument, and returns the result of that call. If neither object has an hull_with member function, the function asserts that left and right are equal and returns left.

Template Parameters

U1	The type of the first object.
U2	The type of the second object.

Parameters

[in]	left	The first object.
[in]	right	The second object.

Returns: The hull of left and right.

◆ intersection()

template<typename U1 , typename U2 >

constexpr auto recti::intersection	(	const U1 &	lhs,
		const U2 &	rhs
	)

constexpr

Computes the intersection of two objects.

This function computes the intersection of the two input objects lhs and rhs. It first checks if lhs has an intersect_with member function that can be called with rhs as an argument, and returns the result of that call. If lhs does not have an intersect_with member function, it checks if rhs has an intersect_with member function that can be called with lhs as an argument, and returns the result of that call. If neither object has an intersect_with member function, the function asserts that lhs and rhs are equal and returns lhs.

*     .---------------------.
*     |                     |
*     |            .--------+-------.
*     |            |        |       |
*     `------------+--------'       |
*                  |                |
*                  `----------------'
*

Template Parameters

U1	The type of the first object.
U2	The type of the second object.

Parameters

[in]	lhs	The first object.
[in]	rhs	The second object.

Returns: The intersection of lhs and rhs.

◆ log_with_spdlog()

void recti::log_with_spdlog ( const std::string & message )

Log a message using spdlog.

This function provides a simple wrapper around spdlog for logging messages. It creates a file logger that writes to "recti.log" and logs at the info level.

Parameters

message The message to log

◆ lower()

template<typename U >

constexpr auto recti::lower ( const U & obj )

constexpr

Calculates the lower corner of an object.

This function returns the lower corner of obj. If obj has a lower_corner member function, it is used. Otherwise, it assumes obj is a scalar and returns it directly.

Template Parameters

U	Type of the object.

Parameters

[in] obj The object to find the lower corner of.

Returns: The lower corner of the object.

◆ measure_of()

template<typename U >

constexpr auto recti::measure_of ( const U & obj )

constexpr

Calculates the measure (length, area, etc.) of an object.

This function returns the measure of obj. If obj has a measure member function, it is used. Otherwise, it returns 1.

Template Parameters

U	Type of the object.

Parameters

[in] obj The object to measure.

Returns: The measure of the object.

◆ min_dist()

template<typename U1 , typename U2 >

constexpr auto recti::min_dist	(	const U1 &	lhs,
		const U2 &	rhs
	)

constexpr

Calculates the minimum distance between two objects lhs and rhs.

*     .-----------.
*     |           |
*     |           |~~~~~.-------------.
*     |           |     |             |
*     `-----------'     |             |
*                       |             |
*                       `-------------'
*

The function first checks if lhs has a min_dist_with member function that can be called with rhs as an argument, and returns the result of that call. If lhs does not have a min_dist_with member function, it checks if rhs has a min_dist_with member function that can be called with lhs as an argument, and returns the result of that call. If neither object has a min_dist_with member function, the function returns the absolute difference between lhs and rhs.

Template Parameters

U1	The type of the first object.
U2	The type of the second object.

Parameters

[in]	lhs	The first object.
[in]	rhs	The second object.

Returns: The minimum distance between lhs and rhs.

◆ min_dist_change()

template<typename U1 , typename U2 >

constexpr auto recti::min_dist_change	(	U1 &	lhs,
		U2 &	rhs
	)

constexpr

Calculates the minimum distance between two objects lhs and rhs, with the ability to handle a change in the objects.

The function first checks if lhs has a min_dist_change_with member function that can be called with rhs as an argument, and returns the result of that call. If lhs does not have a min_dist_change_with member function, it checks if rhs has a min_dist_change_with member function that can be called with lhs as an argument, and returns the result of that call. If neither object has a min_dist_change_with member function, the function returns the absolute difference between lhs and rhs.

Template Parameters

U1	The type of the first object.
U2	The type of the second object.

Parameters

[in]	lhs	The first object.
[in]	rhs	The second object.

Returns: The minimum distance between lhs and rhs, with the ability to handle a change in the objects.

◆ my_abs()

template<typename T >

constexpr auto recti::my_abs ( const T & value ) -> T

constexpr

Compute the absolute value of a number.

Returns the absolute (non-negative) value of the input. Unlike std::abs, this function works for any type supporting comparison against zero and unary negation.

Template Parameters

T	The type of the value.

Parameters

[in] value The input value.

Returns: The absolute value of the input.

◆ nearest()

template<typename U1 , typename U2 >

constexpr auto recti::nearest	(	const U1 &	lhs,
		const U2 &	rhs
	)

constexpr

Returns the nearest point on lhs to rhs.

*     .---------------------.
*     |                     *~~~~~~~~~~~o rhs
*     |                     |
*     |                     |
*     `---------------------'
*         lhs
*

This function returns the point on lhs that is nearest to rhs. If lhs has a nearest_to member function, it is used. Otherwise, it assumes lhs is a scalar and returns it directly.

Template Parameters

U1	Type of the first object.
U2	Type of the second object.

Parameters

[in]	lhs	The object to find the nearest point on.
[in]	rhs	The reference point.

Returns: The nearest point on lhs to rhs.

◆ overlap()

template<typename U1 , typename U2 >

constexpr auto recti::overlap	(	const U1 &	lhs,
		const U2 &	rhs
	)		-> bool

constexpr

Checks if two objects overlap.

This function checks if the two input objects lhs and rhs overlap with each other. It first checks if the lhs object has an overlaps member function that can be called with rhs as an argument. If so, it calls that function and returns the result. If not, it checks if the rhs object has an overlaps member function that can be called with lhs as an argument, and returns the result of that call. If neither object has an overlaps member function, the function simply checks if the two objects are equal and returns the result.

*     .---------------------.
*     |                     |
*     |            .--------+-------.
*     |            |        |       |
*     `------------+--------'       |
*                  |                |
*                  `----------------'
*

Template Parameters

U1	The type of the first object.
U2	The type of the second object.

Parameters

lhs	The first object to check for overlap.
rhs	The second object to check for overlap.

Returns: true if the two objects overlap, false otherwise.

◆ point_in_polygon()

template<typename T >

auto recti::point_in_polygon	(	std::span< const Point< T > >	pointset,
		const Point< T > &	ptq
	)		-> bool

Determine if a point is within a polygon.

This function determines whether a given point is strictly inside, strictly outside, or on the boundary of a polygon represented by a range of points. It uses the Winding Number algorithm to make this determination.

The code below is from Wm. Randolph Franklin wrf@e.nosp@m.cse..nosp@m.rpi.e.nosp@m.du (see URL below) with some minor modifications for integer. It returns true for strictly interior points, false for strictly exterior, and ub for points on the boundary. The boundary behavior is complex but determined; in particular, for a partition of a region into polygons, each Point is "in" exactly one Polygon. (See p.243 of [O'Rourke (C)] for a discussion of boundary behavior.)

See http://www.faqs.org/faqs/graphics/algorithms-faq/ Subject 2.03

Template Parameters

T	The type of the coordinates of the points in the polygon

Parameters

pointset	The range of points representing the polygon
ptq	The point to test

Returns: true if the point is strictly inside the polygon, false if the point is strictly outside the polygon

◆ point_in_rpolygon()

template<typename T >

auto recti::point_in_rpolygon	(	std::span< const Point< T > >	pointset,
		const Point< T > &	query_point
	)		-> bool

Determine if a point is within a rectilinear polygon.

This function implements the Wm. Randolph Franklin algorithm to determine if a given point is strictly inside, strictly outside, or on the boundary of a rectilinear polygon defined by the provided set of points.

See http://www.faqs.org/faqs/graphics/algorithms-faq/ Subject 2.03

Template Parameters

T	The numeric type of the point coordinates.

Parameters

pointset	The set of points defining the rectilinear polygon.
query_point	The point to test for inclusion in the polygon.

Returns: true if the point is strictly inside the polygon, false if the point is strictly outside the polygon, and an unspecified boolean value if the point is on the boundary of the polygon.

◆ polygon_is_anticlockwise()

template<typename T >

auto recti::polygon_is_anticlockwise ( std::span< const Point< T > > pointset ) -> bool

Determines if a polygon represented by a range of points is oriented anticlockwise.

Template Parameters

T	The type of the coordinates of the points in the polygon.

Parameters

pointset The range of points representing the polygon.

Returns: true if the polygon is oriented anti-clockwise, false otherwise.

◆ polygon_is_monotone()

template<typename T , typename DirFunc >

auto recti::polygon_is_monotone	(	std::span< const Point< T > >	pointset,
		const DirFunc &	dir
	)		-> bool

Check if a polygon is monotone with respect to a given direction function.

A polygon is monotone with respect to a direction if it can be divided into two chains that are both monotone (either entirely non-decreasing or non-increasing) in that direction.

Template Parameters

T	The type of the coordinates
DirFunc	The type of the direction function

Parameters

pointset	The polygon vertices as points
dir	The direction function that returns a key for comparison

Returns: true if the polygon is monotone, false otherwise

◆ polygon_is_xmonotone()

template<typename T >

auto recti::polygon_is_xmonotone ( std::span< const Point< T > > pointset ) -> bool

Check if a polygon is x-monotone.

A polygon is x-monotone if it can be divided into two chains that are both monotone with respect to the x-axis.

Template Parameters

T	The type of the coordinates

Parameters

pointset The polygon vertices as points

Returns: true if the polygon is x-monotone, false otherwise

◆ polygon_is_ymonotone()

template<typename T >

auto recti::polygon_is_ymonotone ( std::span< const Point< T > > pointset ) -> bool

Check if a polygon is y-monotone.

A polygon is y-monotone if it can be divided into two chains that are both monotone with respect to the y-axis.

Template Parameters

T	The type of the coordinates

Parameters

pointset The polygon vertices as points

Returns: true if the polygon is y-monotone, false otherwise

◆ rpolygon_cut_convex()

template<typename T >

auto recti::rpolygon_cut_convex	(	std::span< const Point< T > >	pointset,
		bool	is_anticlockwise
	)		-> std::vector< std::vector< Point< T > > >

Cut a rectilinear polygon into convex pieces.

This function takes a rectilinear polygon defined by a set of points and decomposes it into convex polygons using a recursive algorithm. The algorithm finds concave vertices and inserts new vertices to create convex pieces.

Template Parameters

T	The numeric type for coordinates

Parameters

[in]	pointset	Span of points defining the polygon vertices
[in]	is_anticlockwise	Whether the polygon is oriented anti-clockwise

Returns: std::vector<std::vector<Point<T>>> A vector of convex polygon pieces, each defined by points

◆ rpolygon_cut_convex_recur()

template<typename T , typename Cmp >

auto recti::rpolygon_cut_convex_recur	(	Dllink< size_t > *	v1,
		std::vector< Point< T > > &	lst,
		const Cmp &	cmp,
		RDllist &	rdll
	)		-> std::vector< std::vector< size_t > >

Recursive function for convex decomposition.

◆ rpolygon_cut_explicit()

template<typename T >

auto recti::rpolygon_cut_explicit	(	std::span< const Point< T > >	pointset,
		bool	is_anticlockwise
	)		-> std::vector< std::vector< Point< T > > >

Cut a polygon into explicit pieces.

Parameters

[in]	pointset	The polygon vertices
[in]	is_anticlockwise	Orientation flag

Returns: A vector of polygon pieces

◆ rpolygon_cut_explicit_recur()

template<typename T , typename Cmp >

auto recti::rpolygon_cut_explicit_recur	(	Dllink< size_t > *	v1,
		std::vector< Point< T > > &	lst,
		const Cmp &	cmp,
		RDllist &	rdll
	)		-> std::vector< std::vector< size_t > >

Recursive function for explicit decomposition.

◆ rpolygon_cut_implicit()

template<typename T >

auto recti::rpolygon_cut_implicit	(	std::span< const Point< T > >	pointset,
		bool	is_anticlockwise
	)		-> std::vector< std::vector< Point< T > > >

Cut a convex polygon into pieces according to the implicit vertices.

◆ rpolygon_cut_implicit_recur()

template<typename T , typename Cmp >

auto recti::rpolygon_cut_implicit_recur	(	Dllink< size_t > *	v1,
		std::vector< Point< T > > &	lst,
		const Cmp &	cmp,
		RDllist &	rdll
	)		-> std::vector< std::vector< size_t > >

Recursive function for implicit decomposition.

◆ rpolygon_cut_rectangle()

template<typename T >

auto recti::rpolygon_cut_rectangle	(	std::span< const Point< T > >	pointset,
		bool	is_anticlockwise
	)		-> std::vector< std::vector< Point< T > > >

Cut a convex polygon into rectangle pieces.

◆ rpolygon_is_anticlockwise()

template<typename T >

auto recti::rpolygon_is_anticlockwise ( std::span< const Point< T > > pointset ) -> bool

Determine if a rectilinear polygon is oriented clockwise.

This function takes a span of points defining a rectilinear polygon and determines if the polygon is oriented in a clockwise direction.

Template Parameters

T	The numeric type of the point coordinates.

Parameters

pointset The set of points defining the rectilinear polygon.

Returns: true if the polygon is oriented anti-clockwise, false otherwise.

◆ rpolygon_is_convex()

template<typename T >

auto recti::rpolygon_is_convex ( std::span< const Point< T > > pointset ) -> bool

Check if a polygon is convex.

A rectilinear polygon is convex precisely when it is both x-monotone and y-monotone.

Template Parameters

T	The type of the coordinates

Parameters

pointset The polygon vertices as points

Returns: true if the polygon is y-monotone, false otherwise

◆ rpolygon_is_xmonotone()

template<typename T >

auto recti::rpolygon_is_xmonotone ( std::span< const Point< T > > pointset ) -> bool

Check if a polygon is x-monotone.

A polygon is x-monotone if it can be divided into two chains that are both monotone with respect to the x-axis.

Template Parameters

T	The type of the coordinates

Parameters

pointset The polygon vertices as points

Returns: true if the polygon is x-monotone, false otherwise

◆ rpolygon_is_ymonotone()

template<typename T >

auto recti::rpolygon_is_ymonotone ( std::span< const Point< T > > pointset ) -> bool

Check if a polygon is y-monotone.

A polygon is y-monotone if it can be divided into two chains that are both monotone with respect to the y-axis.

Template Parameters

T	The type of the coordinates

Parameters

pointset The polygon vertices as points

Returns: true if the polygon is y-monotone, false otherwise

◆ rpolygon_make_convex_hull()

template<typename T >

auto recti::rpolygon_make_convex_hull	(	std::span< const Point< T > >	pointset,
		bool	is_anticlockwise
	)		-> std::vector<Point<T>>

inline

Create a convex hull from a rectilinear polygon.

Template Parameters

T	The type of the coordinates

Parameters

pointset	The polygon vertices as points
is_anticlockwise	Whether the polygon is oriented anti-clockwise

Returns: A vector of points representing the convex hull

◆ rpolygon_make_monotone_hull()

template<typename T >

auto recti::rpolygon_make_monotone_hull	(	std::span< const Point< T > >	pointset,
		bool	is_anticlockwise,
		const std::function< std::pair< T, T >(const Point< T > &)> &	dir
	)		-> std::vector< Point< T > >

Create a monotone hull from a rectilinear polygon with custom direction.

Template Parameters

T	The type of the coordinates

Parameters

pointset	The polygon vertices as points
is_anticlockwise	Whether the polygon is oriented anti-clockwise
dir	Function to extract comparison coordinates

Returns: A vector of points representing the monotone hull

◆ rpolygon_make_xmonotone_hull()

template<typename T >

auto recti::rpolygon_make_xmonotone_hull	(	std::span< const Point< T > >	pointset,
		bool	is_anticlockwise
	)		-> std::vector<Point<T>>

inline

Create an x-monotone hull from a rectilinear polygon.

Template Parameters

T	The type of the coordinates

Parameters

pointset	The polygon vertices as points
is_anticlockwise	Whether the polygon is oriented anti-clockwise

Returns: A vector of points representing the x-monotone hull

◆ rpolygon_make_ymonotone_hull()

template<typename T >

auto recti::rpolygon_make_ymonotone_hull	(	std::span< const Point< T > >	pointset,
		bool	is_anticlockwise
	)		-> std::vector<Point<T>>

inline

Create a y-monotone hull from a rectilinear polygon.

Template Parameters

T	The type of the coordinates

Parameters

pointset	The polygon vertices as points
is_anticlockwise	Whether the polygon is oriented anti-clockwise

Returns: A vector of points representing the y-monotone hull

◆ save_routing_tree3d_svg()

template<typename IntPoint >

void recti::save_routing_tree3d_svg	(	const GlobalRoutingTree< IntPoint > &	tree,
		std::optional< std::vector< typename GlobalRoutingTree< IntPoint >::Keepout > >	keepouts = `std::nullopt`,
		const int	scale_z = `100`,
		const std::string &	filename = `"routing_tree3d.svg"`,
		const int	width = `800`,
		const int	height = `600`
	)

extern

◆ save_routing_tree_svg()

template<typename IntPoint >

void recti::save_routing_tree_svg	(	const GlobalRoutingTree< IntPoint > &	tree,
		std::optional< std::vector< typename GlobalRoutingTree< IntPoint >::Keepout > >	keepouts = `std::nullopt`,
		const std::string &	filename = `"routing_tree.svg"`,
		const int	width = `800`,
		const int	height = `600`
	)

extern

◆ to_polygon()

template<typename T >

constexpr auto recti::to_polygon ( const RPolygon< T > & rpoly ) -> Polygon<T>

constexpr

Converts a rectilinear polygon to a general polygon.

This function adds intermediate points to ensure the polygon remains rectilinear when converted to a general polygon representation.

Template Parameters

T	The type of the coordinates

Parameters

rpoly The rectilinear polygon to convert

Returns: A Polygon object representing the converted polygon

◆ to_string()

std::string recti::to_string ( const NodeType routing_node_type )

Converts a NodeType enum value to its string representation.

Parameters

routing_node_type The NodeType to convert.

Returns: A string representation of the NodeType.

◆ upper()

template<typename U >

constexpr auto recti::upper ( const U & obj )

constexpr

Calculates the upper corner of an object.

This function returns the upper corner of obj. If obj has a upper_corner member function, it is used. Otherwise, it assumes obj is a scalar and returns it directly.

Template Parameters

U	Type of the object.

Parameters

[in] obj The object to find the upper corner of.

Returns: The upper corner of the object.

◆ visualize_example_tree()

void recti::visualize_example_tree ( )

◆ visualize_routing_tree3d_svg()

template<typename IntPoint >

std::string recti::visualize_routing_tree3d_svg	(	const GlobalRoutingTree< IntPoint > &	tree,
		std::optional< std::vector< typename GlobalRoutingTree< IntPoint >::Keepout > >	keepouts = `std::nullopt`,
		const int	scale_z = `100`,
		const int	width = `800`,
		const int	height = `600`,
		const int	margin = `50`
	)

extern

◆ visualize_routing_tree_svg()

template<typename IntPoint >

std::string recti::visualize_routing_tree_svg	(	const GlobalRoutingTree< IntPoint > &	tree,
		std::optional< std::vector< typename GlobalRoutingTree< IntPoint >::Keepout > >	keepouts = `std::nullopt`,
		const int	width = `800`,
		const int	height = `600`,
		const int	margin = `50`
	)

extern

Namespaces

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ NodeIdx

Enumeration Type Documentation

◆ NodeType

Function Documentation

◆ center()

◆ contain()

◆ create_comparison_visualization()

◆ create_delay_model_comparison()

◆ create_interactive_svg()

◆ create_mono_rpolygon()

◆ create_test_rpolygon()

◆ create_test_rpolygon_old()

◆ create_xmono_polygon()

◆ create_xmono_rpolygon()

◆ create_ymono_polygon()

◆ create_ymono_rpolygon()

◆ detect_overlap()

◆ enlarge()

◆ example_dme_usage()

◆ get_tree_statistics()

◆ hull()

◆ intersection()

◆ log_with_spdlog()

◆ lower()

◆ measure_of()

◆ min_dist()

◆ min_dist_change()

◆ my_abs()

◆ nearest()

◆ overlap()

◆ point_in_polygon()

◆ point_in_rpolygon()

◆ polygon_is_anticlockwise()

◆ polygon_is_monotone()

◆ polygon_is_xmonotone()

◆ polygon_is_ymonotone()

◆ rpolygon_cut_convex()

◆ rpolygon_cut_convex_recur()

◆ rpolygon_cut_explicit()

◆ rpolygon_cut_explicit_recur()

◆ rpolygon_cut_implicit()

◆ rpolygon_cut_implicit_recur()

◆ rpolygon_cut_rectangle()

◆ rpolygon_is_anticlockwise()

◆ rpolygon_is_convex()

◆ rpolygon_is_xmonotone()

◆ rpolygon_is_ymonotone()

◆ rpolygon_make_convex_hull()

◆ rpolygon_make_monotone_hull()

◆ rpolygon_make_xmonotone_hull()

◆ rpolygon_make_ymonotone_hull()

◆ save_routing_tree3d_svg()

◆ save_routing_tree_svg()

◆ to_polygon()

◆ to_string()

◆ upper()

◆ visualize_example_tree()

◆ visualize_routing_tree3d_svg()

◆ visualize_routing_tree_svg()