6f6ace03ae0e88af16cc157dd91eb95071aa718c
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 */
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
26 #define EXTRA_GAP 0.0001
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 }