src/removeoverlap/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
  28 double Rectangle::xBorder=0;
  29 double Rectangle::yBorder=0;
  30 /**
  31  * Takes an array of n rectangles and moves them as little as possible
  32  * such that rectangles are separated by at least xBorder horizontally
  33  * and yBorder vertically
  34  *
  35  * Works in three passes:
  36  * 1) removes some overlap horizontally
  37  * 2) removes remaining overlap vertically
  38  * 3) a last horizontal pass removes all overlap starting from original
  39  *    x-positions - this corrects the case where rectangles were moved
  40  *    too much in the first pass.
  41  */
  42 void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder) {
  43         try {
  44         // The extra gap avoids numerical imprecision problems
  45         Rectangle::setXBorder(xBorder+EXTRA_GAP);
  46         Rectangle::setYBorder(yBorder+EXTRA_GAP);
  47         Variable **vs=new Variable*[n];
  48         for(unsigned int i=0;i<n;i++) {
  49                 vs[i]=new Variable(i,0,1);
  50         }
  51         Constraint **cs;
  52         double *oldX = new double[n];
  53         int m=generateXConstraints(n,rs,vs,cs,true);
  54         for(unsigned int i=0;i<n;i++) {
  55                 oldX[i]=vs[i]->desiredPosition;
  56         }
  57         VPSC vpsc_x(n,vs,m,cs);
  58 #ifdef RECTANGLE_OVERLAP_LOGGING
  59         ofstream f(LOGFILE,ios::app);
  60         f<<"Calling VPSC: Horizontal pass 1"<<endl;
  61         f.close();
  62 #endif
  63         vpsc_x.solve();
  64         for(unsigned int i=0;i<n;i++) {
  65                 rs[i]->moveCentreX(vs[i]->position());
  66         }
  67         for(int i = 0; i < m; ++i) {
  68                 delete cs[i];
  69         }
  70         delete [] cs;
  71         // Removing the extra gap here ensures things that were moved to be adjacent to
  72         // one another above are not considered overlapping
  73         Rectangle::setXBorder(Rectangle::xBorder-EXTRA_GAP);
  74         m=generateYConstraints(n,rs,vs,cs);
  75         VPSC vpsc_y(n,vs,m,cs);
  76 #ifdef RECTANGLE_OVERLAP_LOGGING
  77         f.open(LOGFILE,ios::app);
  78         f<<"Calling VPSC: Vertical pass"<<endl;
  79         f.close();
  80 #endif
  81         vpsc_y.solve();
  82         for(unsigned int i=0;i<n;i++) {
  83                 rs[i]->moveCentreY(vs[i]->position());
  84                 rs[i]->moveCentreX(oldX[i]);
  85         }
  86         delete [] oldX;
  87         for(int i = 0; i < m; ++i) {
  88                 delete cs[i];
  89         }
  90         delete [] cs;
  91         Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP);
  92         m=generateXConstraints(n,rs,vs,cs,false);
  93         VPSC vpsc_x2(n,vs,m,cs);
  94 #ifdef RECTANGLE_OVERLAP_LOGGING
  95         f.open(LOGFILE,ios::app);
  96         f<<"Calling VPSC: Horizontal pass 2"<<endl;
  97         f.close();
  98 #endif
  99         vpsc_x2.solve();
 100         for(int i = 0; i < m; ++i) {
 101                 delete cs[i];
 102         }
 103         delete [] cs;
 104         for(unsigned int i=0;i<n;i++) {
 105                 rs[i]->moveCentreX(vs[i]->position());
 106                 delete vs[i];
 107         }
 108         delete [] vs;
 109         } catch (char const *str) {
 110                 std::cerr<<str<<std::endl;
 111                 for(unsigned int i=0;i<n;i++) {
 112                         std::cerr << *rs[i]<<std::endl;
 113                 }
 114         }
 115 }