ext/OGDF/src/energybased/MAARPacking.cpp

   1 /*
   2  * $Revision: 2552 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class MAARPacking (used by FMMMLayout).
  11  *
  12  * \author Stefan Hachul
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  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
  26  * for details.
  27  *
  28  * \par
  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.
  33  *
  34  * \par
  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.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #include "MAARPacking.h"
  45 #include "numexcept.h"
  46 #include <ogdf/energybased/FMMMLayout.h>
  47
  48 namespace ogdf {
  49
  50 MAARPacking::MAARPacking()
  51 {
  52         area_width = 0;
  53         area_height = 0;
  54 }
  55
  56
  57 MAARPacking::~MAARPacking() { }
  58
  59
  60 void MAARPacking::pack_rectangles_using_Best_Fit_strategy(
  61         List<Rectangle>& R,
  62         double aspect_ratio,
  63         int presort,
  64         int allow_tipping_over,
  65         double& aspect_ratio_area,
  66         double& bounding_rectangles_area)
  67 {
  68         Rectangle r;
  69         double 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
  80
  81         if(presort == FMMMLayout::psDecreasingHeight)
  82                 presort_rectangles_by_height(R);
  83         else if (presort == FMMMLayout::psDecreasingWidth)
  84                 presort_rectangles_by_width(R);
  85
  86         //init rectangle_order
  87         for(rect_item = R.begin(); rect_item.valid(); ++rect_item)
  88                 rectangle_order.pushBack(rect_item);
  89
  90         for(rect_item = R.begin(); rect_item.valid(); ++rect_item)
  91         {
  92                 if (P.empty())
  93                 {
  94                         r = *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(),
  99                                 aspect_ratio);
 100                 }
 101                 else
 102                 {
 103                         B_F_item = find_Best_Fit_insert_position(rect_item,allow_tipping_over,
 104                                 aspect_ratio,aspect_ratio_area,
 105                                 total_width_of_row);
 106
 107                         r = *rect_item;
 108                         B_F_insert_rectangle(r,P,row_of_rectangle,B_F_item,total_width_of_row);
 109                 }
 110         }
 111         export_new_rectangle_positions(P,row_of_rectangle,rectangle_order);
 112         bounding_rectangles_area = calculate_bounding_rectangles_area(R);
 113 }
 114
 115
 116 inline void MAARPacking::presort_rectangles_by_height(List<Rectangle>& R)
 117 {
 118         RectangleComparerHeight comp_height;
 119         R.quicksort(comp_height);
 120 }
 121
 122
 123 inline void MAARPacking::presort_rectangles_by_width(List<Rectangle>& R)
 124 {
 125         RectangleComparerWidth comp_width;
 126         R.quicksort(comp_width);
 127 }
 128
 129
 130 void MAARPacking::B_F_insert_rectangle_in_new_row(
 131         Rectangle r,
 132         List<PackingRowInfo>& P,
 133         List <ListIterator<PackingRowInfo> >&row_of_rectangle,
 134         PQueue& total_width_of_row)
 135 {
 136         PackingRowInfo p;
 137
 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());
 142         P.pushBack(p);
 143
 144         //remember in which row of P r is placed by updating row_of_rectangle
 145         row_of_rectangle.pushBack(P.rbegin());
 146
 147         //update area_height,area_width
 148         area_width = max(r.get_width(),area_width);
 149         area_height += r.get_height();
 150
 151
 152         //update total_width_of_row
 153         total_width_of_row.insert(r.get_width(),P.rbegin());
 154 }
 155
 156
 157 ListIterator<PackingRowInfo> MAARPacking::find_Best_Fit_insert_position(
 158         ListIterator<Rectangle> rect_item,
 159         int allow_tipping_over,
 160         double aspect_ratio,
 161         double& aspect_ratio_area,
 162         PQueue& total_width_of_row)
 163 {
 164         numexcept N;
 165         double area_2;
 166         int best_try_index,index_2;
 167         Rectangle r = *rect_item;
 168
 169         if(better_tipp_rectangle_in_new_row(r,aspect_ratio,allow_tipping_over,
 170                 aspect_ratio_area))
 171                 best_try_index = 2;
 172         else
 173                 best_try_index = 1;
 174
 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))
 178                 index_2 = 4;
 179         else
 180                 index_2 = 3;
 181
 182         if((area_2 <= aspect_ratio_area) || N.nearly_equal(aspect_ratio_area,area_2))
 183         {
 184                 aspect_ratio_area = area_2;
 185                 best_try_index = index_2;
 186         }
 187
 188         //return the row and eventually tipp the rectangle with ListIterator rect_item
 189         if(best_try_index == 1)
 190                 return NULL;
 191         else if(best_try_index == 2)
 192         {
 193                 tipp_over(rect_item);
 194                 return NULL;
 195         }
 196         else if(best_try_index == 3)
 197                 return B_F_item;
 198         else //best_try_index == 4
 199         {
 200                 tipp_over(rect_item);
 201                 return B_F_item;
 202         }
 203 }
 204
 205
 206 void MAARPacking::B_F_insert_rectangle(
 207         Rectangle r,
 208         List<PackingRowInfo>& P,
 209         List<ListIterator<PackingRowInfo> >&row_of_rectangle,
 210         ListIterator<PackingRowInfo> B_F_item,
 211         PQueue& total_width_of_row)
 212 {
 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
 217         {
 218                 double old_max_height;
 219
 220                 //update P[B_F_item]
 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());
 225                 *B_F_item = p;
 226
 227                 //updating row_of_rectangle
 228                 row_of_rectangle.pushBack(B_F_item);
 229
 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());
 233
 234                 //update total_width_of_row
 235
 236                 total_width_of_row.del_min();
 237                 total_width_of_row.insert(p.get_total_width(),B_F_item);
 238
 239         }
 240 }
 241
 242
 243
 244 void MAARPacking::export_new_rectangle_positions(
 245         List<PackingRowInfo>& P,
 246         List<ListIterator<PackingRowInfo> >& row_of_rectangle,
 247         List<ListIterator<Rectangle> >& rectangle_order)
 248 {
 249         int i;
 250         Rectangle r;
 251         PackingRowInfo p,p_pred;
 252         DPoint new_dlc_pos;
 253         double new_x,new_y;
 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
 256         //for each row in P
 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;
 262
 263         //init act_row_x_max;
 264         for(i = 0; i<P.size();i++)
 265                 act_row_x_max[i] = 0;
 266
 267         //calculate minimum heights of each row
 268         for(row_item = P.begin(); row_item.valid(); ++row_item)
 269         {
 270                 if (row_item == P.begin())
 271                         row_y_min[0] = 0;
 272                 else
 273                 {
 274                         p = *row_item;
 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();
 278                 }
 279         }
 280
 281         //calculate for each rectangle its new down left corner coordinate
 282         Rrow_item = row_of_rectangle.begin();
 283
 284         for(RR_item = rectangle_order.begin(); RR_item.valid(); ++RR_item)
 285         {
 286                 R_item = *RR_item;
 287                 r = *R_item;
 288                 row_item = *Rrow_item;
 289                 p = *row_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;
 293
 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);
 297                 *R_item = r;
 298
 299                 if(Rrow_item != row_of_rectangle.rbegin())
 300                         Rrow_item = row_of_rectangle.cyclicSucc(Rrow_item);
 301         }
 302 }
 303
 304
 305 inline double MAARPacking::calculate_bounding_rectangles_area(List<Rectangle>& R)
 306 {
 307         double area = 0;
 308         Rectangle r;
 309
 310         forall_listiterators(Rectangle,r_it,R)
 311                 area += (*r_it).get_width() * (*r_it).get_height();
 312
 313         return area;
 314 }
 315
 316
 317 inline double MAARPacking::calculate_aspect_ratio_area(
 318         double width,
 319         double height,
 320         double aspect_ratio)
 321 {
 322         double ratio = width/height;
 323
 324         if(ratio < aspect_ratio) //scale width
 325                 return ( width * height * (aspect_ratio/ratio));
 326         else //scale height
 327                 return ( width * height * (ratio/aspect_ratio));
 328 }
 329
 330
 331 bool MAARPacking::better_tipp_rectangle_in_new_row(
 332         Rectangle r,
 333         double aspect_ratio,
 334         int allow_tipping_over,
 335         double& best_area)
 336 {
 337         double height,width,act_area;
 338         bool rotate = false;
 339
 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);
 344
 345
 346         //second try: new row insert position with tipping r over
 347         if(allow_tipping_over == FMMMLayout::toNoGrowingRow ||
 348                 allow_tipping_over == FMMMLayout::toAlways)
 349         {
 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)
 354                 {
 355                         best_area = act_area;
 356                         rotate = true;
 357                 }
 358         }
 359         return rotate;
 360 }
 361
 362
 363 bool MAARPacking::better_tipp_rectangle_in_this_row(
 364         Rectangle r,
 365         double aspect_ratio,
 366         int allow_tipping_over,
 367         PackingRowInfo B_F_row,
 368         double& best_area)
 369 {
 370         double height,width,act_area;
 371         bool rotate = false;
 372
 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);
 377
 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)
 381         {
 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)
 386                 {
 387                         best_area = act_area;
 388                         rotate = true;
 389                 }
 390         }
 391         return rotate;
 392 }
 393
 394
 395 inline Rectangle MAARPacking::tipp_over(ListIterator<Rectangle> rect_item)
 396 {
 397         Rectangle r = *rect_item;
 398         Rectangle r_tipped_over = r;
 399         DPoint tipped_dlc;
 400
 401         if(r.is_tipped_over() == false)
 402         {//tipp old_dlc over
 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;
 405         }
 406         else
 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();
 410         }
 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;
 416
 417         return r_tipped_over;
 418 }
 419
 420 }//namespace ogdf