6 * $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
7 ***************************************************************/
10 * \brief Implementation of class MAARPacking (used by FMMMLayout).
12 * \author Stefan Hachul
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
47 #ifndef OGDF_MAAR_PACKING_H
48 #define OGDF_MAAR_PACKING_H
50 #include "PackingRowInfo.h"
51 #include "Rectangle.h"
53 #include <ogdf/basic/List.h>
60 //data structure for packing rectangles within an area of a desired aspect ratio
61 //without overlappings; optimization goal: to minimize the used aspect ratio area
65 MAARPacking(); //constructor
66 ~MAARPacking(); //destructor
68 //The rectangles in R are packed using the First Fit tiling stratey (precisely the
69 //new down left corner coordinate of each rectangle is calculated and stored in R).
70 //The aspect ratio area and the area of the bounding rectangles are calculated,
72 void pack_rectangles_using_Best_Fit_strategy(List
<Rectangle
>& R
,double
73 aspect_ratio
, int presort
, int
74 allow_tipping_over
,double&
75 aspect_ratio_area
,double&
76 bounding_rectangles_area
);
81 double area_height
; //total height of the packing area
82 double area_width
; //total width of the packing area
85 //Sorts elemets of R with momotonously dedreasing height.
86 void presort_rectangles_by_height(List
<Rectangle
>& R
);
88 //Sorts elemets of R with momotonously decreasing width.
89 void presort_rectangles_by_width(List
<Rectangle
>& R
);
91 //Creates a new empty row in P and inserts r into this row (by updating P,
92 //row_of_rectangle and total_width_of_row).
93 void B_F_insert_rectangle_in_new_row(Rectangle r
,List
<PackingRowInfo
>& P
, List
94 <ListIterator
<PackingRowInfo
> >&
95 row_of_rectangle
, PQueue
&
99 //Finds the Best Fit insert positions of *rect_item and returns the
100 //corresp. ListIterator in P or NULL (indicating that a new row has
101 //to be created in P); aspect_ratio_area stores the used aspect ratio area of
103 ListIterator
<PackingRowInfo
> find_Best_Fit_insert_position(
104 ListIterator
<Rectangle
> rect_item
,
105 int allow_tipping_over
,
107 double& aspect_ratio_area
,
108 PQueue
& total_width_of_row
);
111 //Inserts r into the row with corresponding ListIterator B_F_item and updates
112 //total_width_of_row.
113 void B_F_insert_rectangle(Rectangle r
,List
<PackingRowInfo
>& P
,List
115 <PackingRowInfo
> >& row_of_rectangle
,ListIterator
116 <PackingRowInfo
> B_F_item
, PQueue
& total_width_of_row
);
119 //The information in P and row_of_rectangle are used to generate the new down left
120 //coordinates of the rectangles in R (rectangle_order holds the order in which
121 //the rectangles of R have to be processed.
122 void export_new_rectangle_positions(List
<PackingRowInfo
>& P
,List
<ListIterator
124 row_of_rectangle
,List
<ListIterator
125 <Rectangle
> >& rectangle_order
);
127 //Returns the area of the bounding rectangles in R.
128 double calculate_bounding_rectangles_area(List
<Rectangle
>&R
);
130 //Calculate the aspect ratio area of a rectangle with width w and height h and the
131 //given aspect ratio r.
132 double calculate_aspect_ratio_area(double w
,double h
,double r
);
134 //Returns true if the aspect_ratio_area of the acual packing becomes better, when
135 //tipping r over bevore inserting it into the new row. best_area holds the aspect
136 //ratio area of the best of the two insertion alternatives.
137 bool better_tipp_rectangle_in_new_row(Rectangle r
,double aspect_ratio
, int
138 allow_tipping_over
,double& best_area
);
140 //Returns true if the aspect_ratio_area of the acual packing becomes better, when
141 //tipping r over bevore inserting it into the existing row B_F_row. best_area holds
142 //the aspect ratio area of the best of the two insertion alternatives.
143 bool better_tipp_rectangle_in_this_row(Rectangle r
,double aspect_ratio
,int
144 allow_tipping_over
,PackingRowInfo B_F_row
,
147 //Tipps *rect_item over, by newly calculatting its width, height, and old_dlc
148 //values (Coordinates of the underlying connected subgraph are not recaculated
149 //here!!!). The new values are saved in R[rect_item] and are returned.
150 Rectangle
tipp_over(ListIterator
<Rectangle
> rect_item
);