/*
* $Revision: 2552 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
***************************************************************/
/** \file
* \brief Declaration of class MAARPacking (used by FMMMLayout).
*
* \author Stefan Hachul
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#include "MAARPacking.h"
#include "numexcept.h"
#include "FMMMLayout.h"
namespace ogdf {
MAARPacking::MAARPacking()
{
area_width = 0;
area_height = 0;
}
MAARPacking::~MAARPacking() { }
void MAARPacking::pack_rectangles_using_Best_Fit_strategy(
List& R,
double aspect_ratio,
int presort,
double& aspect_ratio_area,
double& bounding_rectangles_area)
{
ListIterator rect_item;
List P; //represents the packing of the rectangles
List > row_of_rectangle; //stores for each rectangle
//r at pos. i in R the ListIterator of the row in P
//where r is placed (at pos i in row_of_rectangle)
List > rectangle_order;//holds the order in which the
//rectangles are touched
//in R and its total width
if(presort == FMMMLayout::psDecreasingHeight)
presort_rectangles_by_height(R);
else if (presort == FMMMLayout::psDecreasingWidth)
presort_rectangles_by_width(R);
else if (presort == FMMMLayout::psDecreasingArea)
presort_rectangles_by_area(R);
double fullWidth = 0;
double widestRect = 0.0;
for(rect_item = R.begin(); rect_item.valid(); ++rect_item) {
double rectWidth = (*rect_item).get_width();
fullWidth += rectWidth;
widestRect = std::max(widestRect, rectWidth);
}
double secondWidestRect = 0.0;
for(rect_item = R.begin(); rect_item.valid(); ++rect_item) {
double rectWidth = (*rect_item).get_width();
if (rectWidth < widestRect)
secondWidestRect = std::max(secondWidestRect, rectWidth);
}
double wrapWidth;
// If there's only one rectangle, then our job is easy: the wrap width is its width.
if (secondWidestRect == 0.0)
wrapWidth = widestRect;
// If the widest rectangle is much wider than the second widest, we again use the widest as the wrap width. This
// is largely for bacterial genome cases, where there will be one very large component and many small ones. In
// such a case, it looks weird for the rows of small ones to extend past the big one, regardless of the aspect
// ratio.
else if (widestRect / secondWidestRect > 5.0)
wrapWidth = widestRect;
// If neither of the above two cases apply, then we binary search our way to a wrap width which brings us closest
// to the desired aspect ratio.
else {
wrapWidth = fullWidth;
double fullWidthAspectRatio = getAspectRatio(R, fullWidth);
double bestAgreement = getAspectRatioAgreement(aspect_ratio, fullWidthAspectRatio);
if (fullWidthAspectRatio > aspect_ratio) {
double left = 0.0;
double right = fullWidth;
while (true) {
double mid = (left + right) / 2.0;
double midAspectRatio = getAspectRatio(R, mid);
if (midAspectRatio == aspect_ratio) { // Exact match! (unlikely)
wrapWidth = mid;
break;
}
else if (midAspectRatio > aspect_ratio)
right = mid;
else // midAspectRatio < aspect_ratio
left = mid;
// We can't let the wrap width become less than the widest rectangle.
if (wrapWidth < widestRect) {
wrapWidth = widestRect;
break;
}
double agreement = getAspectRatioAgreement(aspect_ratio, getAspectRatio(R, mid));
// If the value hasn't changed, then it's not going to get any better.
if (agreement == bestAgreement)
break;
if (agreement > bestAgreement) {
bestAgreement = agreement;
wrapWidth = mid;
}
// No point in continuing too long.
if (right - left < 1.0)
break;
}
}
}
//init rectangle_order
for(rect_item = R.begin(); rect_item.valid(); ++rect_item)
rectangle_order.pushBack(rect_item);
// Now we know the wrapping width so we can position the rectangles in rows.
double widthOfCurrentRow = 0.0;
for(rect_item = R.begin(); rect_item.valid(); ++rect_item)
{
Rectangle r = *rect_item;
double rectWidth = r.get_width();
if (P.empty() || widthOfCurrentRow + rectWidth > wrapWidth || rectWidth > wrapWidth)
{
B_F_insert_rectangle_in_new_row(r,P,row_of_rectangle);
aspect_ratio_area = calculate_aspect_ratio_area(r.get_width(),r.get_height(),
aspect_ratio);
widthOfCurrentRow = rectWidth;
}
else // Insert in current row.
{
ListIterator B_F_item = row_of_rectangle.back();
B_F_insert_rectangle(r,P,row_of_rectangle,B_F_item);
widthOfCurrentRow += rectWidth;
}
}
export_new_rectangle_positions(P,row_of_rectangle,rectangle_order);
bounding_rectangles_area = calculate_bounding_rectangles_area(R);
}
double MAARPacking::getAspectRatio(List& R, double wrappingWidth) {
double width = 0.0, height = 0.0;
double rowWidth = 0.0, rowHeight = 0.0;
for(ListIterator rect_item = R.begin(); rect_item.valid(); ++rect_item) {
double rectWidth = (*rect_item).get_width();
double rectHeight = (*rect_item).get_height();
// If the rectangle fits in this row, it goes in this row.
if (rowWidth + rectWidth <= wrappingWidth) {
rowWidth += rectWidth;
rowHeight = std::max(rowHeight, rectHeight);
}
// Otherwise, it goes in a new row.
else {
width = std::max(width, rowWidth);
height += rowHeight;
rowWidth = rectWidth;
rowHeight = rectHeight;
}
}
width = std::max(width, rowWidth);
height += rowHeight;
if (height > 0.0)
return width / height;
else
return 1.0;
}
double MAARPacking::getAspectRatioAgreement(double ar1, double ar2) {
if (ar1 == 0.0 && ar2 == 0.0)
return 1.0;
return std::min(ar1, ar2) / std::max(ar1, ar2);
}
inline void MAARPacking::presort_rectangles_by_height(List& R)
{
RectangleComparerHeight comp_height;
R.quicksort(comp_height);
}
inline void MAARPacking::presort_rectangles_by_width(List& R)
{
RectangleComparerWidth comp_width;
R.quicksort(comp_width);
}
inline void MAARPacking::presort_rectangles_by_area(List& R)
{
RectangleComparerArea comp_area;
R.quicksort(comp_area);
}
void MAARPacking::B_F_insert_rectangle_in_new_row(
Rectangle r,
List& P,
List >&row_of_rectangle)
{
PackingRowInfo p;
//create new empty row and insert r into this row of P
p.set_max_height(r.get_height());
p.set_total_width(r.get_width());
p.set_row_index(P.size());
P.pushBack(p);
//remember in which row of P r is placed by updating row_of_rectangle
row_of_rectangle.pushBack(P.rbegin());
//update area_height,area_width
area_width = max(r.get_width(),area_width);
area_height += r.get_height();
}
ListIterator MAARPacking::find_Best_Fit_insert_position(
ListIterator rect_item,
double aspect_ratio,
double& aspect_ratio_area,
PQueue& total_width_of_row)
{
numexcept N;
double area_2;
Rectangle r = *rect_item;
better_tipp_rectangle_in_new_row(r,aspect_ratio,aspect_ratio_area);
ListIterator B_F_item = total_width_of_row.find_min();
PackingRowInfo B_F_row = *B_F_item;
better_tipp_rectangle_in_this_row(r,aspect_ratio,B_F_row,area_2);
if((area_2 <= aspect_ratio_area) || N.nearly_equal(aspect_ratio_area,area_2))
{
aspect_ratio_area = area_2;
return B_F_item;
}
else
return NULL;
}
void MAARPacking::B_F_insert_rectangle(
Rectangle r,
List& P,
List >&row_of_rectangle,
ListIterator B_F_item)
{
ListIterator null = NULL;
if (B_F_item == null) //insert into a new row
B_F_insert_rectangle_in_new_row(r,P,row_of_rectangle);
else //insert into an existing row
{
double old_max_height;
//update P[B_F_item]
PackingRowInfo p = *B_F_item;
old_max_height = p.get_max_height();
p.set_max_height(max(old_max_height,r.get_height()));
p.set_total_width(p.get_total_width()+r.get_width());
*B_F_item = p;
//updating row_of_rectangle
row_of_rectangle.pushBack(B_F_item);
//update area_height,area_width
area_width = max(area_width,p.get_total_width());
area_height = max(area_height,area_height-old_max_height+r.get_height());
}
}
void MAARPacking::export_new_rectangle_positions(
List& P,
List >& row_of_rectangle,
List >& rectangle_order)
{
int i;
Rectangle r;
PackingRowInfo p,p_pred;
DPoint new_dlc_pos;
double new_x,new_y;
Array row_y_min (P.size()); //stores the min. y-coordinates for each row in P
Array act_row_x_max (P.size()); //stores the actual rightmost x-coordinate
//for each row in P
//ListIterator< ListIterator > row_item;
ListIterator row_item;
ListIterator R_item;
ListIterator > RR_item;
ListIterator > Rrow_item;
//init act_row_x_max;
for(i = 0; i& R)
{
double area = 0;
Rectangle r;
forall_listiterators(Rectangle,r_it,R)
area += (*r_it).get_width() * (*r_it).get_height();
return area;
}
inline double MAARPacking::calculate_aspect_ratio_area(
double width,
double height,
double aspect_ratio)
{
double ratio = width/height;
if(ratio < aspect_ratio) //scale width
return ( width * height * (aspect_ratio/ratio));
else //scale height
return ( width * height * (ratio/aspect_ratio));
}
bool MAARPacking::better_tipp_rectangle_in_new_row(
Rectangle r,
double aspect_ratio,
double& best_area)
{
double height,width;
bool rotate = false;
//first try: new row insert position
width = max(area_width,r.get_width());
height = area_height + r.get_height();
best_area = calculate_aspect_ratio_area(width,height,aspect_ratio);
return rotate;
}
bool MAARPacking::better_tipp_rectangle_in_this_row(
Rectangle r,
double aspect_ratio,
PackingRowInfo B_F_row,
double& best_area)
{
double height,width;
bool rotate = false;
//first try: BEST_FIT insert position
width = max(area_width,B_F_row.get_total_width()+r.get_width());
height = max(area_height, area_height-B_F_row.get_max_height()+r.get_height());
best_area = calculate_aspect_ratio_area(width,height,aspect_ratio);
return rotate;
}
inline Rectangle MAARPacking::tipp_over(ListIterator rect_item)
{
Rectangle r = *rect_item;
Rectangle r_tipped_over = r;
DPoint tipped_dlc;
if(r.is_tipped_over() == false)
{//tipp old_dlc over
tipped_dlc.m_x = r.get_old_dlc_position().m_y*(-1)-r.get_height();
tipped_dlc.m_y = r.get_old_dlc_position().m_x;
}
else
{//tipp old_dlc back;
tipped_dlc.m_x = r.get_old_dlc_position().m_y;
tipped_dlc.m_y = r.get_old_dlc_position().m_x*(-1)-r.get_width();
}
r_tipped_over.set_old_dlc_position(tipped_dlc);
r_tipped_over.set_width(r.get_height());
r_tipped_over.set_height(r.get_width());
r_tipped_over.tipp_over();
*rect_item = r_tipped_over;
return r_tipped_over;
}
}//namespace ogdf