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