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