data structure for packing rectangles within an area of a desired aspect ratio without overlappings; optimization goal: to minimize the used aspect ratio area More...

#include <ogdf/energybased/fmmm/MAARPacking.h>

Public Member Functions
	MAARPacking ()
	constructor More...

	~MAARPacking ()
	destructor More...

void	pack_rectangles_using_Best_Fit_strategy (List< Rectangle > &R, double aspect_ratio, FMMMOptions::PreSort presort, FMMMOptions::TipOver allow_tipping_over, double &aspect_ratio_area, double &bounding_rectangles_area)
	The rectangles in R are packed using the First Fit tiling stratey (precisely the new down left corner coordinate of each rectangle is calculated and stored in R). The aspect ratio area and the area of the bounding rectangles are calculated, too. More...

Private Types
using	PQueue = PrioritizedQueue< ListIterator< PackingRowInfo >, double >

Private Member Functions
void	B_F_insert_rectangle (Rectangle r, List< PackingRowInfo > &P, List< ListIterator< PackingRowInfo >> &row_of_rectangle, ListIterator< PackingRowInfo > B_F_item, PQueue &total_width_of_row)
	Inserts r into the row with corresponding ListIterator B_F_item and updates total_width_of_row. More...

void	B_F_insert_rectangle_in_new_row (Rectangle r, List< PackingRowInfo > &P, List< ListIterator< PackingRowInfo >> &row_of_rectangle, PQueue &total_width_of_row)
	Creates a new empty row in P and inserts r into this row (by updating P, row_of_rectangle and total_width_of_row). More...

bool	better_tipp_rectangle_in_new_row (Rectangle r, double aspect_ratio, FMMMOptions::TipOver allow_tipping_over, double &best_area)
	Returns true if the aspect_ratio_area of the acual packing becomes better, when tipping r over bevore inserting it into the new row. best_area holds the aspect ratio area of the best of the two insertion alternatives. More...

bool	better_tipp_rectangle_in_this_row (Rectangle r, double aspect_ratio, FMMMOptions::TipOver allow_tipping_over, PackingRowInfo B_F_row, double &best_area)
	Returns true if the aspect_ratio_area of the acual packing becomes better, when tipping r over bevore inserting it into the existing row B_F_row. best_area holds the aspect ratio area of the best of the two insertion alternatives. More...

double	calculate_aspect_ratio_area (double w, double h, double r)
	Calculate the aspect ratio area of a rectangle with width w and height h and the given aspect ratio r. More...

double	calculate_bounding_rectangles_area (List< Rectangle > &R)
	Returns the area of the bounding rectangles in R. More...

void	export_new_rectangle_positions (List< PackingRowInfo > &P, List< ListIterator< PackingRowInfo >> &row_of_rectangle, List< ListIterator< Rectangle >> &rectangle_order)
	The information in P and row_of_rectangle are used to generate the new down left coordinates of the rectangles in R (rectangle_order holds the order in which the rectangles of R have to be processed. More...

ListIterator< PackingRowInfo >	find_Best_Fit_insert_position (ListIterator< Rectangle > rect_item, FMMMOptions::TipOver allow_tipping_over, double aspect_ratio, double &aspect_ratio_area, PQueue &total_width_of_row)
	Finds the Best Fit insert positions of *rect_item and returns the corresp. ListIterator in P or nullptr (indicating that a new row has to be created in P); aspect_ratio_area stores the used aspect ratio area of the drawing. More...

void	presort_rectangles_by_height (List< Rectangle > &R)
	Sorts elemets of R with momotonously dedreasing height. More...

void	presort_rectangles_by_width (List< Rectangle > &R)
	Sorts elemets of R with momotonously decreasing width. More...

Rectangle	tipp_over (ListIterator< Rectangle > rect_item)
	Tipps *rect_item over, by newly calculatting its width, height, and old_dlc values (Coordinates of the underlying connected subgraph are not recaculated here!!!). The new values are saved in R[rect_item] and are returned. More...

Private Attributes
double	area_height
	total height of the packing area More...

double	area_width
	total width of the packing area More...

Detailed Description

data structure for packing rectangles within an area of a desired aspect ratio without overlappings; optimization goal: to minimize the used aspect ratio area

Definition at line 46 of file MAARPacking.h.

Member Typedef Documentation

◆ PQueue

using ogdf::energybased::fmmm::MAARPacking::PQueue = PrioritizedQueue<ListIterator<PackingRowInfo>, double>

private

Definition at line 47 of file MAARPacking.h.

Constructor & Destructor Documentation

◆ MAARPacking()

ogdf::energybased::fmmm::MAARPacking::MAARPacking ( )

constructor

◆ ~MAARPacking()

ogdf::energybased::fmmm::MAARPacking::~MAARPacking ( )

destructor

Member Function Documentation

◆ B_F_insert_rectangle()

void ogdf::energybased::fmmm::MAARPacking::B_F_insert_rectangle	(	Rectangle	r,
		List< PackingRowInfo > &	P,
		List< ListIterator< PackingRowInfo >> &	row_of_rectangle,
		ListIterator< PackingRowInfo >	B_F_item,
		PQueue &	total_width_of_row
	)

private

Inserts r into the row with corresponding ListIterator B_F_item and updates total_width_of_row.

◆ B_F_insert_rectangle_in_new_row()

void ogdf::energybased::fmmm::MAARPacking::B_F_insert_rectangle_in_new_row	(	Rectangle	r,
		List< PackingRowInfo > &	P,
		List< ListIterator< PackingRowInfo >> &	row_of_rectangle,
		PQueue &	total_width_of_row
	)

private

Creates a new empty row in P and inserts r into this row (by updating P, row_of_rectangle and total_width_of_row).

◆ better_tipp_rectangle_in_new_row()

bool ogdf::energybased::fmmm::MAARPacking::better_tipp_rectangle_in_new_row	(	Rectangle	r,
		double	aspect_ratio,
		FMMMOptions::TipOver	allow_tipping_over,
		double &	best_area
	)

private

Returns true if the aspect_ratio_area of the acual packing becomes better, when tipping r over bevore inserting it into the new row. best_area holds the aspect ratio area of the best of the two insertion alternatives.

◆ better_tipp_rectangle_in_this_row()

bool ogdf::energybased::fmmm::MAARPacking::better_tipp_rectangle_in_this_row	(	Rectangle	r,
		double	aspect_ratio,
		FMMMOptions::TipOver	allow_tipping_over,
		PackingRowInfo	B_F_row,
		double &	best_area
	)

private

Returns true if the aspect_ratio_area of the acual packing becomes better, when tipping r over bevore inserting it into the existing row B_F_row. best_area holds the aspect ratio area of the best of the two insertion alternatives.

◆ calculate_aspect_ratio_area()

double ogdf::energybased::fmmm::MAARPacking::calculate_aspect_ratio_area	(	double	w,
		double	h,
		double	r
	)

private

Calculate the aspect ratio area of a rectangle with width w and height h and the given aspect ratio r.

◆ calculate_bounding_rectangles_area()

double ogdf::energybased::fmmm::MAARPacking::calculate_bounding_rectangles_area ( List< Rectangle > & R )

private

Returns the area of the bounding rectangles in R.

◆ export_new_rectangle_positions()

void ogdf::energybased::fmmm::MAARPacking::export_new_rectangle_positions	(	List< PackingRowInfo > &	P,
		List< ListIterator< PackingRowInfo >> &	row_of_rectangle,
		List< ListIterator< Rectangle >> &	rectangle_order
	)

private

The information in P and row_of_rectangle are used to generate the new down left coordinates of the rectangles in R (rectangle_order holds the order in which the rectangles of R have to be processed.

◆ find_Best_Fit_insert_position()

ListIterator<PackingRowInfo> ogdf::energybased::fmmm::MAARPacking::find_Best_Fit_insert_position	(	ListIterator< Rectangle >	rect_item,
		FMMMOptions::TipOver	allow_tipping_over,
		double	aspect_ratio,
		double &	aspect_ratio_area,
		PQueue &	total_width_of_row
	)

private

Finds the Best Fit insert positions of *rect_item and returns the corresp. ListIterator in P or nullptr (indicating that a new row has to be created in P); aspect_ratio_area stores the used aspect ratio area of the drawing.

◆ pack_rectangles_using_Best_Fit_strategy()

void ogdf::energybased::fmmm::MAARPacking::pack_rectangles_using_Best_Fit_strategy	(	List< Rectangle > &	R,
		double	aspect_ratio,
		FMMMOptions::PreSort	presort,
		FMMMOptions::TipOver	allow_tipping_over,
		double &	aspect_ratio_area,
		double &	bounding_rectangles_area
	)

The rectangles in R are packed using the First Fit tiling stratey (precisely the new down left corner coordinate of each rectangle is calculated and stored in R). The aspect ratio area and the area of the bounding rectangles are calculated, too.

◆ presort_rectangles_by_height()

void ogdf::energybased::fmmm::MAARPacking::presort_rectangles_by_height ( List< Rectangle > & R )

private

Sorts elemets of R with momotonously dedreasing height.

◆ presort_rectangles_by_width()

void ogdf::energybased::fmmm::MAARPacking::presort_rectangles_by_width ( List< Rectangle > & R )

private

Sorts elemets of R with momotonously decreasing width.

◆ tipp_over()

Rectangle ogdf::energybased::fmmm::MAARPacking::tipp_over ( ListIterator< Rectangle > rect_item )

private

Tipps *rect_item over, by newly calculatting its width, height, and old_dlc values (Coordinates of the underlying connected subgraph are not recaculated here!!!). The new values are saved in R[rect_item] and are returned.

Member Data Documentation

◆ area_height

double ogdf::energybased::fmmm::MAARPacking::area_height

private

total height of the packing area

Definition at line 62 of file MAARPacking.h.

◆ area_width

double ogdf::energybased::fmmm::MAARPacking::area_width

private

total width of the packing area

Definition at line 63 of file MAARPacking.h.

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

include/ogdf/energybased/fmmm/MAARPacking.h

OpenGraph DrawingFramework

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ PQueue

Constructor & Destructor Documentation

◆ MAARPacking()

◆ ~MAARPacking()

Member Function Documentation

◆ B_F_insert_rectangle()

◆ B_F_insert_rectangle_in_new_row()

◆ better_tipp_rectangle_in_new_row()

◆ better_tipp_rectangle_in_this_row()

◆ calculate_aspect_ratio_area()

◆ calculate_bounding_rectangles_area()

◆ export_new_rectangle_positions()

◆ find_Best_Fit_insert_position()

◆ pack_rectangles_using_Best_Fit_strategy()

◆ presort_rectangles_by_height()

◆ presort_rectangles_by_width()

◆ tipp_over()

Member Data Documentation

◆ area_height

◆ area_width

Open
Graph Drawing
Framework