Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::energybased::fmmm::MAARPacking Class Reference

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
 
 ~MAARPacking ()
 destructor
 
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.
 

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.
 
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).
 
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.
 
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.
 
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.
 
double calculate_bounding_rectangles_area (List< Rectangle > &R)
 Returns the area of the bounding rectangles in R.
 
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.
 
ListIterator< PackingRowInfofind_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.
 
void presort_rectangles_by_height (List< Rectangle > &R)
 Sorts elemets of R with momotonously dedreasing height.
 
void presort_rectangles_by_width (List< Rectangle > &R)
 Sorts elemets of R with momotonously decreasing width.
 
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.
 

Private Attributes

double area_height
 total height of the packing area
 
double area_width
 total width of the packing area
 

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 47 of file MAARPacking.h.

Member Typedef Documentation

◆ PQueue

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 63 of file MAARPacking.h.

◆ area_width

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

total width of the packing area

Definition at line 64 of file MAARPacking.h.


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