generate-constraints.cpp revision 6af8609f35d86944763dc80141002c548984b2ed
2N/A/**
2N/A * \brief Functions to automatically generate constraints for the
2N/A * rectangular node overlap removal problem.
2N/A *
2N/A * Authors:
2N/A * Tim Dwyer <tgdwyer@gmail.com>
2N/A *
2N/A * Copyright (C) 2005 Authors
2N/A *
2N/A * Released under GNU LGPL. Read the file 'COPYING' for more information.
2N/A */
2N/A
2N/A#include <set>
2N/A#include <cassert>
2N/A#include "generate-constraints.h"
2N/A#include "constraint.h"
2N/A
2N/A#include "isnan.h" /* Include last */
2N/A
2N/Ausing std::set;
2N/Ausing std::vector;
2N/A
2N/Astd::ostream& operator <<(std::ostream &os, const Rectangle &r) {
2N/A os << "{"<<r.minX<<","<<r.maxX<<","<<r.minY<<","<<r.maxY<<"},";
2N/A return os;
2N/A}
2N/ARectangle::Rectangle(double x, double X, double y, double Y)
2N/A: minX(x),maxX(X),minY(y),maxY(Y) {
2N/A assert(x<=X);
2N/A assert(y<=Y);
2N/A}
2N/A
2N/Astruct Node;
2N/Astruct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
2N/A
2N/Atypedef set<Node*,CmpNodePos> NodeSet;
2N/A
2N/Astruct Node {
2N/A Variable *v;
2N/A Rectangle *r;
2N/A double pos;
2N/A Node *firstAbove, *firstBelow;
2N/A NodeSet *leftNeighbours, *rightNeighbours;
2N/A Node(Variable *v, Rectangle *r, double p) : v(v),r(r),pos(p) {
2N/A firstAbove=firstBelow=NULL;
2N/A leftNeighbours=rightNeighbours=NULL;
2N/A assert(r->width()<1e40);
2N/A }
2N/A ~Node() {
2N/A delete leftNeighbours;
2N/A delete rightNeighbours;
2N/A }
2N/A void addLeftNeighbour(Node *u) {
2N/A leftNeighbours->insert(u);
2N/A }
2N/A void addRightNeighbour(Node *u) {
2N/A rightNeighbours->insert(u);
2N/A }
2N/A void setNeighbours(NodeSet *left, NodeSet *right) {
2N/A leftNeighbours=left;
2N/A rightNeighbours=right;
2N/A for(NodeSet::iterator i=left->begin();i!=left->end();++i) {
2N/A Node *v=*(i);
2N/A v->addRightNeighbour(this);
2N/A }
2N/A for(NodeSet::iterator i=right->begin();i!=right->end();++i) {
2N/A Node *v=*(i);
2N/A v->addLeftNeighbour(this);
2N/A }
2N/A }
2N/A};
2N/Abool CmpNodePos::operator() (const Node* u, const Node* v) const {
2N/A if (u->pos < v->pos) {
2N/A return true;
2N/A }
2N/A if (v->pos < u->pos) {
2N/A return false;
2N/A }
2N/A if (isNaN(u->pos) != isNaN(v->pos)) {
2N/A return isNaN(u->pos);
2N/A }
2N/A return u < v;
2N/A
2N/A /* I don't know how important it is to handle NaN correctly
2N/A * (e.g. we probably handle it badly in other code anyway, and
2N/A * in any case the best we can hope for is to reduce the
2N/A * badness of other nodes).
2N/A *
2N/A * Nevertheless, we try to do the right thing here and in
2N/A * event comparison. The issue is that (on platforms with
2N/A * ieee floating point comparison) NaN compares neither less
2N/A * than nor greater than any other number, yet sort wants a
2N/A * well-defined ordering. In particular, we want to ensure
2N/A * transitivity of equivalence, which normally wouldn't be
2N/A * guaranteed if the "middle" item in the transitivity
2N/A * involves a NaN. (NaN is neither less than nor greater than
2N/A * other numbers, so tends to be considered as equal to all
2N/A * other numbers: even unequal numbers.)
2N/A */
2N/A}
2N/A
2N/ANodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) {
2N/A NodeSet *leftv = new NodeSet;
2N/A NodeSet::iterator i=scanline.find(v);
2N/A while(i--!=scanline.begin()) {
2N/A Node *u=*(i);
2N/A if(u->r->overlapX(v->r)<=0) {
2N/A leftv->insert(u);
2N/A return leftv;
2N/A }
2N/A if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
2N/A leftv->insert(u);
2N/A }
2N/A }
2N/A return leftv;
2N/A}
2N/ANodeSet* getRightNeighbours(NodeSet &scanline,Node *v) {
2N/A NodeSet *rightv = new NodeSet;
2N/A NodeSet::iterator i=scanline.find(v);
2N/A for(++i;i!=scanline.end(); ++i) {
2N/A Node *u=*(i);
2N/A if(u->r->overlapX(v->r)<=0) {
2N/A rightv->insert(u);
2N/A return rightv;
2N/A }
2N/A if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
2N/A rightv->insert(u);
2N/A }
2N/A }
2N/A return rightv;
2N/A}
2N/A
2N/Atypedef enum {Open, Close} EventType;
2N/Astruct Event {
2N/A EventType type;
2N/A Node *v;
2N/A double pos;
2N/A Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {};
2N/A};
2N/AEvent **events;
2N/Aint compare_events(const void *a, const void *b) {
2N/A Event *ea=*(Event**)a;
2N/A Event *eb=*(Event**)b;
2N/A if(ea->v->r==eb->v->r) {
2N/A // when comparing opening and closing from the same rect
2N/A // open must come first
2N/A if(ea->type==Open) return -1;
2N/A return 1;
2N/A } else if(ea->pos > eb->pos) {
2N/A return 1;
2N/A } else if(ea->pos < eb->pos) {
2N/A return -1;
2N/A } else if(isNaN(ea->pos) != isNaN(ea->pos)) {
2N/A /* See comment in CmpNodePos. */
2N/A return ( isNaN(ea->pos)
2N/A ? -1
2N/A : 1 );
2N/A }
2N/A return 0;
2N/A}
2N/A
2N/A/**
2N/A * Prepares constraints in order to apply VPSC horizontally. Assumes variables have already been created.
2N/A * useNeighbourLists determines whether or not a heuristic is used to deciding whether to resolve
2N/A * all overlap in the x pass, or leave some overlaps for the y pass.
2N/A */
2N/Aint generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists) {
2N/A events=new Event*[2*n];
2N/A int i,m,ctr=0;
2N/A for(i=0;i<n;i++) {
2N/A vars[i]->desiredPosition=rs[i]->getCentreX();
2N/A Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX());
2N/A events[ctr++]=new Event(Open,v,rs[i]->getMinY());
2N/A events[ctr++]=new Event(Close,v,rs[i]->getMaxY());
2N/A }
2N/A qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
2N/A
2N/A NodeSet scanline;
2N/A vector<Constraint*> constraints;
2N/A for(i=0;i<2*n;i++) {
2N/A Event *e=events[i];
2N/A Node *v=e->v;
2N/A if(e->type==Open) {
2N/A scanline.insert(v);
2N/A if(useNeighbourLists) {
2N/A v->setNeighbours(
2N/A getLeftNeighbours(scanline,v),
2N/A getRightNeighbours(scanline,v)
2N/A );
2N/A } else {
2N/A NodeSet::iterator it=scanline.find(v);
2N/A if(it--!=scanline.begin()) {
2N/A Node *u=*it;
2N/A v->firstAbove=u;
2N/A u->firstBelow=v;
2N/A }
2N/A it=scanline.find(v);
2N/A if(++it!=scanline.end()) {
2N/A Node *u=*it;
2N/A v->firstBelow=u;
2N/A u->firstAbove=v;
2N/A }
2N/A }
2N/A } else {
2N/A // Close event
2N/A int r;
2N/A if(useNeighbourLists) {
2N/A for(NodeSet::iterator i=v->leftNeighbours->begin();
2N/A i!=v->leftNeighbours->end();i++
2N/A ) {
2N/A Node *u=*i;
2N/A double sep = (v->r->width()+u->r->width())/2.0;
2N/A constraints.push_back(new Constraint(u->v,v->v,sep));
2N/A r=u->rightNeighbours->erase(v);
2N/A }
2N/A
2N/A for(NodeSet::iterator i=v->rightNeighbours->begin();
2N/A i!=v->rightNeighbours->end();i++
2N/A ) {
2N/A Node *u=*i;
2N/A double sep = (v->r->width()+u->r->width())/2.0;
2N/A constraints.push_back(new Constraint(v->v,u->v,sep));
2N/A r=u->leftNeighbours->erase(v);
2N/A }
2N/A } else {
2N/A Node *l=v->firstAbove, *r=v->firstBelow;
2N/A if(l!=NULL) {
2N/A double sep = (v->r->width()+l->r->width())/2.0;
2N/A constraints.push_back(new Constraint(l->v,v->v,sep));
2N/A l->firstBelow=v->firstBelow;
2N/A }
2N/A if(r!=NULL) {
2N/A double sep = (v->r->width()+r->r->width())/2.0;
2N/A constraints.push_back(new Constraint(v->v,r->v,sep));
2N/A r->firstAbove=v->firstAbove;
2N/A }
2N/A }
2N/A r=scanline.erase(v);
2N/A delete v;
2N/A }
2N/A delete e;
2N/A }
2N/A delete [] events;
2N/A cs=new Constraint*[m=constraints.size()];
2N/A for(i=0;i<m;i++) cs[i]=constraints[i];
2N/A return m;
2N/A}
2N/A
2N/A/**
2N/A * Prepares constraints in order to apply VPSC vertically to remove ALL overlap.
2N/A */
2N/Aint generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs) {
2N/A events=new Event*[2*n];
2N/A int ctr=0,i,m;
2N/A for(i=0;i<n;i++) {
2N/A vars[i]->desiredPosition=rs[i]->getCentreY();
2N/A Node *v = new Node(vars[i],rs[i],rs[i]->getCentreY());
2N/A events[ctr++]=new Event(Open,v,rs[i]->getMinX());
2N/A events[ctr++]=new Event(Close,v,rs[i]->getMaxX());
2N/A }
2N/A qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
2N/A NodeSet scanline;
2N/A vector<Constraint*> constraints;
2N/A for(i=0;i<2*n;i++) {
2N/A Event *e=events[i];
2N/A Node *v=e->v;
2N/A if(e->type==Open) {
2N/A scanline.insert(v);
2N/A NodeSet::iterator i=scanline.find(v);
2N/A if(i--!=scanline.begin()) {
2N/A Node *u=*i;
2N/A v->firstAbove=u;
2N/A u->firstBelow=v;
2N/A }
2N/A i=scanline.find(v);
2N/A if(++i!=scanline.end()) {
2N/A Node *u=*i;
2N/A v->firstBelow=u;
2N/A u->firstAbove=v;
2N/A }
2N/A } else {
2N/A // Close event
2N/A Node *l=v->firstAbove, *r=v->firstBelow;
2N/A if(l!=NULL) {
2N/A double sep = (v->r->height()+l->r->height())/2.0;
2N/A constraints.push_back(new Constraint(l->v,v->v,sep));
2N/A l->firstBelow=v->firstBelow;
2N/A }
2N/A if(r!=NULL) {
2N/A double sep = (v->r->height()+r->r->height())/2.0;
2N/A constraints.push_back(new Constraint(v->v,r->v,sep));
2N/A r->firstAbove=v->firstAbove;
2N/A }
2N/A scanline.erase(v);
2N/A delete v;
2N/A }
2N/A delete e;
2N/A }
2N/A delete [] events;
2N/A cs=new Constraint*[m=constraints.size()];
2N/A for(i=0;i<m;i++) cs[i]=constraints[i];
2N/A return m;
2N/A}
2N/A