1 /*
2 ** vim: set cindent
3 ** vim: ts=4 sw=4 et tw=0 wm=0
4 */
5 /**
6 * \brief Functions to automatically generate constraints for the
7 * rectangular node overlap removal problem.
8 *
9 * Authors:
10 * Tim Dwyer <tgdwyer@gmail.com>
11 *
12 * Copyright (C) 2005 Authors
13 *
14 * Released under GNU LGPL. Read the file 'COPYING' for more information.
15 */
17 #include <set>
18 #include <list>
19 #include <cassert>
20 #include "straightener.h"
21 #include <iostream>
22 #include <cmath>
24 using std::set;
25 using std::vector;
26 using std::list;
28 namespace straightener {
30 // is point p on line a-b?
31 static bool pointOnLine(double px,double py, double ax, double ay, double bx, double by, double& tx) {
32 double dx=bx-ax;
33 double dy=by-ay;
34 double ty=0;
35 if(fabs(dx)<0.0001&&fabs(dy)<0.0001) {
36 // runty line!
37 tx=px-ax;
38 ty=py-ay;
39 } else {
40 if(fabs(dx)<0.0001) {
41 //vertical line
42 if(fabs(px-ax)<0.01) {
43 tx=(py-ay)/dy;
44 }
45 } else {
46 tx=(px-ax)/dx;
47 }
48 if(fabs(dy)<0.0001) {
49 //horizontal line
50 if(fabs(py-ay)<0.01) {
51 ty=tx;
52 }
53 } else {
54 ty=(py-ay)/dy;
55 }
56 }
57 //printf(" tx=%f,ty=%f\n",tx,ty);
58 if(fabs(tx-ty)<0.001 && tx>0 && tx<=1) {
59 return true;
60 }
61 return false;
62 }
63 void Edge::nodePath(vector<Node*>& nodes) {
64 list<unsigned> ds(dummyNodes.size());
65 copy(dummyNodes.begin(),dummyNodes.end(),ds.begin());
66 //printf("Edge::nodePath: (%d,%d) dummyNodes:%d\n",startNode,endNode,ds.size());
67 path.clear();
68 path.push_back(startNode);
69 for(unsigned i=1;i<route->n;i++) {
70 //printf(" checking segment %d-%d\n",i-1,i);
71 set<pair<double,unsigned> > pntsOnLineSegment;
72 for(list<unsigned>::iterator j=ds.begin();j!=ds.end();) {
73 double px=nodes[*j]->x;
74 double py=nodes[*j]->y;
75 double ax=route->xs[i-1];
76 double ay=route->ys[i-1];
77 double bx=route->xs[i];
78 double by=route->ys[i];
79 double t=0;
80 list<unsigned>::iterator copyit=j++;
81 //printf(" px=%f, py=%f, ax=%f, ay=%f, bx=%f, by=%f\n",px,py,ax,ay,bx,by);
82 if(pointOnLine(px,py,ax,ay,bx,by,t)) {
83 //printf(" got node %d\n",*copyit);
84 pntsOnLineSegment.insert(make_pair(t,*copyit));
85 ds.erase(copyit);
86 }
87 }
88 for(set<pair<double,unsigned> >::iterator j=pntsOnLineSegment.begin();j!=pntsOnLineSegment.end();j++) {
89 path.push_back(j->second);
90 }
91 //printf("\n");
92 }
93 path.push_back(endNode);
94 assert(ds.empty());
95 }
97 typedef enum {Open, Close} EventType;
98 struct Event {
99 EventType type;
100 Node *v;
101 Edge *e;
102 double pos;
103 Event(EventType t, Node *v, double p) : type(t),v(v),e(NULL),pos(p) {};
104 Event(EventType t, Edge *e, double p) : type(t),v(NULL),e(e),pos(p) {};
105 };
106 Event **events;
107 int compare_events(const void *a, const void *b) {
108 Event *ea=*(Event**)a;
109 Event *eb=*(Event**)b;
110 if(ea->v!=NULL&&ea->v==eb->v||ea->e!=NULL&&ea->e==eb->e) {
111 // when comparing opening and closing from object
112 // open must come first
113 if(ea->type==Open) return -1;
114 return 1;
115 } else if(ea->pos > eb->pos) {
116 return 1;
117 } else if(ea->pos < eb->pos) {
118 return -1;
119 }
120 return 0;
121 }
123 void sortNeighbours(Node* v, Node* l, Node* r,
124 double conjpos, vector<Edge*>& openEdges,
125 vector<Node*>& L,vector<Node*>& nodes, Dim dim) {
126 double minpos=-DBL_MAX, maxpos=DBL_MAX;
127 if(l!=NULL) {
128 L.push_back(l);
129 minpos=l->scanpos;
130 }
131 typedef pair<double,Edge*> PosEdgePair;
132 set<PosEdgePair> sortedEdges;
133 for(unsigned i=0;i<openEdges.size();i++) {
134 Edge *e=openEdges[i];
135 vector<double> bs;
136 if(dim==HORIZONTAL) {
137 e->xpos(conjpos,bs);
138 } else {
139 e->ypos(conjpos,bs);
140 }
141 //cerr << "edge(intersections="<<bs.size()<<":("<<e->startNode<<","<<e->endNode<<"))"<<endl;
142 for(vector<double>::iterator it=bs.begin();it!=bs.end();it++) {
143 sortedEdges.insert(make_pair(*it,e));
144 }
145 }
146 for(set<PosEdgePair>::iterator i=sortedEdges.begin();i!=sortedEdges.end();i++) {
147 double pos=i->first;
148 if(pos < minpos) continue;
149 if(pos > v->scanpos) break;
150 // if edge is connected (start or end) to v then skip
151 // need to record start and end positions of edge segment!
152 Edge* e=i->second;
153 if(e->startNode==v->id||e->endNode==v->id) continue;
154 //if(l!=NULL&&(e->startNode==l->id||e->endNode==l->id)) continue;
155 //cerr << "edge("<<e->startNode<<","<<e->endNode<<",pts="<<e->pts<<")"<<endl;
156 Node* d=dim==HORIZONTAL?
157 new Node(nodes.size(),pos,conjpos,e):
158 new Node(nodes.size(),conjpos,pos,e);
159 L.push_back(d);
160 nodes.push_back(d);
161 }
162 L.push_back(v);
164 if(r!=NULL) {
165 maxpos=r->scanpos;
166 }
167 for(set<PosEdgePair>::iterator i=sortedEdges.begin();i!=sortedEdges.end();i++) {
168 if(i->first < v->scanpos) continue;
169 if(i->first > maxpos) break;
170 double pos=i->first;
171 // if edge is connected (start or end) to v then skip
172 // need to record start and end positions of edge segment!
173 Edge* e=i->second;
174 if(e->startNode==v->id||e->endNode==v->id) continue;
175 //if(r!=NULL&&(e->startNode==r->id||e->endNode==r->id)) continue;
176 //cerr << "edge("<<e->startNode<<","<<e->endNode<<",pts="<<e->pts<<")"<<endl;
177 Node* d=dim==HORIZONTAL?
178 new Node(nodes.size(),pos,conjpos,e):
179 new Node(nodes.size(),conjpos,pos,e);
180 L.push_back(d);
181 nodes.push_back(d);
182 }
183 if(r!=NULL) {
184 L.push_back(r);
185 }
186 }
187 static SimpleConstraint* createConstraint(Node* u, Node* v, Dim dim) {
188 double g=dim==HORIZONTAL?(u->width+v->width):(u->height+v->height);
189 g/=2;
190 //cerr << "Constraint: "<< u->id << "+"<<g<<"<="<<v->id<<endl;
191 return new SimpleConstraint(u->id,v->id,g);
192 }
194 void generateConstraints(vector<Node*>& nodes, vector<Edge*>& edges,vector<SimpleConstraint*>& cs,Dim dim) {
195 unsigned nevents=2*nodes.size()+2*edges.size();
196 events=new Event*[nevents];
197 unsigned ctr=0;
198 if(dim==HORIZONTAL) {
199 //cout << "Scanning top to bottom..." << endl;
200 for(unsigned i=0;i<nodes.size();i++) {
201 Node *v=nodes[i];
202 v->scanpos=v->x;
203 events[ctr++]=new Event(Open,v,v->ymin+0.01);
204 events[ctr++]=new Event(Close,v,v->ymax-0.01);
205 }
206 for(unsigned i=0;i<edges.size();i++) {
207 Edge *e=edges[i];
208 events[ctr++]=new Event(Open,e,e->ymin-1);
209 events[ctr++]=new Event(Close,e,e->ymax+1);
210 }
211 } else {
212 //cout << "Scanning left to right..." << endl;
213 for(unsigned i=0;i<nodes.size();i++) {
214 Node *v=nodes[i];
215 v->scanpos=v->y;
216 events[ctr++]=new Event(Open,v,v->xmin+0.01);
217 events[ctr++]=new Event(Close,v,v->xmax-0.01);
218 }
219 for(unsigned i=0;i<edges.size();i++) {
220 Edge *e=edges[i];
221 events[ctr++]=new Event(Open,e,e->xmin-1);
222 events[ctr++]=new Event(Close,e,e->xmax+1);
223 }
224 }
225 qsort((Event*)events, (size_t)nevents, sizeof(Event*), compare_events );
227 NodeSet openNodes;
228 vector<Edge*> openEdges;
229 for(unsigned i=0;i<nevents;i++) {
230 Event *e=events[i];
231 Node *v=e->v;
232 if(v!=NULL) {
233 v->open = true;
234 //printf("NEvent@%f,nid=%d,(%f,%f),w=%f,h=%f,openn=%d,opene=%d\n",e->pos,v->id,v->x,v->y,v->width,v->height,(int)openNodes.size(),(int)openEdges.size());
235 Node *l=NULL, *r=NULL;
236 if(!openNodes.empty()) {
237 // it points to the first node to the right of v
238 NodeSet::iterator it=openNodes.lower_bound(v);
239 // step left to find the first node to the left of v
240 if(it--!=openNodes.begin()) {
241 l=*it;
242 //printf("l=%d\n",l->id);
243 }
244 it=openNodes.upper_bound(v);
245 if(it!=openNodes.end()) {
246 r=*it;
247 }
248 }
249 vector<Node*> L;
250 sortNeighbours(v,l,r,e->pos,openEdges,L,nodes,dim);
251 //printf("L=[");
252 for(unsigned i=0;i<L.size();i++) {
253 //printf("%d ",L[i]->id);
254 }
255 //printf("]\n");
257 // Case A: create constraints between adjacent edges skipping edges joined
258 // to l,v or r.
259 Node* lastNode=NULL;
260 for(vector<Node*>::iterator i=L.begin();i!=L.end();i++) {
261 if((*i)->dummy) {
262 // node is on an edge
263 Edge *edge=(*i)->edge;
264 if(!edge->isEnd(v->id)
265 &&(l!=NULL&&!edge->isEnd(l->id)||l==NULL)
266 &&(r!=NULL&&!edge->isEnd(r->id)||r==NULL)) {
267 if(lastNode!=NULL) {
268 //printf(" Rule A: Constraint: v%d +g <= v%d\n",lastNode->id,(*i)->id);
269 cs.push_back(createConstraint(lastNode,*i,dim));
270 }
271 lastNode=*i;
272 }
273 } else {
274 // is an actual node
275 lastNode=NULL;
276 }
277 }
278 // Case B: create constraints for all the edges connected to the right of
279 // their own end, also in the scan line
280 vector<Node*> skipList;
281 lastNode=NULL;
282 for(vector<Node*>::iterator i=L.begin();i!=L.end();i++) {
283 if((*i)->dummy) {
284 // node is on an edge
285 if(lastNode!=NULL) {
286 if((*i)->edge->isEnd(lastNode->id)) {
287 skipList.push_back(*i);
288 } else {
289 for(vector<Node*>::iterator j=skipList.begin();
290 j!=skipList.end();j++) {
291 //printf(" Rule B: Constraint: v%d +g <= v%d\n",(*j)->id,(*i)->id);
292 cs.push_back(createConstraint(*j,*i,dim));
293 }
294 skipList.clear();
295 }
296 }
297 } else {
298 // is an actual node
299 skipList.clear();
300 skipList.push_back(*i);
301 lastNode=*i;
302 }
303 }
304 skipList.clear();
305 // Case C: reverse of B
306 lastNode=NULL;
307 for(vector<Node*>::reverse_iterator i=L.rbegin();i!=L.rend();i++) {
308 if((*i)->dummy) {
309 // node is on an edge
310 if(lastNode!=NULL) {
311 if((*i)->edge->isEnd(lastNode->id)) {
312 skipList.push_back(*i);
313 } else {
314 for(vector<Node*>::iterator j=skipList.begin();
315 j!=skipList.end();j++) {
316 //printf(" Rule C: Constraint: v%d +g <= v%d\n",(*i)->id,(*j)->id);
317 cs.push_back(createConstraint(*i,*j,dim));
318 }
319 skipList.clear();
320 }
321 }
322 } else {
323 // is an actual node
324 skipList.clear();
325 skipList.push_back(*i);
326 lastNode=*i;
327 }
328 }
329 if(e->type==Close) {
330 if(l!=NULL) cs.push_back(createConstraint(l,v,dim));
331 if(r!=NULL) cs.push_back(createConstraint(v,r,dim));
332 }
333 }
334 if(e->type==Open) {
335 if(v!=NULL) {
336 openNodes.insert(v);
337 } else {
338 //printf("EdgeOpen@%f,eid=%d,(u,v)=(%d,%d)\n", e->pos,e->e->id,e->e->startNode,e->e->endNode);
339 e->e->openInd=openEdges.size();
340 openEdges.push_back(e->e);
341 }
342 } else {
343 // Close
344 if(v!=NULL) {
345 openNodes.erase(v);
346 v->open=false;
347 } else {
348 //printf("EdgeClose@%f,eid=%d,(u,v)=(%d,%d)\n", e->pos,e->e->id,e->e->startNode,e->e->endNode);
349 unsigned i=e->e->openInd;
350 openEdges[i]=openEdges[openEdges.size()-1];
351 openEdges[i]->openInd=i;
352 openEdges.resize(openEdges.size()-1);
353 }
354 }
355 delete e;
356 }
357 delete [] events;
358 }
359 }