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 "generate-constraints.h"
  16 #include "constraint.h"
  17
  18 #include "isnan.h" /* Include last */
  19
  20 using std::set;
  21 using std::vector;
  22
  23 std::ostream& operator <<(std::ostream &os, const Rectangle &r) {
  24         os << "{"<<r.minX<<","<<r.maxX<<","<<r.minY<<","<<r.maxY<<"},";
  25         return os;
  26 }
  27 Rectangle::Rectangle(double x, double X, double y, double Y)
  28 : minX(x),maxX(X),minY(y),maxY(Y) {
  29                 assert(x<=X);
  30                 assert(y<=Y);
  31 }
  32
  33 struct Node;
  34 struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
  35
  36 typedef set<Node*,CmpNodePos> NodeSet;
  37
  38 struct Node {
  39         Variable *v;
  40         Rectangle *r;
  41         double pos;
  42         Node *firstAbove, *firstBelow;
  43         NodeSet *leftNeighbours, *rightNeighbours;
  44         Node(Variable *v, Rectangle *r, double p) : v(v),r(r),pos(p) {
  45                 firstAbove=firstBelow=NULL;
  46                 leftNeighbours=rightNeighbours=NULL;
  47                 assert(r->width()<1e40);
  48         }
  49         ~Node() {
  50                 delete leftNeighbours;
  51                 delete rightNeighbours;
  52         }
  53         void addLeftNeighbour(Node *u) {
  54                 leftNeighbours->insert(u);
  55         }
  56         void addRightNeighbour(Node *u) {
  57                 rightNeighbours->insert(u);
  58         }
  59         void setNeighbours(NodeSet *left, NodeSet *right) {
  60                 leftNeighbours=left;
  61                 rightNeighbours=right;
  62                 for(NodeSet::iterator i=left->begin();i!=left->end();++i) {
  63                         Node *v=*(i);
  64                         v->addRightNeighbour(this);
  65                 }
  66                 for(NodeSet::iterator i=right->begin();i!=right->end();++i) {
  67                         Node *v=*(i);
  68                         v->addLeftNeighbour(this);
  69                 }
  70         }
  71 };
  72 bool CmpNodePos::operator() (const Node* u, const Node* v) const {
  73         if (u->pos < v->pos) {
  74                 return true;
  75         }
  76         if (v->pos < u->pos) {
  77                 return false;
  78         }
  79         if (isNaN(u->pos) != isNaN(v->pos)) {
  80                 return isNaN(u->pos);
  81         }
  82         return u < v;
  83
  84         /* I don't know how important it is to handle NaN correctly
  85          * (e.g. we probably handle it badly in other code anyway, and
  86          * in any case the best we can hope for is to reduce the
  87          * badness of other nodes).
  88          *
  89          * Nevertheless, we try to do the right thing here and in
  90          * event comparison.  The issue is that (on platforms with
  91          * ieee floating point comparison) NaN compares neither less
  92          * than nor greater than any other number, yet sort wants a
  93          * well-defined ordering.  In particular, we want to ensure
  94          * transitivity of equivalence, which normally wouldn't be
  95          * guaranteed if the "middle" item in the transitivity
  96          * involves a NaN.  (NaN is neither less than nor greater than
  97          * other numbers, so tends to be considered as equal to all
  98          * other numbers: even unequal numbers.)
  99          */
 100 }
 101
 102 NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) {
 103         NodeSet *leftv = new NodeSet;
 104         NodeSet::iterator i=scanline.find(v);
 105         while(i--!=scanline.begin()) {
 106                 Node *u=*(i);
 107                 if(u->r->overlapX(v->r)<=0) {
 108                         leftv->insert(u);
 109                         return leftv;
 110                 }
 111                 if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
 112                         leftv->insert(u);
 113                 }
 114         }
 115         return leftv;
 116 }
 117 NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) {
 118         NodeSet *rightv = new NodeSet;
 119         NodeSet::iterator i=scanline.find(v);
 120         for(++i;i!=scanline.end(); ++i) {
 121                 Node *u=*(i);
 122                 if(u->r->overlapX(v->r)<=0) {
 123                         rightv->insert(u);
 124                         return rightv;
 125                 }
 126                 if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
 127                         rightv->insert(u);
 128                 }
 129         }
 130         return rightv;
 131 }
 132
 133 typedef enum {Open, Close} EventType;
 134 struct Event {
 135         EventType type;
 136         Node *v;
 137         double pos;
 138         Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {};
 139 };
 140 Event **events;
 141 int compare_events(const void *a, const void *b) {
 142         Event *ea=*(Event**)a;
 143         Event *eb=*(Event**)b;
 144         if(ea->v->r==eb->v->r) {
 145                 // when comparing opening and closing from the same rect
 146                 // open must come first
 147                 if(ea->type==Open) return -1;
 148                 return 1;
 149         } else if(ea->pos > eb->pos) {
 150                 return 1;
 151         } else if(ea->pos < eb->pos) {
 152                 return -1;
 153         } else if(isNaN(ea->pos) != isNaN(ea->pos)) {
 154                 /* See comment in CmpNodePos. */
 155                 return ( isNaN(ea->pos)
 156                          ? -1
 157                          : 1 );
 158         }
 159         return 0;
 160 }
 161
 162 /**
 163  * Prepares constraints in order to apply VPSC horizontally.  Assumes variables have already been created.
 164  * useNeighbourLists determines whether or not a heuristic is used to deciding whether to resolve
 165  * all overlap in the x pass, or leave some overlaps for the y pass.
 166  */
 167 int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists) {
 168         events=new Event*[2*n];
 169         int i,m,ctr=0;
 170         for(i=0;i<n;i++) {
 171                 vars[i]->desiredPosition=rs[i]->getCentreX();
 172                 Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX());
 173                 events[ctr++]=new Event(Open,v,rs[i]->getMinY());
 174                 events[ctr++]=new Event(Close,v,rs[i]->getMaxY());
 175         }
 176         qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
 177
 178         NodeSet scanline;
 179         vector<Constraint*> constraints;
 180         for(i=0;i<2*n;i++) {
 181                 Event *e=events[i];
 182                 Node *v=e->v;
 183                 if(e->type==Open) {
 184                         scanline.insert(v);
 185                         if(useNeighbourLists) {
 186                                 v->setNeighbours(
 187                                         getLeftNeighbours(scanline,v),
 188                                         getRightNeighbours(scanline,v)
 189                                 );
 190                         } else {
 191                                 NodeSet::iterator it=scanline.find(v);
 192                                 if(it--!=scanline.begin()) {
 193                                         Node *u=*it;
 194                                         v->firstAbove=u;
 195                                         u->firstBelow=v;
 196                                 }
 197                                 it=scanline.find(v);
 198                                 if(++it!=scanline.end()) {
 199                                         Node *u=*it;
 200                                         v->firstBelow=u;
 201                                         u->firstAbove=v;
 202                                 }
 203                         }
 204                 } else {
 205                         // Close event
 206                         int r;
 207                         if(useNeighbourLists) {
 208                                 for(NodeSet::iterator i=v->leftNeighbours->begin();
 209                                         i!=v->leftNeighbours->end();i++
 210                                 ) {
 211                                         Node *u=*i;
 212                                         double sep = (v->r->width()+u->r->width())/2.0;
 213                                         constraints.push_back(new Constraint(u->v,v->v,sep));
 214                                         r=u->rightNeighbours->erase(v);
 215                                 }
 216
 217                                 for(NodeSet::iterator i=v->rightNeighbours->begin();
 218                                         i!=v->rightNeighbours->end();i++
 219                                 ) {
 220                                         Node *u=*i;
 221                                         double sep = (v->r->width()+u->r->width())/2.0;
 222                                         constraints.push_back(new Constraint(v->v,u->v,sep));
 223                                         r=u->leftNeighbours->erase(v);
 224                                 }
 225                         } else {
 226                                 Node *l=v->firstAbove, *r=v->firstBelow;
 227                                 if(l!=NULL) {
 228                                         double sep = (v->r->width()+l->r->width())/2.0;
 229                                         constraints.push_back(new Constraint(l->v,v->v,sep));
 230                                         l->firstBelow=v->firstBelow;
 231                                 }
 232                                 if(r!=NULL) {
 233                                         double sep = (v->r->width()+r->r->width())/2.0;
 234                                         constraints.push_back(new Constraint(v->v,r->v,sep));
 235                                         r->firstAbove=v->firstAbove;
 236                                 }
 237                         }
 238                         r=scanline.erase(v);
 239                         delete v;
 240                 }
 241                 delete e;
 242         }
 243         delete [] events;
 244         cs=new Constraint*[m=constraints.size()];
 245         for(i=0;i<m;i++) cs[i]=constraints[i];
 246         return m;
 247 }
 248
 249 /**
 250  * Prepares constraints in order to apply VPSC vertically to remove ALL overlap.
 251  */
 252 int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs) {
 253         events=new Event*[2*n];
 254         int ctr=0,i,m;
 255         for(i=0;i<n;i++) {
 256                 vars[i]->desiredPosition=rs[i]->getCentreY();
 257                 Node *v = new Node(vars[i],rs[i],rs[i]->getCentreY());
 258                 events[ctr++]=new Event(Open,v,rs[i]->getMinX());
 259                 events[ctr++]=new Event(Close,v,rs[i]->getMaxX());
 260         }
 261         qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
 262         NodeSet scanline;
 263         vector<Constraint*> constraints;
 264         for(i=0;i<2*n;i++) {
 265                 Event *e=events[i];
 266                 Node *v=e->v;
 267                 if(e->type==Open) {
 268                         scanline.insert(v);
 269                         NodeSet::iterator i=scanline.find(v);
 270                         if(i--!=scanline.begin()) {
 271                                 Node *u=*i;
 272                                 v->firstAbove=u;
 273                                 u->firstBelow=v;
 274                         }
 275                         i=scanline.find(v);
 276                         if(++i!=scanline.end())  {
 277                                 Node *u=*i;
 278                                 v->firstBelow=u;
 279                                 u->firstAbove=v;
 280                         }
 281                 } else {
 282                         // Close event
 283                         Node *l=v->firstAbove, *r=v->firstBelow;
 284                         if(l!=NULL) {
 285                                 double sep = (v->r->height()+l->r->height())/2.0;
 286                                 constraints.push_back(new Constraint(l->v,v->v,sep));
 287                                 l->firstBelow=v->firstBelow;
 288                         }
 289                         if(r!=NULL) {
 290                                 double sep = (v->r->height()+r->r->height())/2.0;
 291                                 constraints.push_back(new Constraint(v->v,r->v,sep));
 292                                 r->firstAbove=v->firstAbove;
 293                         }
 294                         scanline.erase(v);
 295                         delete v;
 296                 }
 297                 delete e;
 298         }
 299         delete [] events;
 300         cs=new Constraint*[m=constraints.size()];
 301         for(i=0;i<m;i++) cs[i]=constraints[i];
 302         return m;
 303 }