src/removeoverlap/generate-constraints.cpp

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