6 * $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration 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 ***************************************************************/
44 #include "MAARPacking.h"
45 #include "numexcept.h"
46 #include <ogdf/energybased/FMMMLayout.h>
50 MAARPacking::MAARPacking()
57 MAARPacking::~MAARPacking() { }
60 void MAARPacking::pack_rectangles_using_Best_Fit_strategy(
64 int allow_tipping_over
,
65 double& aspect_ratio_area
,
66 double& bounding_rectangles_area
)
70 ListIterator
<PackingRowInfo
> B_F_item
;
71 ListIterator
<Rectangle
> rect_item
;
72 List
<PackingRowInfo
> P
; //represents the packing of the rectangles
73 List
<ListIterator
<PackingRowInfo
> > row_of_rectangle
; //stores for each rectangle
74 //r at pos. i in R the ListIterator of the row in P
75 //where r is placed (at pos i in row_of_rectangle)
76 List
<ListIterator
<Rectangle
> > rectangle_order
;//holds the order in which the
77 //rectangles are touched
78 PQueue total_width_of_row
; //stores for each row the ListIterator of the corresp. list
79 //in R and its total width
81 if(presort
== FMMMLayout::psDecreasingHeight
)
82 presort_rectangles_by_height(R
);
83 else if (presort
== FMMMLayout::psDecreasingWidth
)
84 presort_rectangles_by_width(R
);
86 //init rectangle_order
87 for(rect_item
= R
.begin(); rect_item
.valid(); ++rect_item
)
88 rectangle_order
.pushBack(rect_item
);
90 for(rect_item
= R
.begin(); rect_item
.valid(); ++rect_item
)
95 if(better_tipp_rectangle_in_new_row(r
,aspect_ratio
,allow_tipping_over
,area
))
96 r
= tipp_over(rect_item
);
97 B_F_insert_rectangle_in_new_row(r
,P
,row_of_rectangle
,total_width_of_row
);
98 aspect_ratio_area
= calculate_aspect_ratio_area(r
.get_width(),r
.get_height(),
103 B_F_item
= find_Best_Fit_insert_position(rect_item
,allow_tipping_over
,
104 aspect_ratio
,aspect_ratio_area
,
108 B_F_insert_rectangle(r
,P
,row_of_rectangle
,B_F_item
,total_width_of_row
);
111 export_new_rectangle_positions(P
,row_of_rectangle
,rectangle_order
);
112 bounding_rectangles_area
= calculate_bounding_rectangles_area(R
);
116 inline void MAARPacking::presort_rectangles_by_height(List
<Rectangle
>& R
)
118 RectangleComparerHeight comp_height
;
119 R
.quicksort(comp_height
);
123 inline void MAARPacking::presort_rectangles_by_width(List
<Rectangle
>& R
)
125 RectangleComparerWidth comp_width
;
126 R
.quicksort(comp_width
);
130 void MAARPacking::B_F_insert_rectangle_in_new_row(
132 List
<PackingRowInfo
>& P
,
133 List
<ListIterator
<PackingRowInfo
> >&row_of_rectangle
,
134 PQueue
& total_width_of_row
)
138 //create new empty row and insert r into this row of P
139 p
.set_max_height(r
.get_height());
140 p
.set_total_width(r
.get_width());
141 p
.set_row_index(P
.size());
144 //remember in which row of P r is placed by updating row_of_rectangle
145 row_of_rectangle
.pushBack(P
.rbegin());
147 //update area_height,area_width
148 area_width
= max(r
.get_width(),area_width
);
149 area_height
+= r
.get_height();
152 //update total_width_of_row
153 total_width_of_row
.insert(r
.get_width(),P
.rbegin());
157 ListIterator
<PackingRowInfo
> MAARPacking::find_Best_Fit_insert_position(
158 ListIterator
<Rectangle
> rect_item
,
159 int allow_tipping_over
,
161 double& aspect_ratio_area
,
162 PQueue
& total_width_of_row
)
166 int best_try_index
,index_2
;
167 Rectangle r
= *rect_item
;
169 if(better_tipp_rectangle_in_new_row(r
,aspect_ratio
,allow_tipping_over
,
175 ListIterator
<PackingRowInfo
> B_F_item
= total_width_of_row
.find_min();
176 PackingRowInfo B_F_row
= *B_F_item
;
177 if(better_tipp_rectangle_in_this_row(r
,aspect_ratio
,allow_tipping_over
,B_F_row
,area_2
))
182 if((area_2
<= aspect_ratio_area
) || N
.nearly_equal(aspect_ratio_area
,area_2
))
184 aspect_ratio_area
= area_2
;
185 best_try_index
= index_2
;
188 //return the row and eventually tipp the rectangle with ListIterator rect_item
189 if(best_try_index
== 1)
191 else if(best_try_index
== 2)
193 tipp_over(rect_item
);
196 else if(best_try_index
== 3)
198 else //best_try_index == 4
200 tipp_over(rect_item
);
206 void MAARPacking::B_F_insert_rectangle(
208 List
<PackingRowInfo
>& P
,
209 List
<ListIterator
<PackingRowInfo
> >&row_of_rectangle
,
210 ListIterator
<PackingRowInfo
> B_F_item
,
211 PQueue
& total_width_of_row
)
213 ListIterator
<PackingRowInfo
> null
= NULL
;
214 if (B_F_item
== null
) //insert into a new row
215 B_F_insert_rectangle_in_new_row(r
,P
,row_of_rectangle
,total_width_of_row
);
216 else //insert into an existing row
218 double old_max_height
;
221 PackingRowInfo p
= *B_F_item
;
222 old_max_height
= p
.get_max_height();
223 p
.set_max_height(max(old_max_height
,r
.get_height()));
224 p
.set_total_width(p
.get_total_width()+r
.get_width());
227 //updating row_of_rectangle
228 row_of_rectangle
.pushBack(B_F_item
);
230 //update area_height,area_width
231 area_width
= max(area_width
,p
.get_total_width());
232 area_height
= max(area_height
,area_height
-old_max_height
+r
.get_height());
234 //update total_width_of_row
236 total_width_of_row
.del_min();
237 total_width_of_row
.insert(p
.get_total_width(),B_F_item
);
244 void MAARPacking::export_new_rectangle_positions(
245 List
<PackingRowInfo
>& P
,
246 List
<ListIterator
<PackingRowInfo
> >& row_of_rectangle
,
247 List
<ListIterator
<Rectangle
> >& rectangle_order
)
251 PackingRowInfo p
,p_pred
;
254 Array
<double> row_y_min (P
.size()); //stores the min. y-coordinates for each row in P
255 Array
<double> act_row_x_max (P
.size()); //stores the actual rightmost x-coordinate
257 //ListIterator< ListIterator<PackingRowInfo> > row_item;
258 ListIterator
<PackingRowInfo
> row_item
;
259 ListIterator
<Rectangle
> R_item
;
260 ListIterator
<ListIterator
<Rectangle
> > RR_item
;
261 ListIterator
<ListIterator
<PackingRowInfo
> > Rrow_item
;
263 //init act_row_x_max;
264 for(i
= 0; i
<P
.size();i
++)
265 act_row_x_max
[i
] = 0;
267 //calculate minimum heights of each row
268 for(row_item
= P
.begin(); row_item
.valid(); ++row_item
)
270 if (row_item
== P
.begin())
275 p_pred
= *(P
.cyclicPred(row_item
));
276 row_y_min
[p
.get_row_index()] = row_y_min
[p
.get_row_index()-1]+
277 p_pred
.get_max_height();
281 //calculate for each rectangle its new down left corner coordinate
282 Rrow_item
= row_of_rectangle
.begin();
284 for(RR_item
= rectangle_order
.begin(); RR_item
.valid(); ++RR_item
)
288 row_item
= *Rrow_item
;
290 new_x
= act_row_x_max
[p
.get_row_index()];
291 act_row_x_max
[p
.get_row_index()] += r
.get_width();
292 new_y
= row_y_min
[p
.get_row_index()]+ (p
.get_max_height()-r
.get_height())/2;
294 new_dlc_pos
.m_x
= new_x
;
295 new_dlc_pos
.m_y
= new_y
;
296 r
.set_new_dlc_position(new_dlc_pos
);
299 if(Rrow_item
!= row_of_rectangle
.rbegin())
300 Rrow_item
= row_of_rectangle
.cyclicSucc(Rrow_item
);
305 inline double MAARPacking::calculate_bounding_rectangles_area(List
<Rectangle
>& R
)
310 forall_listiterators(Rectangle
,r_it
,R
)
311 area
+= (*r_it
).get_width() * (*r_it
).get_height();
317 inline double MAARPacking::calculate_aspect_ratio_area(
322 double ratio
= width
/height
;
324 if(ratio
< aspect_ratio
) //scale width
325 return ( width
* height
* (aspect_ratio
/ratio
));
327 return ( width
* height
* (ratio
/aspect_ratio
));
331 bool MAARPacking::better_tipp_rectangle_in_new_row(
334 int allow_tipping_over
,
337 double height
,width
,act_area
;
340 //first try: new row insert position
341 width
= max(area_width
,r
.get_width());
342 height
= area_height
+ r
.get_height();
343 best_area
= calculate_aspect_ratio_area(width
,height
,aspect_ratio
);
346 //second try: new row insert position with tipping r over
347 if(allow_tipping_over
== FMMMLayout::toNoGrowingRow
||
348 allow_tipping_over
== FMMMLayout::toAlways
)
350 width
= max(area_width
,r
.get_height());
351 height
= area_height
+ r
.get_width();
352 act_area
= calculate_aspect_ratio_area(width
,height
,aspect_ratio
);
353 if(act_area
< 0.99999 * best_area
)
355 best_area
= act_area
;
363 bool MAARPacking::better_tipp_rectangle_in_this_row(
366 int allow_tipping_over
,
367 PackingRowInfo B_F_row
,
370 double height
,width
,act_area
;
373 //first try: BEST_FIT insert position
374 width
= max(area_width
,B_F_row
.get_total_width()+r
.get_width());
375 height
= max(area_height
, area_height
-B_F_row
.get_max_height()+r
.get_height());
376 best_area
= calculate_aspect_ratio_area(width
,height
,aspect_ratio
);
378 //second try: BEST_FIT insert position with skipping r over
379 if((allow_tipping_over
== FMMMLayout::toNoGrowingRow
&& r
.get_width()
380 <= B_F_row
.get_max_height()) || allow_tipping_over
== FMMMLayout::toAlways
)
382 width
= max(area_width
,B_F_row
.get_total_width()+r
.get_height());
383 height
= max(area_height
, area_height
-B_F_row
.get_max_height()+r
.get_width());
384 act_area
= calculate_aspect_ratio_area(width
,height
,aspect_ratio
);
385 if(act_area
< 0.99999 * best_area
)
387 best_area
= act_area
;
395 inline Rectangle
MAARPacking::tipp_over(ListIterator
<Rectangle
> rect_item
)
397 Rectangle r
= *rect_item
;
398 Rectangle r_tipped_over
= r
;
401 if(r
.is_tipped_over() == false)
403 tipped_dlc
.m_x
= r
.get_old_dlc_position().m_y
*(-1)-r
.get_height();
404 tipped_dlc
.m_y
= r
.get_old_dlc_position().m_x
;
407 {//tipp old_dlc back;
408 tipped_dlc
.m_x
= r
.get_old_dlc_position().m_y
;
409 tipped_dlc
.m_y
= r
.get_old_dlc_position().m_x
*(-1)-r
.get_width();
411 r_tipped_over
.set_old_dlc_position(tipped_dlc
);
412 r_tipped_over
.set_width(r
.get_height());
413 r_tipped_over
.set_height(r
.get_width());
414 r_tipped_over
.tipp_over();
415 *rect_item
= r_tipped_over
;
417 return r_tipped_over
;