← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/inkscape/oneiric-updates

« back to all changes in this revision

Viewing changes to inkscape-0.47pre1/src/libvpsc/generate-constraints.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Bryce Harrington
  • Date: 2009-07-02 17:09:45 UTC
  • mfrom: (1.1.9 upstream)
  • Revision ID: james.westby@ubuntu.com-20090702170945-nn6d6zswovbwju1t
Tags: 0.47~pre1-0ubuntu1
https://launchpad.net/bugs/348842
https://launchpad.net/bugs/391149
* New upstream release.
  - Don't constrain maximization on small resolution devices (pre0)
    (LP: #348842)
  - Fixes segfault on startup (pre0)
    (LP: #391149)

Show diffs side-by-side

added added

removed removed

Lines of Context:
inkscape-0.47pre1/src/libvpsc/generate-constraints.cpp
 
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
 */
 
12
 
 
13
#include <set>
 
14
#include <cassert>
 
15
#include <cstdlib>
 
16
#include "generate-constraints.h"
 
17
#include "constraint.h"
 
18
 
 
19
#include "2geom/isnan.h" /* Include last */
 
20
 
 
21
using std::set;
 
22
using std::vector;
 
23
 
 
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
}
 
29
 
 
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
}
 
35
 
 
36
struct Node;
 
37
struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
 
38
 
 
39
typedef set<Node*,CmpNodePos> NodeSet;
 
40
 
 
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;
 
86
 
 
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
}
 
104
 
 
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
}
 
135
 
 
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
}
 
164
 
 
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 );
 
180
 
 
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
                                }
 
219
                                
 
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
}
 
251
 
 
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
}