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
  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         assert(0 <= n);
  44         try {
  45         // The extra gap avoids numerical imprecision problems
  46         Rectangle::setXBorder(xBorder+EXTRA_GAP);
  47         Rectangle::setYBorder(yBorder+EXTRA_GAP);
  48         Variable **vs=new Variable*[n];
  49         for(int i=0;i<n;i++) {
  50                 vs[i]=new Variable(i,0,1);
  51         }
  52         Constraint **cs;
  53         double *oldX = new double[n];
  54         int m=generateXConstraints(n,rs,vs,cs,true);
  55         for(int i=0;i<n;i++) {
  56                 oldX[i]=vs[i]->desiredPosition;
  57         }
  58         VPSC vpsc_x(n,vs,m,cs);
  59 #ifdef RECTANGLE_OVERLAP_LOGGING
  60         ofstream f(LOGFILE,ios::app);
  61         f<<"Calling VPSC: Horizontal pass 1"<<endl;
  62         f.close();
  63 #endif
  64         vpsc_x.solve();
  65         for(int i=0;i<n;i++) {
  66                 rs[i]->moveCentreX(vs[i]->position());
  67         }
  68         for(int i = 0; i < m; ++i) {
  69                 delete cs[i];
  70         }
  71         delete [] cs;
  72         // Removing the extra gap here ensures things that were moved to be adjacent to
  73         // one another above are not considered overlapping
  74         Rectangle::setXBorder(Rectangle::xBorder-EXTRA_GAP);
  75         m=generateYConstraints(n,rs,vs,cs);
  76         VPSC vpsc_y(n,vs,m,cs);
  77 #ifdef RECTANGLE_OVERLAP_LOGGING
  78         f.open(LOGFILE,ios::app);
  79         f<<"Calling VPSC: Vertical pass"<<endl;
  80         f.close();
  81 #endif
  82         vpsc_y.solve();
  83         for(int i=0;i<n;i++) {
  84                 rs[i]->moveCentreY(vs[i]->position());
  85                 rs[i]->moveCentreX(oldX[i]);
  86         }
  87         delete [] oldX;
  88         for(int i = 0; i < m; ++i) {
  89                 delete cs[i];
  90         }
  91         delete [] cs;
  92         Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP);
  93         m=generateXConstraints(n,rs,vs,cs,false);
  94         VPSC vpsc_x2(n,vs,m,cs);
  95 #ifdef RECTANGLE_OVERLAP_LOGGING
  96         f.open(LOGFILE,ios::app);
  97         f<<"Calling VPSC: Horizontal pass 2"<<endl;
  98         f.close();
  99 #endif
 100         vpsc_x2.solve();
 101         for(int i = 0; i < m; ++i) {
 102                 delete cs[i];
 103         }
 104         delete [] cs;
 105         for(int i=0;i<n;i++) {
 106                 rs[i]->moveCentreX(vs[i]->position());
 107                 delete vs[i];
 108         }
 109         delete [] vs;
 110         } catch (char const *str) {
 111                 std::cerr<<str<<std::endl;
 112                 for(int i=0;i<n;i++) {
 113                         std::cerr << *rs[i]<<std::endl;
 114                 }
 115         }
 116 }