src/libvpsc/remove_rectangle_overlap.cpp

   1 /**
   2  * \brief remove overlaps between a set of rectangles.
   3  *
   4  * Authors:
   5  *   Tim Dwyer <tgdwyer@gmail.com>
   6  *
   7  * Copyright (C) 2005 Authors
   8  *
   9  * Released under GNU LGPL.  Read the file 'COPYING' for more information.
  10  */
  11
  12 #include <iostream>
  13 #include <cassert>
  14 #include "generate-constraints.h"
  15 #include "solve_VPSC.h"
  16 #include "variable.h"
  17 #include "constraint.h"
  18 #ifdef RECTANGLE_OVERLAP_LOGGING
  19 #include <fstream>
  20 #include "blocks.h"
  21 using std::ios;
  22 using std::ofstream;
  23 using std::endl;
  24 #endif
  25
  26 #define EXTRA_GAP 0.0001
  27 using namespace vpsc;
  28
  29 double Rectangle::xBorder=0;
  30 double Rectangle::yBorder=0;
  31 /**
  32  * Takes an array of n rectangles and moves them as little as possible
  33  * such that rectangles are separated by at least xBorder horizontally
  34  * and yBorder vertically
  35  *
  36  * Works in three passes:
  37  * 1) removes some overlap horizontally
  38  * 2) removes remaining overlap vertically
  39  * 3) a last horizontal pass removes all overlap starting from original
  40  *    x-positions - this corrects the case where rectangles were moved
  41  *    too much in the first pass.
  42  */
  43 void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder) {
  44         assert(0 <= n);
  45         try {
  46         // The extra gap avoids numerical imprecision problems
  47         Rectangle::setXBorder(xBorder+EXTRA_GAP);
  48         Rectangle::setYBorder(yBorder+EXTRA_GAP);
  49         Variable **vs=new Variable*[n];
  50         for(int i=0;i<n;i++) {
  51                 vs[i]=new Variable(i,0,1);
  52         }
  53         Constraint **cs;
  54         double *oldX = new double[n];
  55         int m=generateXConstraints(n,rs,vs,cs,true);
  56         for(int i=0;i<n;i++) {
  57                 oldX[i]=vs[i]->desiredPosition;
  58         }
  59         Solver vpsc_x(n,vs,m,cs);
  60 #ifdef RECTANGLE_OVERLAP_LOGGING
  61         ofstream f(LOGFILE,ios::app);
  62         f<<"Calling VPSC: Horizontal pass 1"<<endl;
  63         f.close();
  64 #endif
  65         vpsc_x.solve();
  66         for(int i=0;i<n;i++) {
  67                 rs[i]->moveCentreX(vs[i]->position());
  68         }
  69         for(int i = 0; i < m; ++i) {
  70                 delete cs[i];
  71         }
  72         delete [] cs;
  73         // Removing the extra gap here ensures things that were moved to be adjacent to
  74         // one another above are not considered overlapping
  75         Rectangle::setXBorder(Rectangle::xBorder-EXTRA_GAP);
  76         m=generateYConstraints(n,rs,vs,cs);
  77         Solver vpsc_y(n,vs,m,cs);
  78 #ifdef RECTANGLE_OVERLAP_LOGGING
  79         f.open(LOGFILE,ios::app);
  80         f<<"Calling VPSC: Vertical pass"<<endl;
  81         f.close();
  82 #endif
  83         vpsc_y.solve();
  84         for(int i=0;i<n;i++) {
  85                 rs[i]->moveCentreY(vs[i]->position());
  86                 rs[i]->moveCentreX(oldX[i]);
  87         }
  88         delete [] oldX;
  89         for(int i = 0; i < m; ++i) {
  90                 delete cs[i];
  91         }
  92         delete [] cs;
  93         Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP);
  94         m=generateXConstraints(n,rs,vs,cs,false);
  95         Solver vpsc_x2(n,vs,m,cs);
  96 #ifdef RECTANGLE_OVERLAP_LOGGING
  97         f.open(LOGFILE,ios::app);
  98         f<<"Calling VPSC: Horizontal pass 2"<<endl;
  99         f.close();
 100 #endif
 101         vpsc_x2.solve();
 102         for(int i = 0; i < m; ++i) {
 103                 delete cs[i];
 104         }
 105         delete [] cs;
 106         for(int i=0;i<n;i++) {
 107                 rs[i]->moveCentreX(vs[i]->position());
 108                 delete vs[i];
 109         }
 110         delete [] vs;
 111         } catch (char const *str) {
 112                 std::cerr<<str<<std::endl;
 113                 for(int i=0;i<n;i++) {
 114                         std::cerr << *rs[i]<<std::endl;
 115                 }
 116         }
 117 }