src/libcola/straightener.cpp

   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  */
  16
  17 #include <set>
  18 #include <list>
  19 #include <cassert>
  20 #include "straightener.h"
  21 #include <iostream>
  22 #include <cmath>
  23 #include <cstdlib>
  24
  25 using std::set;
  26 using std::vector;
  27 using std::list;
  28
  29 namespace straightener {
  30
  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     }
  97
  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     }
 123
 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);
 164
 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     }
 194
 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 );
 227
 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");
 257
 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 }
 361