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