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
  24 using std::set;
  25 using std::vector;
  26 using std::list;
  27
  28 namespace straightener {
  29
  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     }
  96
  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     }
 122
 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);
 163
 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     }
 193
 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 );
 226
 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");
 256
 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 }
 360