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