generate-constraints.cpp

/**
 * \brief Functions to automatically generate constraints for the
 * rectangular node overlap removal problem.
 *
 * Authors:
 *   Tim Dwyer <tgdwyer@gmail.com>
 *
 * Copyright (C) 2005 Authors
 *
 * Released under GNU LGPL.  Read the file 'COPYING' for more information.
 */

#include <set>
#include <cassert>
#include <cstdlib>
#include "generate-constraints.h"
#include "constraint.h"

#include "isnan.h" /* Include last */

using std::set;
using std::vector;

namespace vpsc {
std::ostream& operator <<(std::ostream &os, const Rectangle &r) {
      os << "{"<<r.minX<<","<<r.maxX<<","<<r.minY<<","<<r.maxY<<"},";
      return os;
}

Rectangle::Rectangle(double x, double X, double y, double Y) 
: minX(x),maxX(X),minY(y),maxY(Y) {
            assert(x<=X);
            assert(y<=Y);
}

struct Node;
struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };

typedef set<Node*,CmpNodePos> NodeSet;

struct Node {
      Variable *v;
      Rectangle *r;
      double pos;
      Node *firstAbove, *firstBelow;
      NodeSet *leftNeighbours, *rightNeighbours;
      Node(Variable *v, Rectangle *r, double p) : v(v),r(r),pos(p) {
            firstAbove=firstBelow=NULL;
            leftNeighbours=rightNeighbours=NULL;
            assert(r->width()<1e40);
      }
      ~Node() {
            delete leftNeighbours;
            delete rightNeighbours;
      }
      void addLeftNeighbour(Node *u) {
            leftNeighbours->insert(u);
      }
      void addRightNeighbour(Node *u) {
            rightNeighbours->insert(u);
      }
      void setNeighbours(NodeSet *left, NodeSet *right) {
            leftNeighbours=left;
            rightNeighbours=right;
            for(NodeSet::iterator i=left->begin();i!=left->end();++i) {
                  Node *v=*(i);
                  v->addRightNeighbour(this);
            }
            for(NodeSet::iterator i=right->begin();i!=right->end();++i) {
                  Node *v=*(i);
                  v->addLeftNeighbour(this);
            }
      }
};
bool CmpNodePos::operator() (const Node* u, const Node* v) const {
      if (u->pos < v->pos) {
            return true;
      }
      if (v->pos < u->pos) {
            return false;
      }
      if (isNaN(u->pos) != isNaN(v->pos)) {
            return isNaN(u->pos);
      }
      return u < v;

      /* I don't know how important it is to handle NaN correctly
       * (e.g. we probably handle it badly in other code anyway, and
       * in any case the best we can hope for is to reduce the
       * badness of other nodes).
       *
       * Nevertheless, we try to do the right thing here and in
       * event comparison.  The issue is that (on platforms with
       * ieee floating point comparison) NaN compares neither less
       * than nor greater than any other number, yet sort wants a
       * well-defined ordering.  In particular, we want to ensure
       * transitivity of equivalence, which normally wouldn't be
       * guaranteed if the "middle" item in the transitivity
       * involves a NaN.  (NaN is neither less than nor greater than
       * other numbers, so tends to be considered as equal to all
       * other numbers: even unequal numbers.)
       */
}

NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) {
      NodeSet *leftv = new NodeSet;
      NodeSet::iterator i=scanline.find(v);
      while(i--!=scanline.begin()) {
            Node *u=*(i);
            if(u->r->overlapX(v->r)<=0) {
                  leftv->insert(u);
                  return leftv;
            }
            if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
                  leftv->insert(u);
            }
      }
      return leftv;
}
NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) {
      NodeSet *rightv = new NodeSet;
      NodeSet::iterator i=scanline.find(v);
      for(++i;i!=scanline.end(); ++i) {
            Node *u=*(i);
            if(u->r->overlapX(v->r)<=0) {
                  rightv->insert(u);
                  return rightv;
            }
            if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
                  rightv->insert(u);
            }
      }
      return rightv;
}

typedef enum {Open, Close} EventType;
struct Event {
      EventType type;
      Node *v;
      double pos;
      Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {};
};
Event **events;
int compare_events(const void *a, const void *b) {
      Event *ea=*(Event**)a;
      Event *eb=*(Event**)b;
      if(ea->v->r==eb->v->r) {
            // when comparing opening and closing from the same rect
            // open must come first
            if(ea->type==Open) return -1;
            return 1;
      } else if(ea->pos > eb->pos) {
            return 1;
      } else if(ea->pos < eb->pos) {
            return -1;
      } else if(isNaN(ea->pos) != isNaN(ea->pos)) {
            /* See comment in CmpNodePos. */
            return ( isNaN(ea->pos)
                   ? -1
                   : 1 );
      }
      return 0;
}

/**
 * Prepares constraints in order to apply VPSC horizontally.  Assumes variables have already been created.
 * useNeighbourLists determines whether or not a heuristic is used to deciding whether to resolve
 * all overlap in the x pass, or leave some overlaps for the y pass.
 */
00170 int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists) {
      events=new Event*[2*n];
      int i,m,ctr=0;
      for(i=0;i<n;i++) {
            vars[i]->desiredPosition=rs[i]->getCentreX();
            Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX());
            events[ctr++]=new Event(Open,v,rs[i]->getMinY());
            events[ctr++]=new Event(Close,v,rs[i]->getMaxY());
      }
      qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );

      NodeSet scanline;
      vector<Constraint*> constraints;
      for(i=0;i<2*n;i++) {
            Event *e=events[i];
            Node *v=e->v;
            if(e->type==Open) {
                  scanline.insert(v);
                  if(useNeighbourLists) {
                        v->setNeighbours(
                              getLeftNeighbours(scanline,v),
                              getRightNeighbours(scanline,v)
                        );
                  } else {
                        NodeSet::iterator it=scanline.find(v);
                        if(it--!=scanline.begin()) {
                              Node *u=*it;
                              v->firstAbove=u;
                              u->firstBelow=v;
                        }
                        it=scanline.find(v);
                        if(++it!=scanline.end()) {
                              Node *u=*it;
                              v->firstBelow=u;
                              u->firstAbove=v;
                        }
                  }
            } else {
                  // Close event
                  int r;
                  if(useNeighbourLists) {
                        for(NodeSet::iterator i=v->leftNeighbours->begin();
                              i!=v->leftNeighbours->end();i++
                        ) {
                              Node *u=*i;
                              double sep = (v->r->width()+u->r->width())/2.0;
                              constraints.push_back(new Constraint(u->v,v->v,sep));
                              r=u->rightNeighbours->erase(v);
                        }
                        
                        for(NodeSet::iterator i=v->rightNeighbours->begin();
                              i!=v->rightNeighbours->end();i++
                        ) {
                              Node *u=*i;
                              double sep = (v->r->width()+u->r->width())/2.0;
                              constraints.push_back(new Constraint(v->v,u->v,sep));
                              r=u->leftNeighbours->erase(v);
                        }
                  } else {
                        Node *l=v->firstAbove, *r=v->firstBelow;
                        if(l!=NULL) {
                              double sep = (v->r->width()+l->r->width())/2.0;
                              constraints.push_back(new Constraint(l->v,v->v,sep));
                              l->firstBelow=v->firstBelow;
                        }
                        if(r!=NULL) {
                              double sep = (v->r->width()+r->r->width())/2.0;
                              constraints.push_back(new Constraint(v->v,r->v,sep));
                              r->firstAbove=v->firstAbove;
                        }
                  }
                  r=scanline.erase(v);
                  delete v;
            }
            delete e;
      }
      delete [] events;
      cs=new Constraint*[m=constraints.size()];
      for(i=0;i<m;i++) cs[i]=constraints[i];
      return m;
}

/**
 * Prepares constraints in order to apply VPSC vertically to remove ALL overlap.
 */
00255 int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs) {
      events=new Event*[2*n];
      int ctr=0,i,m;
      for(i=0;i<n;i++) {
            vars[i]->desiredPosition=rs[i]->getCentreY();
            Node *v = new Node(vars[i],rs[i],rs[i]->getCentreY());
            events[ctr++]=new Event(Open,v,rs[i]->getMinX());
            events[ctr++]=new Event(Close,v,rs[i]->getMaxX());
      }
      qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
      NodeSet scanline;
      vector<Constraint*> constraints;
      for(i=0;i<2*n;i++) {
            Event *e=events[i];
            Node *v=e->v;
            if(e->type==Open) {
                  scanline.insert(v);
                  NodeSet::iterator i=scanline.find(v);
                  if(i--!=scanline.begin()) {
                        Node *u=*i;
                        v->firstAbove=u;
                        u->firstBelow=v;
                  }
                  i=scanline.find(v);
                  if(++i!=scanline.end())  {
                        Node *u=*i;
                        v->firstBelow=u;
                        u->firstAbove=v;
                  }
            } else {
                  // Close event
                  Node *l=v->firstAbove, *r=v->firstBelow;
                  if(l!=NULL) {
                        double sep = (v->r->height()+l->r->height())/2.0;
                        constraints.push_back(new Constraint(l->v,v->v,sep));
                        l->firstBelow=v->firstBelow;
                  }
                  if(r!=NULL) {
                        double sep = (v->r->height()+r->r->height())/2.0;
                        constraints.push_back(new Constraint(v->v,r->v,sep));
                        r->firstAbove=v->firstAbove;
                  }
                  scanline.erase(v);
                  delete v;
            }
            delete e;
      }
      delete [] events;
      cs=new Constraint*[m=constraints.size()];
      for(i=0;i<m;i++) cs[i]=constraints[i];
      return m;
}
}