1 /**
2 * \brief Remove overlaps function
3 *
4 * Authors:
5 * Tim Dwyer <tgdwyer@gmail.com>
6 *
7 * Copyright (C) 2005 Authors
8 *
9 * Released under GNU GPL. Read the file 'COPYING' for more information.
10 */
12 #include <set>
13 #include <cassert>
14 #include "generate-constraints.h"
15 #include "constraint.h"
17 #include "isnan.h" /* Include last */
19 using std::set;
20 using std::vector;
22 std::ostream& operator <<(std::ostream &os, const Rectangle &r) {
23 os << "{"<<r.minX<<","<<r.maxX<<","<<r.minY<<","<<r.maxY<<"},";
24 return os;
25 }
26 Rectangle::Rectangle(double x, double X, double y, double Y)
27 : minX(x),maxX(X),minY(y),maxY(Y) {
28 assert(x<=X);
29 assert(y<=Y);
30 }
32 struct Node;
33 struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
35 typedef set<Node*,CmpNodePos> NodeSet;
37 struct Node {
38 Variable *v;
39 Rectangle *r;
40 double pos;
41 Node *firstAbove, *firstBelow;
42 NodeSet *leftNeighbours, *rightNeighbours;
43 Node(Variable *v, Rectangle *r, double p) : v(v),r(r),pos(p) {
44 firstAbove=firstBelow=NULL;
45 leftNeighbours=rightNeighbours=NULL;
46 assert(r->width()<1e40);
47 }
48 ~Node() {
49 delete leftNeighbours;
50 delete rightNeighbours;
51 }
52 void addLeftNeighbour(Node *u) {
53 leftNeighbours->insert(u);
54 }
55 void addRightNeighbour(Node *u) {
56 rightNeighbours->insert(u);
57 }
58 void setNeighbours(NodeSet *left, NodeSet *right) {
59 leftNeighbours=left;
60 rightNeighbours=right;
61 for(NodeSet::iterator i=left->begin();i!=left->end();i++) {
62 Node *v=*(i);
63 v->addRightNeighbour(this);
64 }
65 for(NodeSet::iterator i=right->begin();i!=right->end();i++) {
66 Node *v=*(i);
67 v->addLeftNeighbour(this);
68 }
69 }
70 };
71 bool CmpNodePos::operator() (const Node* u, const Node* v) const {
72 if (u->pos < v->pos) {
73 return true;
74 }
75 if (v->pos < u->pos) {
76 return false;
77 }
78 if (isNaN(u->pos) != isNaN(v->pos)) {
79 return isNaN(u->pos);
80 }
81 return u < v;
83 /* I don't know how important it is to handle NaN correctly
84 * (e.g. we probably handle it badly in other code anyway, and
85 * in any case the best we can hope for is to reduce the
86 * badness of other nodes).
87 *
88 * Nevertheless, we try to do the right thing here and in
89 * event comparison. The issue is that (on platforms with
90 * ieee floating point comparison) NaN compares neither less
91 * than nor greater than any other number, yet sort wants a
92 * well-defined ordering. In particular, we want to ensure
93 * transitivity of equivalence, which normally wouldn't be
94 * guaranteed if the "middle" item in the transitivity
95 * involves a NaN. (NaN is neither less than nor greater than
96 * other numbers, so tends to be considered as equal to all
97 * other numbers: even unequal numbers.)
98 */
99 }
101 NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) {
102 NodeSet *leftv = new NodeSet;
103 NodeSet::iterator i=scanline.find(v);
104 while(i--!=scanline.begin()) {
105 Node *u=*(i);
106 if(u->r->overlapX(v->r)<=0) {
107 leftv->insert(u);
108 return leftv;
109 }
110 if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
111 leftv->insert(u);
112 }
113 }
114 return leftv;
115 }
116 NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) {
117 NodeSet *rightv = new NodeSet;
118 NodeSet::iterator i=scanline.find(v);
119 for(i++;i!=scanline.end(); i++) {
120 Node *u=*(i);
121 if(u->r->overlapX(v->r)<=0) {
122 rightv->insert(u);
123 return rightv;
124 }
125 if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
126 rightv->insert(u);
127 }
128 }
129 return rightv;
130 }
132 typedef enum {Open, Close} EventType;
133 struct Event {
134 EventType type;
135 Node *v;
136 double pos;
137 Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {};
138 };
139 Event **events;
140 int compare_events(const void *a, const void *b) {
141 Event *ea=*(Event**)a;
142 Event *eb=*(Event**)b;
143 if(ea->v->r==eb->v->r) {
144 // when comparing opening and closing from the same rect
145 // open must come first
146 if(ea->type==Open) return -1;
147 return 1;
148 } else if(ea->pos > eb->pos) {
149 return 1;
150 } else if(ea->pos < eb->pos) {
151 return -1;
152 } else if(isNaN(ea->pos) != isNaN(ea->pos)) {
153 /* See comment in CmpNodePos. */
154 return ( isNaN(ea->pos)
155 ? -1
156 : 1 );
157 }
158 return 0;
159 }
161 /**
162 * Prepares variables and constraints in order to apply VPSC horizontally.
163 * useNeighbourLists determines whether or not a heuristic is used to deciding whether to resolve
164 * all overlap in the x pass, or leave some overlaps for the y pass.
165 */
166 int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs, bool useNeighbourLists) {
167 events=new Event*[2*n];
168 int i,m,ctr=0;
169 vector<Constraint*> constraints;
170 vars=new Variable*[n];
171 for(i=0;i<n;i++) {
172 vars[i]=new Variable(i,rs[i]->getCentreX(),weights[i]);
173 Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX());
174 events[ctr++]=new Event(Open,v,rs[i]->getMinY());
175 events[ctr++]=new Event(Close,v,rs[i]->getMaxY());
176 }
177 qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
179 NodeSet scanline;
180 for(i=0;i<2*n;i++) {
181 Event *e=events[i];
182 Node *v=e->v;
183 if(e->type==Open) {
184 scanline.insert(v);
185 if(useNeighbourLists) {
186 v->setNeighbours(
187 getLeftNeighbours(scanline,v),
188 getRightNeighbours(scanline,v)
189 );
190 } else {
191 NodeSet::iterator it=scanline.find(v);
192 if(it--!=scanline.begin()) {
193 Node *u=*it;
194 v->firstAbove=u;
195 u->firstBelow=v;
196 }
197 it=scanline.find(v);
198 if(++it!=scanline.end()) {
199 Node *u=*it;
200 v->firstBelow=u;
201 u->firstAbove=v;
202 }
203 }
204 } else {
205 // Close event
206 int r;
207 if(useNeighbourLists) {
208 for(NodeSet::iterator i=v->leftNeighbours->begin();
209 i!=v->leftNeighbours->end();i++
210 ) {
211 Node *u=*i;
212 double sep = (v->r->width()+u->r->width())/2.0;
213 constraints.push_back(new Constraint(u->v,v->v,sep));
214 r=u->rightNeighbours->erase(v);
215 }
217 for(NodeSet::iterator i=v->rightNeighbours->begin();
218 i!=v->rightNeighbours->end();i++
219 ) {
220 Node *u=*i;
221 double sep = (v->r->width()+u->r->width())/2.0;
222 constraints.push_back(new Constraint(v->v,u->v,sep));
223 r=u->leftNeighbours->erase(v);
224 }
225 } else {
226 Node *l=v->firstAbove, *r=v->firstBelow;
227 if(l!=NULL) {
228 double sep = (v->r->width()+l->r->width())/2.0;
229 constraints.push_back(new Constraint(l->v,v->v,sep));
230 l->firstBelow=v->firstBelow;
231 }
232 if(r!=NULL) {
233 double sep = (v->r->width()+r->r->width())/2.0;
234 constraints.push_back(new Constraint(v->v,r->v,sep));
235 r->firstAbove=v->firstAbove;
236 }
237 }
238 r=scanline.erase(v);
239 delete v;
240 }
241 delete e;
242 }
243 delete [] events;
244 cs=new Constraint*[m=constraints.size()];
245 for(i=0;i<m;i++) cs[i]=constraints[i];
246 return m;
247 }
249 /**
250 * Prepares variables and constraints in order to apply VPSC vertically to remove ALL overlap.
251 */
252 int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs) {
253 events=new Event*[2*n];
254 int ctr=0,i,m;
255 vector<Constraint*> constraints;
256 vars=new Variable*[n];
257 for(i=0;i<n;i++) {
258 vars[i]=new Variable(i,rs[i]->getCentreY(),weights[i]);
259 Node *v = new Node(vars[i],rs[i],rs[i]->getCentreY());
260 events[ctr++]=new Event(Open,v,rs[i]->getMinX());
261 events[ctr++]=new Event(Close,v,rs[i]->getMaxX());
262 }
263 qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
264 NodeSet scanline;
265 for(i=0;i<2*n;i++) {
266 Event *e=events[i];
267 Node *v=e->v;
268 if(e->type==Open) {
269 scanline.insert(v);
270 NodeSet::iterator i=scanline.find(v);
271 if(i--!=scanline.begin()) {
272 Node *u=*i;
273 v->firstAbove=u;
274 u->firstBelow=v;
275 }
276 i=scanline.find(v);
277 if(++i!=scanline.end()) {
278 Node *u=*i;
279 v->firstBelow=u;
280 u->firstAbove=v;
281 }
282 } else {
283 // Close event
284 Node *l=v->firstAbove, *r=v->firstBelow;
285 if(l!=NULL) {
286 double sep = (v->r->height()+l->r->height())/2.0;
287 constraints.push_back(new Constraint(l->v,v->v,sep));
288 l->firstBelow=v->firstBelow;
289 }
290 if(r!=NULL) {
291 double sep = (v->r->height()+r->r->height())/2.0;
292 constraints.push_back(new Constraint(v->v,r->v,sep));
293 r->firstAbove=v->firstAbove;
294 }
295 scanline.erase(v);
296 delete v;
297 }
298 delete e;
299 }
300 delete [] events;
301 cs=new Constraint*[m=constraints.size()];
302 for(i=0;i<m;i++) cs[i]=constraints[i];
303 return m;
304 }