diff options
Diffstat (limited to 'src/removeoverlap')
26 files changed, 2615 insertions, 0 deletions
diff --git a/src/removeoverlap/.cvsignore b/src/removeoverlap/.cvsignore new file mode 100644 index 000000000..e8014d011 --- /dev/null +++ b/src/removeoverlap/.cvsignore @@ -0,0 +1,5 @@ +Makefile +Makefile.in +.deps +makefile +.dirstamp diff --git a/src/removeoverlap/Makefile_insert b/src/removeoverlap/Makefile_insert new file mode 100644 index 000000000..e28304431 --- /dev/null +++ b/src/removeoverlap/Makefile_insert @@ -0,0 +1,31 @@ +## Makefile.am fragment sourced by src/Makefile.am. + +removeoverlap/all: removeoverlap/libremoveoverlap.a + +removeoverlap/clean: + rm -f removeoverlap/libremoveoverlap.a $(removeoverlap_libremoveoverlap_a_OBJECTS) + +removeoverlap_libremoveoverlap_a_SOURCES = \ + removeoverlap/block.cpp \ + removeoverlap/block.h \ + removeoverlap/blocks.cpp \ + removeoverlap/blocks.h \ + removeoverlap/constraint.cpp \ + removeoverlap/constraint.h \ + removeoverlap/generate-constraints.cpp \ + removeoverlap/generate-constraints.h \ + removeoverlap/remove_rectangle_overlap.cpp \ + removeoverlap/remove_rectangle_overlap.h \ + removeoverlap/removeoverlap.cpp \ + removeoverlap/removeoverlap.h \ + removeoverlap/solve_VPSC.cpp \ + removeoverlap/solve_VPSC.h \ + removeoverlap/variable.cpp \ + removeoverlap/variable.h \ + removeoverlap/pairingheap/dsexceptions.h \ + removeoverlap/pairingheap/PairingHeap.cpp \ + removeoverlap/pairingheap/PairingHeap.h + +removeoverlap_remove_rectangle_overlap_test_SOURCES = \ + removeoverlap/remove_rectangle_overlap-test.cpp +removeoverlap_remove_rectangle_overlap_test_LDADD = removeoverlap/libremoveoverlap.a -lglib-2.0 diff --git a/src/removeoverlap/block.cpp b/src/removeoverlap/block.cpp new file mode 100644 index 000000000..799fa5d8e --- /dev/null +++ b/src/removeoverlap/block.cpp @@ -0,0 +1,279 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + + +#include "constraint.h" +#include "block.h" +#include "blocks.h" +#include "pairingheap/PairingHeap.h" +#ifdef RECTANGLE_OVERLAP_LOGGING +using std::ios; +using std::ofstream; +using std::endl; +#endif +using std::vector; + +void Block::addVariable(Variable *v) { + v->block=this; + vars->push_back(v); + weight+=v->weight; + wposn += v->weight * (v->desiredPosition - v->offset); + posn=wposn/weight; +} +Block::Block(Variable *v) { + timeStamp=0; + posn=weight=wposn=0; + in=NULL; + out=NULL; + deleted=false; + vars=new vector<Variable*>; + if(v!=NULL) { + v->offset=0; + addVariable(v); + } +} + +double Block::desiredWeightedPosition() { + double wp = 0; + for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) { + wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight; + } + return wp; +} +Block::~Block(void) +{ + delete vars; + delete in; + delete out; +} +void Block::setUpInConstraints() { + setUpConstraintHeap(in,true); +} +void Block::setUpOutConstraints() { + setUpConstraintHeap(out,false); +} +void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) { + delete h; + h = new PairingHeap<Constraint*>(&compareConstraints); + for (vector<Variable*>::iterator i=vars->begin();i!=vars->end();i++) { + Variable *v=*i; + vector<Constraint*> *cs=in?&(v->in):&(v->out); + for (vector<Constraint*>::iterator j=cs->begin();j!=cs->end();j++) { + Constraint *c=*j; + c->timeStamp=blockTimeCtr; + if (c->left->block != this && in || c->right->block != this && !in) { + h->insert(c); + } + } + } +} +/** + * Merges b into this block across c. Can be either a + * right merge or a left merge + * @param b block to merge into this + * @param c constraint being merged + * @param distance separation required to satisfy c + */ +void Block::merge(Block *b, Constraint *c, double dist) { + c->active=true; + wposn+=b->wposn-dist*b->weight; + weight+=b->weight; + posn=wposn/weight; + for(vector<Variable*>::iterator i=b->vars->begin();i!=b->vars->end();i++) { + Variable *v=*i; + v->block=this; + v->offset+=dist; + vars->push_back(v); + } +} + +void Block::mergeIn(Block *b) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging constraint heaps... "<<endl; +#endif + // We check the top of the heaps to remove possible internal constraints + findMinInConstraint(); + b->findMinInConstraint(); + in->merge(b->in); +} +void Block::mergeOut(Block *b) { + findMinOutConstraint(); + b->findMinOutConstraint(); + out->merge(b->out); +} +Constraint *Block::findMinInConstraint() { + Constraint *v = NULL; + vector<Constraint*> outOfDate; + while (!in->isEmpty()) { + v = in->findMin(); + Block *lb=v->left->block; + Block *rb=v->right->block; + // rb may not be this if called between merge and mergeIn +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" checking constraint ... "<<*v; + f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl; +#endif + if(lb == rb) { + // constraint has been merged into the same block + in->deleteMin(); +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" ... skipping internal constraint"<<endl; +#endif + } else if(lb->timeStamp > rb->timeStamp + && v->timeStamp < lb->timeStamp + || v->timeStamp < rb->timeStamp) { + // block at other end of constraint has been moved since this + in->deleteMin(); + outOfDate.push_back(v); +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" reinserting out of date constraint"<<endl; +#endif + } else { + break; + } + } + for(vector<Constraint*>::iterator i=outOfDate.begin();i!=outOfDate.end();i++) { + v=*i; + v->timeStamp=blockTimeCtr; + in->insert(v); + } + if(in->isEmpty()) { + v=NULL; + } else { + v=in->findMin(); + } + return v; +} +Constraint *Block::findMinOutConstraint() { + if(out->isEmpty()) return NULL; + Constraint *v = out->findMin(); + while (v->left->block == v->right->block) { + out->deleteMin(); + if(out->isEmpty()) return NULL; + v = out->findMin(); + } + return v; +} +void Block::deleteMinInConstraint() { + in->deleteMin(); +} +void Block::deleteMinOutConstraint() { + out->deleteMin(); +} +inline bool Block::canFollowLeft(Constraint *c, Variable *last) { + return c->left->block==this && c->active && last!=c->left; +} +inline bool Block::canFollowRight(Constraint *c, Variable *last) { + return c->right->block==this && c->active && last!=c->right; +} + +// computes the derivative of v and the lagrange multipliers +// of v's out constraints (as the recursive sum of those below. +// Does not backtrack over u. +// also records the constraint with minimum lagrange multiplier +// in min_lm +double Block::compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm) { + double dfdv=v->weight*(v->position() - v->desiredPosition); + for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + dfdv+=c->lm=compute_dfdv(c->right,v,min_lm); + if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c; + } + } + for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm); + if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c; + } + } + return dfdv; +} + +// resets LMs for all active constraints to 0 by +// traversing active constraint tree starting from v, +// not back tracking over u +void Block::reset_active_lm(Variable *v, Variable *u) { + for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + c->lm=0; + reset_active_lm(c->right,v); + } + } + for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + c->lm=0; + reset_active_lm(c->left,v); + } + } +} +/** + * finds the constraint with the minimum lagrange multiplier, that is, the constraint + * that most wants to split + */ +Constraint *Block::findMinLM() { + Constraint *min_lm=NULL; + reset_active_lm(vars->front(),NULL); + compute_dfdv(vars->front(),NULL,min_lm); + return min_lm; +} + +// populates block b by traversing the active constraint tree adding variables as they're +// visited. Starts from variable v and does not backtrack over variable u. +void Block::populateSplitBlock(Block *b, Variable *v, Variable *u) { + b->addVariable(v); + for (vector<Constraint*>::iterator c=v->in.begin();c!=v->in.end();c++) { + if (canFollowLeft(*c,u)) + populateSplitBlock(b, (*c)->left, v); + } + for (vector<Constraint*>::iterator c=v->out.begin();c!=v->out.end();c++) { + if (canFollowRight(*c,u)) + populateSplitBlock(b, (*c)->right, v); + } +} +/** + * Creates two new blocks, l and r, and splits this block across constraint c, + * placing the left subtree of constraints (and associated variables) into l + * and the right into r + */ +void Block::split(Block *&l, Block *&r, Constraint *c) { + c->active=false; + l=new Block(); + populateSplitBlock(l,c->left,c->right); + r=new Block(); + populateSplitBlock(r,c->right,c->left); +} + +/** + * Computes the cost (squared euclidean distance from desired positions) of the + * current positions for variables in this block + */ +double Block::cost() { + double c = 0; + for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) { + double diff = (*v)->position() - (*v)->desiredPosition; + c += (*v)->weight * diff * diff; + } + return c; +} +ostream& operator <<(ostream &os, const Block &b) +{ + os<<"Block:"; + for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();v++) { + os<<" "<<**v; + } + return os; +} diff --git a/src/removeoverlap/block.h b/src/removeoverlap/block.h new file mode 100644 index 000000000..7905309bb --- /dev/null +++ b/src/removeoverlap/block.h @@ -0,0 +1,59 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#ifndef SEEN_REMOVEOVERLAP_BLOCK_H +#define SEEN_REMOVEOVERLAP_BLOCK_H + +#include <vector> +#include <iostream> +class Variable; +class Constraint; +template <class T> class PairingHeap; +class StupidPriorityQueue; + +class Block +{ + friend std::ostream& operator <<(std::ostream &os,const Block &b); +public: + std::vector<Variable*> *vars; + double posn; + double weight; + double wposn; + Block(Variable *v=NULL); + ~Block(void); + Constraint *findMinLM(); + Constraint *findMinInConstraint(); + Constraint *findMinOutConstraint(); + void deleteMinInConstraint(); + void deleteMinOutConstraint(); + double desiredWeightedPosition(); + void merge(Block *b, Constraint *c, double dist); + void mergeIn(Block *b); + void mergeOut(Block *b); + void split(Block *&l, Block *&r, Constraint *c); + void setUpInConstraints(); + void setUpOutConstraints(); + double cost(); + bool deleted; + long timeStamp; + PairingHeap<Constraint*> *in; + PairingHeap<Constraint*> *out; +private: + void reset_active_lm(Variable *v, Variable *u); + double compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm); + bool canFollowLeft(Constraint *c, Variable *last); + bool canFollowRight(Constraint *c, Variable *last); + void populateSplitBlock(Block *b, Variable *v, Variable *u); + void addVariable(Variable *v); + void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in); +}; + +#endif // SEEN_REMOVEOVERLAP_BLOCK_H diff --git a/src/removeoverlap/blocks.cpp b/src/removeoverlap/blocks.cpp new file mode 100644 index 000000000..45c479187 --- /dev/null +++ b/src/removeoverlap/blocks.cpp @@ -0,0 +1,190 @@ +/** + * \brief A block structure defined over the variables + * + * A block structure defined over the variables such that each block contains + * 1 or more variables, with the invariant that all constraints inside a block + * are satisfied by keeping the variables fixed relative to one another + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#include "blocks.h" +#include "block.h" +#include "constraint.h" +#ifdef RECTANGLE_OVERLAP_LOGGING +using std::ios; +using std::ofstream; +using std::endl; +#endif +using std::set; +using std::vector; +using std::iterator; +using std::list; +using std::copy; + +long blockTimeCtr; + +Blocks::Blocks(Variable *vs[], const int n) : vs(vs),nvs(n) { + blockTimeCtr=0; + for(int i=0;i<nvs;i++) { + insert(new Block(vs[i])); + } +} +Blocks::~Blocks(void) +{ + for(set<Block*>::iterator i=begin();i!=end();i++) { + delete *i; + } + clear(); +} + +/** + * returns a list of variables with total ordering determined by the constraint + * DAG + */ +list<Variable*> *Blocks::totalOrder() { + list<Variable*> *order = new list<Variable*>; + for(int i=0;i<nvs;i++) { + vs[i]->visited=false; + } + for(int i=0;i<nvs;i++) { + if(vs[i]->in.size()==0) { + dfsVisit(vs[i],order); + } + } + return order; +} +// Recursive depth first search giving total order by pushing nodes in the DAG +// onto the front of the list when we finish searching them +void Blocks::dfsVisit(Variable *v, list<Variable*> *order) { + v->visited=true; + vector<Constraint*>::iterator it=v->out.begin(); + for(;it!=v->out.end();it++) { + Constraint *c=*it; + if(!c->right->visited) { + dfsVisit(c->right, order); + } + } + order->push_front(v); +} +/** + * Processes incoming constraints, most violated to least, merging with the + * neighbouring (left) block until no more violated constraints are found + */ +void Blocks::mergeLeft(Block *r) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"mergeLeft called on "<<*r<<endl; +#endif + r->timeStamp=++blockTimeCtr; + r->setUpInConstraints(); + Constraint *c=r->findMinInConstraint(); + while (c != NULL && c->slack()<0) { +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<"mergeLeft on constraint: "<<*c<<endl; +#endif + r->deleteMinInConstraint(); + Block *l = c->left->block; + if (l->in==NULL) l->setUpInConstraints(); + double dist = c->right->offset - c->left->offset - c->gap; + if (r->vars->size() < l->vars->size()) { + dist=-dist; + std::swap(l, r); + } + r->merge(l, c, dist); + r->mergeIn(l); + r->timeStamp=++blockTimeCtr; + removeBlock(l); + c=r->findMinInConstraint(); + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<"merged "<<*r<<endl; +#endif +} +/** + * Symmetrical to mergeLeft + */ +void Blocks::mergeRight(Block *l) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"mergeRight called on "<<*l<<endl; +#endif + l->setUpOutConstraints(); + Constraint *c = l->findMinOutConstraint(); + while (c != NULL && c->slack()<0) { +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<"mergeRight on constraint: "<<*c<<endl; +#endif + l->deleteMinOutConstraint(); + Block *r = c->right->block; + r->setUpOutConstraints(); + double dist = c->left->offset + c->gap - c->right->offset; + if (l->vars->size() > r->vars->size()) { + dist=-dist; + std::swap(l, r); + } + l->merge(r, c, dist); + l->mergeOut(r); + removeBlock(r); + c=l->findMinOutConstraint(); + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<"merged "<<*l<<endl; +#endif +} +void Blocks::removeBlock(Block *doomed) { + doomed->deleted=true; + //erase(doomed); +} +void Blocks::cleanup() { + vector<Block*> bcopy(size()); + copy(begin(),end(),bcopy.begin()); + for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();i++) { + Block *b=*i; + if(b->deleted) { + erase(b); + delete b; + } + } +} +/** + * Splits block b across constraint c into two new blocks, l and r (c's left + * and right sides respectively) + */ +void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) { + b->split(l,r,c); +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Split left: "<<*l<<endl; + f<<"Split right: "<<*r<<endl; +#endif + r->posn = b->posn; + r->wposn = r->posn * r->weight; + mergeLeft(l); + // r may have been merged! + r = c->right->block; + r->wposn = r->desiredWeightedPosition(); + r->posn = r->wposn / r->weight; + mergeRight(r); + removeBlock(b); + + insert(l); + insert(r); +} +/** + * returns the cost total squared distance of variables from their desired + * positions + */ +double Blocks::cost() { + double c = 0; + for(set<Block*>::iterator i=begin();i!=end();i++) { + c += (*i)->cost(); + } + return c; +} + diff --git a/src/removeoverlap/blocks.h b/src/removeoverlap/blocks.h new file mode 100644 index 000000000..437af6310 --- /dev/null +++ b/src/removeoverlap/blocks.h @@ -0,0 +1,49 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#ifndef SEEN_REMOVEOVERLAP_BLOCKS_H +#define SEEN_REMOVEOVERLAP_BLOCKS_H + +#ifdef RECTANGLE_OVERLAP_LOGGING +#define LOGFILE "cRectangleOverlap.log" +#endif + +#include <set> +#include <list> + +class Block; +class Variable; +class Constraint; +/** + * A block structure defined over the variables such that each block contains + * 1 or more variables, with the invariant that all constraints inside a block + * are satisfied by keeping the variables fixed relative to one another + */ +class Blocks : public std::set<Block*> +{ +public: + Blocks(Variable *vs[], const int n); + ~Blocks(void); + void mergeLeft(Block *r); + void mergeRight(Block *l); + void split(Block *b, Block *&l, Block *&r, Constraint *c); + std::list<Variable*> *totalOrder(); + void cleanup(); + double cost(); +private: + void dfsVisit(Variable *v, std::list<Variable*> *order); + void removeBlock(Block *doomed); + Variable **vs; + int nvs; +}; + +extern long blockTimeCtr; +#endif // SEEN_REMOVEOVERLAP_BLOCKS_H diff --git a/src/removeoverlap/constraint.cpp b/src/removeoverlap/constraint.cpp new file mode 100644 index 000000000..78c5f03ad --- /dev/null +++ b/src/removeoverlap/constraint.cpp @@ -0,0 +1,29 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#include "constraint.h" + +Constraint::Constraint(Variable *left, Variable *right, double gap) +{ + this->left=left; + left->out.push_back(this); + this->right=right; + right->in.push_back(this); + this->gap=gap; + active=false; + visited=false; + timeStamp=0; +} +std::ostream& operator <<(std::ostream &os, const Constraint &c) +{ + os<<*c.left<<"+"<<c.gap<<"<="<<*c.right<<"("<<c.slack()<<")"; + return os; +} diff --git a/src/removeoverlap/constraint.h b/src/removeoverlap/constraint.h new file mode 100644 index 000000000..26afcefdd --- /dev/null +++ b/src/removeoverlap/constraint.h @@ -0,0 +1,52 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#ifndef SEEN_REMOVEOVERLAP_CONSTRAINT_H +#define SEEN_REMOVEOVERLAP_CONSTRAINT_H + +#include <iostream> +#include "variable.h" + +class Constraint +{ + friend std::ostream& operator <<(std::ostream &os,const Constraint &c); +public: + Variable *left; + Variable *right; + double gap; + double lm; + Constraint(Variable *left, Variable *right, double gap); + ~Constraint(void){}; + inline double Constraint::slack() const { return right->position() - gap - left->position(); } + //inline bool operator<(Constraint const &o) const { return slack() < o.slack(); } + long timeStamp; + bool active; + bool visited; +}; +#include <float.h> +static inline bool compareConstraints(Constraint *&l, Constraint *&r) { + double sl = l->slack(); + double sr = r->slack(); + if(l->left->block==l->right->block) sl=DBL_MIN; + if(r->left->block==r->right->block) sr=DBL_MIN; + if(sl==sr) { + // arbitrary choice based on id + if(l->left->id==r->left->id) { + if(l->right->id<r->right->id) return true; + return false; + } + if(l->left->id<r->left->id) return true; + return false; + } + return sl < sr; +} + +#endif // SEEN_REMOVEOVERLAP_CONSTRAINT_H diff --git a/src/removeoverlap/generate-constraints.cpp b/src/removeoverlap/generate-constraints.cpp new file mode 100644 index 000000000..3238a0ca9 --- /dev/null +++ b/src/removeoverlap/generate-constraints.cpp @@ -0,0 +1,302 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#include <set> +#include <cassert> +#include "generate-constraints.h" +#include "constraint.h" + +#include "isnan.h" /* Include last */ + +using std::set; +using std::vector; + +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; + } + ~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->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 ); + } else if(ea->v->r==ea->v->r) { + // when comparing opening and closing from the same rect + // open must come first + if(ea->type==Open) return -1; + return 1; + } + return 0; +} + +/** + * Prepares variables and constraints in order to apply VPSC horizontally. + * 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. + */ +int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs, bool useNeighbourLists) { + events=new Event*[2*n]; + int i,m,ctr=0; + vector<Constraint*> constraints; + vars=new Variable*[n]; + for(i=0;i<n;i++) { + vars[i]=new Variable(i,rs[i]->getCentreX(),weights[i]); + 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; + 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 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 + 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 variables and constraints in order to apply VPSC vertically to remove ALL overlap. + */ +int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs) { + events=new Event*[2*n]; + int ctr=0,i,m; + vector<Constraint*> constraints; + vars=new Variable*[n]; + for(i=0;i<n;i++) { + vars[i]=new Variable(i,rs[i]->getCentreY(),weights[i]); + 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; + 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; +} diff --git a/src/removeoverlap/generate-constraints.h b/src/removeoverlap/generate-constraints.h new file mode 100644 index 000000000..ad9ccb1f9 --- /dev/null +++ b/src/removeoverlap/generate-constraints.h @@ -0,0 +1,78 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#ifndef SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H +#define SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H +#include <iostream> + +class Rectangle { + friend std::ostream& operator <<(std::ostream &os, const Rectangle &r); +public: + static double xBorder,yBorder; + Rectangle(double x, double X, double y, double Y); + double getMaxX() const { return maxX+xBorder; } + double getMaxY() const { return maxY+yBorder; } + double getMinX() const { return minX; } + double getMinY() const { return minY; } + double getMinD(unsigned const d) const { + return ( d == 0 ? getMinX() : getMinY() ); + } + double getMaxD(unsigned const d) const { + return ( d == 0 ? getMaxX() : getMaxY() ); + } + double getCentreX() const { return minX+width()/2.0; } + double getCentreY() const { return minY+height()/2.0; } + double width() const { return getMaxX()-minX; } + double height() const { return getMaxY()-minY; } + static void setXBorder(double x) {xBorder=x;} + static void setYBorder(double y) {yBorder=y;} + void moveCentreX(double x) { + moveMinX(x-width()/2.0); + } + void moveCentreY(double y) { + moveMinY(y-height()/2.0); + } + void moveMinX(double x) { + maxX=x+width()-xBorder; + minX=x; + } + void moveMinY(double y) { + maxY=y+height()-yBorder; + minY=y; + } + inline double overlapX(Rectangle *r) const { + if (getCentreX() <= r->getCentreX() && r->minX < getMaxX()) + return getMaxX() - r->minX; + if (r->getCentreX() <= getCentreX() && minX < r->getMaxX()) + return r->getMaxX() - minX; + return 0; + } + inline double overlapY(Rectangle *r) const { + if (getCentreY() <= r->getCentreY() && r->minY < getMaxY()) + return getMaxY() - r->minY; + if (r->getCentreY() <= getCentreY() && minY < r->getMaxY()) + return r->getMaxY() - minY; + return 0; + } +private: + double minX,maxX,minY,maxY; +}; + + +class Variable; +class Constraint; + +// returns number of constraints generated +int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vs, Constraint **&cs,bool useNeighbourLists); + +int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vs, Constraint **&cs); + +#endif // SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H diff --git a/src/removeoverlap/makefile.in b/src/removeoverlap/makefile.in new file mode 100644 index 000000000..480b25a90 --- /dev/null +++ b/src/removeoverlap/makefile.in @@ -0,0 +1,17 @@ +# Convenience stub makefile to call the real Makefile. + +@SET_MAKE@ + +# Explicit so that it's the default rule. +all: + cd .. && $(MAKE) removeoverlap/all + +clean %.a %.o: + cd .. && $(MAKE) removeoverlap/$@ + +.PHONY: all clean + +OBJEXT = @OBJEXT@ + +.SUFFIXES: +.SUFFIXES: .a .$(OBJEXT) diff --git a/src/removeoverlap/pairingheap/.cvsignore b/src/removeoverlap/pairingheap/.cvsignore new file mode 100644 index 000000000..e8014d011 --- /dev/null +++ b/src/removeoverlap/pairingheap/.cvsignore @@ -0,0 +1,5 @@ +Makefile +Makefile.in +.deps +makefile +.dirstamp diff --git a/src/removeoverlap/pairingheap/PairingHeap.cpp b/src/removeoverlap/pairingheap/PairingHeap.cpp new file mode 100644 index 000000000..9c67f44fa --- /dev/null +++ b/src/removeoverlap/pairingheap/PairingHeap.cpp @@ -0,0 +1,309 @@ +/** + * \brief Pairing heap datastructure implementation + * + * Based on example code in "Data structures and Algorithm Analysis in C++" + * by Mark Allen Weiss, used and released under the GPL by permission + * of the author. + * + * No promises about correctness. Use at your own risk! + * + * Authors: + * Mark Allen Weiss + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#include <vector> + +#include "dsexceptions.h" +#include "PairingHeap.h" + +#ifndef PAIRING_HEAP_CPP +#define PAIRING_HEAP_CPP +using namespace std; +/** +* Construct the pairing heap. +*/ +template <class T> +PairingHeap<T>::PairingHeap( bool (*lessThan)(T &lhs, T &rhs) ) +{ + root = NULL; + counter=0; + this->lessThan=lessThan; +} + + +/** +* Copy constructor +*/ +template <class T> +PairingHeap<T>::PairingHeap( const PairingHeap<T> & rhs ) +{ + root = NULL; + counter=rhs->size(); + *this = rhs; +} + +/** +* Destroy the leftist heap. +*/ +template <class T> +PairingHeap<T>::~PairingHeap( ) +{ + makeEmpty( ); +} + +/** +* Insert item x into the priority queue, maintaining heap order. +* Return a pointer to the node containing the new item. +*/ +template <class T> +PairNode<T> * +PairingHeap<T>::insert( const T & x ) +{ + PairNode<T> *newNode = new PairNode<T>( x ); + + if( root == NULL ) + root = newNode; + else + compareAndLink( root, newNode ); + counter++; + return newNode; +} +template <class T> +int PairingHeap<T>::size() { + return counter; +} +/** +* Find the smallest item in the priority queue. +* Return the smallest item, or throw Underflow if empty. +*/ +template <class T> +const T & PairingHeap<T>::findMin( ) const +{ + if( isEmpty( ) ) + throw Underflow( ); + return root->element; +} +/** + * Remove the smallest item from the priority queue. + * Throws Underflow if empty. + */ +template <class T> +void PairingHeap<T>::deleteMin( ) +{ + if( isEmpty( ) ) + throw Underflow( ); + + PairNode<T> *oldRoot = root; + + if( root->leftChild == NULL ) + root = NULL; + else + root = combineSiblings( root->leftChild ); + counter--; + delete oldRoot; +} + +/** +* Test if the priority queue is logically empty. +* Returns true if empty, false otherwise. +*/ +template <class T> +bool PairingHeap<T>::isEmpty( ) const +{ + return root == NULL; +} + +/** +* Test if the priority queue is logically full. +* Returns false in this implementation. +*/ +template <class T> +bool PairingHeap<T>::isFull( ) const +{ + return false; +} + +/** +* Make the priority queue logically empty. +*/ +template <class T> +void PairingHeap<T>::makeEmpty( ) +{ + reclaimMemory( root ); + root = NULL; +} + +/** +* Deep copy. +*/ +template <class T> +const PairingHeap<T> & +PairingHeap<T>::operator=( const PairingHeap<T> & rhs ) +{ + if( this != &rhs ) + { + makeEmpty( ); + root = clone( rhs.root ); + } + + return *this; +} + +/** +* Internal method to make the tree empty. +* WARNING: This is prone to running out of stack space. +*/ +template <class T> +void PairingHeap<T>::reclaimMemory( PairNode<T> * t ) const +{ + if( t != NULL ) + { + reclaimMemory( t->leftChild ); + reclaimMemory( t->nextSibling ); + delete t; + } +} + +/** +* Change the value of the item stored in the pairing heap. +* Does nothing if newVal is larger than currently stored value. +* p points to a node returned by insert. +* newVal is the new value, which must be smaller +* than the currently stored value. +*/ +template <class T> +void PairingHeap<T>::decreaseKey( PairNode<T> *p, + const T & newVal ) +{ + if( p->element < newVal ) + return; // newVal cannot be bigger + p->element = newVal; + if( p != root ) + { + if( p->nextSibling != NULL ) + p->nextSibling->prev = p->prev; + if( p->prev->leftChild == p ) + p->prev->leftChild = p->nextSibling; + else + p->prev->nextSibling = p->nextSibling; + + p->nextSibling = NULL; + compareAndLink( root, p ); + } +} + +/** +* Internal method that is the basic operation to maintain order. +* Links first and second together to satisfy heap order. +* first is root of tree 1, which may not be NULL. +* first->nextSibling MUST be NULL on entry. +* second is root of tree 2, which may be NULL. +* first becomes the result of the tree merge. +*/ +template <class T> +void PairingHeap<T>:: +compareAndLink( PairNode<T> * & first, + PairNode<T> *second ) const +{ + if( second == NULL ) + return; + if( lessThan(second->element,first->element) ) + { + // Attach first as leftmost child of second + second->prev = first->prev; + first->prev = second; + first->nextSibling = second->leftChild; + if( first->nextSibling != NULL ) + first->nextSibling->prev = first; + second->leftChild = first; + first = second; + } + else + { + // Attach second as leftmost child of first + second->prev = first; + first->nextSibling = second->nextSibling; + if( first->nextSibling != NULL ) + first->nextSibling->prev = first; + second->nextSibling = first->leftChild; + if( second->nextSibling != NULL ) + second->nextSibling->prev = second; + first->leftChild = second; + } +} + +/** +* Internal method that implements two-pass merging. +* firstSibling the root of the conglomerate; +* assumed not NULL. +*/ +template <class T> +PairNode<T> * +PairingHeap<T>::combineSiblings( PairNode<T> *firstSibling ) const +{ + if( firstSibling->nextSibling == NULL ) + return firstSibling; + + // Allocate the array + static vector<PairNode<T> *> treeArray( 5 ); + + // Store the subtrees in an array + int numSiblings = 0; + for( ; firstSibling != NULL; numSiblings++ ) + { + if( numSiblings == (int)treeArray.size( ) ) + treeArray.resize( numSiblings * 2 ); + treeArray[ numSiblings ] = firstSibling; + firstSibling->prev->nextSibling = NULL; // break links + firstSibling = firstSibling->nextSibling; + } + if( numSiblings == (int)treeArray.size( ) ) + treeArray.resize( numSiblings + 1 ); + treeArray[ numSiblings ] = NULL; + + // Combine subtrees two at a time, going left to right + int i = 0; + for( ; i + 1 < numSiblings; i += 2 ) + compareAndLink( treeArray[ i ], treeArray[ i + 1 ] ); + + int j = i - 2; + + // j has the result of last compareAndLink. + // If an odd number of trees, get the last one. + if( j == numSiblings - 3 ) + compareAndLink( treeArray[ j ], treeArray[ j + 2 ] ); + + // Now go right to left, merging last tree with + // next to last. The result becomes the new last. + for( ; j >= 2; j -= 2 ) + compareAndLink( treeArray[ j - 2 ], treeArray[ j ] ); + return treeArray[ 0 ]; +} + +/** +* Internal method to clone subtree. +* WARNING: This is prone to running out of stack space. +*/ +template <class T> +PairNode<T> * +PairingHeap<T>::clone( PairNode<T> * t ) const +{ + if( t == NULL ) + return NULL; + else + { + PairNode<T> *p = new PairNode<T>( t->element ); + if( ( p->leftChild = clone( t->leftChild ) ) != NULL ) + p->leftChild->prev = p; + if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL ) + p->nextSibling->prev = p; + return p; + } +} + +#endif diff --git a/src/removeoverlap/pairingheap/PairingHeap.h b/src/removeoverlap/pairingheap/PairingHeap.h new file mode 100644 index 000000000..586a591a8 --- /dev/null +++ b/src/removeoverlap/pairingheap/PairingHeap.h @@ -0,0 +1,111 @@ +/** + * \brief Pairing heap datastructure implementation + * + * Based on example code in "Data structures and Algorithm Analysis in C++" + * by Mark Allen Weiss, used and released under the GPL by permission + * of the author. + * + * No promises about correctness. Use at your own risk! + * + * Authors: + * Mark Allen Weiss + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ +#ifndef PAIRING_HEAP_H_ +#define PAIRING_HEAP_H_ +#include <stdlib.h> +// Pairing heap class +// +// CONSTRUCTION: with no parameters +// +// ******************PUBLIC OPERATIONS********************* +// PairNode & insert( x ) --> Insert x +// deleteMin( minItem ) --> Remove (and optionally return) smallest item +// T findMin( ) --> Return smallest item +// bool isEmpty( ) --> Return true if empty; else false +// bool isFull( ) --> Return true if empty; else false +// void makeEmpty( ) --> Remove all items +// void decreaseKey( PairNode p, newVal ) +// --> Decrease value in node p +// ******************ERRORS******************************** +// Throws Underflow as warranted + + +// Node and forward declaration because g++ does +// not understand nested classes. +template <class T> +class PairingHeap; + +template <class T> +class PairNode +{ + T element; + PairNode *leftChild; + PairNode *nextSibling; + PairNode *prev; + + PairNode( const T & theElement ) : element( theElement ), + leftChild(NULL), nextSibling(NULL), prev(NULL) { } + friend class PairingHeap<T>; +}; + +template <class T> +class Comparator +{ +public: + virtual bool isLessThan(const T &lhs, const T &rhs) const = 0; +}; + +template <class T> +class PairingHeap +{ +public: + PairingHeap( bool (*lessThan)(T &lhs, T &rhs) ); + PairingHeap( const PairingHeap & rhs ); + ~PairingHeap( ); + + bool isEmpty( ) const; + bool isFull( ) const; + int size(); + + PairNode<T> *insert( const T & x ); + const T & findMin( ) const; + void deleteMin( ); + void makeEmpty( ); + void decreaseKey( PairNode<T> *p, const T & newVal ); + void merge( PairingHeap<T> *rhs ) + { + PairNode<T> *broot=rhs->getRoot(); + if (root == NULL) { + if(broot != NULL) { + root = broot; + } + } else { + compareAndLink(root, broot); + } + counter+=rhs->size(); + } + + const PairingHeap & operator=( const PairingHeap & rhs ); +protected: + PairNode<T> * getRoot() { + PairNode<T> *r=root; + root=NULL; + return r; + } +private: + PairNode<T> *root; + bool (*lessThan)(T &lhs, T &rhs); + int counter; + void reclaimMemory( PairNode<T> *t ) const; + void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const; + PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const; + PairNode<T> * clone( PairNode<T> * t ) const; +}; + +#include "PairingHeap.cpp" +#endif diff --git a/src/removeoverlap/pairingheap/dsexceptions.h b/src/removeoverlap/pairingheap/dsexceptions.h new file mode 100644 index 000000000..bef2c78c5 --- /dev/null +++ b/src/removeoverlap/pairingheap/dsexceptions.h @@ -0,0 +1,9 @@ +#ifndef DSEXCEPTIONS_H_ +#define DSEXCEPTIONS_H_ + +class Underflow { }; +class Overflow { }; +class OutOfMemory { }; +class BadIterator { }; + +#endif diff --git a/src/removeoverlap/placement_SolveVPSC.cpp b/src/removeoverlap/placement_SolveVPSC.cpp new file mode 100755 index 000000000..a9f4344c8 --- /dev/null +++ b/src/removeoverlap/placement_SolveVPSC.cpp @@ -0,0 +1,130 @@ +#include <jni.h> +#include "placement_SolveVPSC.h" +#include <stdio.h> +#include "solve_VPSC.h" +#include "variable.h" +#include "constraint.h" +#include "remove_rectangle_overlap.h" +#include "generate-constraints.h" +#include <assert.h> +#include <map> +#define MaxSize 500 + +JNIEXPORT jdouble JNICALL Java_placement_SolveVPSC_solve + (JNIEnv *env, jobject obj, jobjectArray vName, jdoubleArray vWeight, jdoubleArray vDesPos, jintArray cLeft, jintArray cRight, jdoubleArray cGap, jdoubleArray vResult, jint mode) +{ + jsize n = env->GetArrayLength(vWeight); + jsize m = env->GetArrayLength(cLeft); + int i; + double *lvWeight = env->GetDoubleArrayElements(vWeight, 0); + double *lvDesPos = env->GetDoubleArrayElements(vDesPos, 0); + long *lcLeft = env->GetIntArrayElements(cLeft, 0); + long *lcRight = env->GetIntArrayElements(cRight, 0); + double *lcGap = env->GetDoubleArrayElements(cGap, 0); + Variable **vs=new Variable*[n]; + Constraint **cs=new Constraint*[m]; + for (i=0; i<n; i++) { + jstring lvName = (jstring)env->GetObjectArrayElement(vName, i); + const char *name = env->GetStringUTFChars(lvName, NULL); + // once upon a time variables had real names, now you'll have to + // track them by number. + vs[i]=new Variable(i,lvDesPos[i],lvWeight[i]); + } + for (i=0; i<m; i++) { + cs[i]=new Constraint(vs[lcLeft[i]],vs[lcRight[i]],lcGap[i]); + } + double cost=0; + VPSC vpsc(vs,n,cs,m); + if(mode==0) { + vpsc.satisfy(); + } else { + vpsc.solve(); + } + for (i=0; i<n; i++) { + double p=vs[i]->position(); + env->SetDoubleArrayRegion(vResult, i,1,&p); + } + for (i=0; i<m; i++) { + delete cs[i]; + } + delete [] cs; + for (i=0; i<n; i++) { + delete vs[i]; + } + env->ReleaseIntArrayElements(cLeft, lcLeft, 0); + env->ReleaseIntArrayElements(cRight, lcRight, 0); + env->ReleaseDoubleArrayElements(cGap, lcGap, 0); + env->ReleaseDoubleArrayElements(vWeight, lvWeight, 0); + env->ReleaseDoubleArrayElements(vDesPos, lvDesPos, 0); + delete [] vs; + return cost; +} + +static Variable **vs; +static Constraint **cs; +static int m,n; +JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateXConstraints +(JNIEnv *env, jobject obj, jdoubleArray rMinX, jdoubleArray rMaxX, jdoubleArray rMinY, jdoubleArray rMaxY, jdoubleArray rWeight) { + n = (int)env->GetArrayLength(rWeight); + Rectangle **rs=new Rectangle*[n]; + double *ws = env->GetDoubleArrayElements(rWeight, 0); + double *minX = env->GetDoubleArrayElements(rMinX, 0); + double *maxX = env->GetDoubleArrayElements(rMaxX, 0); + double *minY = env->GetDoubleArrayElements(rMinY, 0); + double *maxY = env->GetDoubleArrayElements(rMaxY, 0); + for(int i=0;i<n;i++) rs[i]=new Rectangle(minX[i],maxX[i],minY[i],maxY[i]); + m = generateXConstraints(rs, ws, n, vs, cs, true); + return m; +} + +JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateYConstraints +(JNIEnv *env, jobject obj, jdoubleArray rMinX, jdoubleArray rMaxX, jdoubleArray rMinY, jdoubleArray rMaxY, jdoubleArray rWeight) { + n = (int)env->GetArrayLength(rWeight); + Rectangle **rs=new Rectangle*[n]; + double *ws = env->GetDoubleArrayElements(rWeight, 0); + double *minX = env->GetDoubleArrayElements(rMinX, 0); + double *maxX = env->GetDoubleArrayElements(rMaxX, 0); + double *minY = env->GetDoubleArrayElements(rMinY, 0); + double *maxY = env->GetDoubleArrayElements(rMaxY, 0); + for(int i=0;i<n;i++) rs[i]=new Rectangle(minX[i],maxX[i],minY[i],maxY[i]); + m = generateYConstraints(rs, ws, n, vs, cs); + return m; +} +using namespace std; +JNIEXPORT void JNICALL Java_placement_SolveVPSC_getConstraints +(JNIEnv *env, jobject obj, jintArray cLeft, jintArray cRight, jdoubleArray cGap) { + map<Variable*,int> vmap; + for(int i=0;i<n;i++) { + vmap[vs[i]]=i; + } + + for(int i=0;i<m;i++) { + jint l=vmap[cs[i]->left]; + jint r=vmap[cs[i]->right]; + double g=cs[i]->gap; + env->SetIntArrayRegion(cLeft, i,1,&l); + env->SetIntArrayRegion(cRight, i,1,&r); + env->SetDoubleArrayRegion(cGap, i,1,&g); + } +} +JNIEXPORT void JNICALL Java_placement_SolveVPSC_removeOverlaps +(JNIEnv *env, jobject obj, jdoubleArray rMinX, jdoubleArray rMaxX, jdoubleArray rMinY, jdoubleArray rMaxY) { + //assert(1==2); //break for debugging + n = (int)env->GetArrayLength(rMinX); + Rectangle **rs=new Rectangle*[n]; + double *minX = env->GetDoubleArrayElements(rMinX, 0); + double *maxX = env->GetDoubleArrayElements(rMaxX, 0); + double *minY = env->GetDoubleArrayElements(rMinY, 0); + double *maxY = env->GetDoubleArrayElements(rMaxY, 0); + for(int i=0;i<n;i++) rs[i]=new Rectangle(minX[i],maxX[i],minY[i],maxY[i]); + removeRectangleOverlap(rs,n,0,0); + for (i=0; i<n; i++) { + double x=rs[i]->getMinX(); + double y=rs[i]->getMinY(); + env->SetDoubleArrayRegion(rMinX, i,1,&x); + env->SetDoubleArrayRegion(rMinY, i,1,&y); + } + delete [] rs; + env->ReleaseDoubleArrayElements(rMaxX, maxX, 0); + env->ReleaseDoubleArrayElements(rMaxY, maxY, 0); +}
\ No newline at end of file diff --git a/src/removeoverlap/placement_SolveVPSC.h b/src/removeoverlap/placement_SolveVPSC.h new file mode 100755 index 000000000..9f1c10cda --- /dev/null +++ b/src/removeoverlap/placement_SolveVPSC.h @@ -0,0 +1,53 @@ +/* DO NOT EDIT THIS FILE - it is machine generated */ +#include <jni.h> +/* Header for class placement_SolveVPSC */ + +#ifndef _Included_placement_SolveVPSC +#define _Included_placement_SolveVPSC +#ifdef __cplusplus +extern "C" { +#endif +/* + * Class: placement_SolveVPSC + * Method: solve + * Signature: ([Ljava/lang/String;[D[D[I[I[D[DI)D + */ +JNIEXPORT jdouble JNICALL Java_placement_SolveVPSC_solve + (JNIEnv *, jobject, jobjectArray, jdoubleArray, jdoubleArray, jintArray, jintArray, jdoubleArray, jdoubleArray, jint); + +/* + * Class: placement_SolveVPSC + * Method: generateXConstraints + * Signature: ([D[D[D[D[D)I + */ +JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateXConstraints + (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray); + +/* + * Class: placement_SolveVPSC + * Method: generateYConstraints + * Signature: ([D[D[D[D[D)I + */ +JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateYConstraints + (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray); + +/* + * Class: placement_SolveVPSC + * Method: getConstraints + * Signature: ([I[I[D)V + */ +JNIEXPORT void JNICALL Java_placement_SolveVPSC_getConstraints + (JNIEnv *, jobject, jintArray, jintArray, jdoubleArray); + +/* + * Class: placement_SolveVPSC + * Method: removeOverlaps + * Signature: ([D[D[D[D)V + */ +JNIEXPORT void JNICALL Java_placement_SolveVPSC_removeOverlaps + (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray); + +#ifdef __cplusplus +} +#endif +#endif diff --git a/src/removeoverlap/remove_rectangle_overlap-test.cpp b/src/removeoverlap/remove_rectangle_overlap-test.cpp new file mode 100644 index 000000000..9999d027e --- /dev/null +++ b/src/removeoverlap/remove_rectangle_overlap-test.cpp @@ -0,0 +1,308 @@ +#include "removeoverlap/remove_rectangle_overlap.h" +#include <unistd.h> // for alarm() +#include <time.h> // for srand seed and clock(). +#include <glib/gmacros.h> +#include <glib/gmem.h> +#include <cstdlib> +#include <cmath> +#include "removeoverlap/generate-constraints.h" +#include "utest/utest.h" +using std::abs; +using std::rand; + +static bool +possibly_eq(double const a, double const b) +{ + return abs(a - b) < 1e-13; +} + +static bool +possibly_le(double const a, double const b) +{ + return a - b < 1e-13; +} + +static void +show_rects(unsigned const n_rects, double const rect2coords[][4]) +{ + for (unsigned i = 0; i < n_rects; ++i) { + printf("{%g, %g, %g, %g},\n", + rect2coords[i][0], + rect2coords[i][1], + rect2coords[i][2], + rect2coords[i][3]); + } +} + +/** + * Returns the signum of x, but erring towards returning 0 if x is "not too far" from 0. ("Not too + * far from 0" means [-0.9, 0.9] in current version.) + */ +static int +sgn0(double const x) +{ + if (x <= -0.9) { + return -1; + } else if (0.9 <= x) { + return 1; + } else { + return 0; + } +} + +static void +test_case(unsigned const n_rects, double const rect2coords[][4]) +{ + Rectangle **rs = (Rectangle **) g_malloc(sizeof(Rectangle*) * n_rects); + for (unsigned i = 0; i < n_rects; ++i) { + rs[i] = new Rectangle(rect2coords[i][0], + rect2coords[i][1], + rect2coords[i][2], + rect2coords[i][3]); + } + removeRectangleOverlap(rs, n_rects, 0.0, 0.0); + for (unsigned i = 0; i < n_rects; ++i) { + UTEST_ASSERT(possibly_eq(rs[i]->width(), (rect2coords[i][1] - + rect2coords[i][0] ))); + UTEST_ASSERT(possibly_eq(rs[i]->height(), (rect2coords[i][3] - + rect2coords[i][2] ))); + for (unsigned j = 0; j < i; ++j) { + if (!( possibly_le(rs[i]->getMaxX(), rs[j]->getMinX()) || + possibly_le(rs[j]->getMaxX(), rs[i]->getMinX()) || + possibly_le(rs[i]->getMaxY(), rs[j]->getMinY()) || + possibly_le(rs[j]->getMaxY(), rs[i]->getMinY()) )) { + show_rects(n_rects, rect2coords); + char buf[32]; + sprintf(buf, "[%u],[%u] of %u", j, i, n_rects); + utest__fail("Found overlap among ", buf, " rectangles"); + } + } + + /* Optimality test. */ + { + bool found_block[2] = {false, false}; + int const desired_movement[2] = {sgn0(rect2coords[i][0] - rs[i]->getMinX()), + sgn0(rect2coords[i][2] - rs[i]->getMinY())}; + for (unsigned j = 0; j < n_rects; ++j) { + if (j == i) + continue; + for (unsigned d = 0; d < 2; ++d) { + if ( ( desired_movement[d] < 0 + ? abs(rs[j]->getMaxD(d) - rs[i]->getMinD(d)) + : abs(rs[i]->getMaxD(d) - rs[j]->getMinD(d)) ) + < .002 ) { + found_block[d] = true; + } + } + } + + for (unsigned d = 0; d < 2; ++d) { + if ( !found_block[d] + && desired_movement[d] != 0 ) { + show_rects(n_rects, rect2coords); + char buf[32]; + sprintf(buf, "%c in rectangle [%u] of %u", "XY"[d], i, n_rects); + utest__fail("Found clear non-optimality in ", buf, " rectangles"); + } + } + } + } + for (unsigned i = 0; i < n_rects; ++i) { + delete rs[i]; + } + g_free(rs); +} + +int main() +{ + srand(time(NULL)); + + /* Ensure that the program doesn't run for more than 30 seconds. */ + alarm(30); + + utest_start("removeRectangleOverlap(zero gaps)"); + + /* Derived from Bulia's initial test case. This used to crash. */ + UTEST_TEST("eg0") { + double case0[][4] = { + {-180.5, 69.072, 368.071, 629.071}, + {99.5, 297.644, 319.5, 449.071}, + {199.5, 483.358, 450.929, 571.929}, + {168.071, 277.644, 462.357, 623.357}, + {99.5, 99.751, 479.5, 674.786}, + {-111.929, 103.358, 453.786, 611.929}, + {-29.0714, 143.358, 273.786, 557.643}, + {122.357, 269.072, 322.357, 531.929}, + {256.643, 357.644, 396.643, 520.5} + }; + test_case(G_N_ELEMENTS(case0), case0); + } + +#if 0 /* This involves a zero-height rect, so we'll ignore for the moment. */ + UTEST_TEST("eg1") { + double case1[][4] = { + {5, 14, 9, 14}, + {6, 13, 6, 8}, + {11, 12, 5, 5}, + {5, 8, 5, 7}, + {12, 14, 14, 15}, + {12, 14, 1, 14}, + {1, 15, 14, 15}, + {5, 6, 13, 13} + }; + test_case(G_N_ELEMENTS(case1), case1); + } +#endif + + /* The next few examples used to result in overlaps. */ + UTEST_TEST("eg2") { + double case2[][4] = { + {3, 4, 6, 13}, + {0, 1, 0, 5}, + {0, 4, 1, 6}, + {2, 5, 0, 6}, + {0, 10, 9, 13}, + {5, 11, 1, 13}, + {1, 2, 3, 8} + }; + test_case(G_N_ELEMENTS(case2), case2); + } + + UTEST_TEST("eg3") { + double case3[][4] = { + {0, 5, 0, 3}, + {1, 2, 1, 3}, + {3, 7, 4, 7}, + {0, 9, 4, 5}, + {3, 7, 0, 3} + }; + test_case(G_N_ELEMENTS(case3), case3); + } + + UTEST_TEST("eg4") { + double case4[][4] = { + {0, 1, 2, 3}, + {0, 4, 0, 4}, + {1, 6, 0, 4}, + {2, 3, 4, 5}, + {0, 5, 4, 6} + }; + test_case(G_N_ELEMENTS(case4), case4); + } + + UTEST_TEST("eg5") { + double case5[][4] = { + {1, 5, 1, 2}, + {1, 6, 5, 7}, + {6, 8, 1, 2}, + {2, 3, 1, 4}, + {5, 8, 2, 6} + }; + test_case(G_N_ELEMENTS(case5), case5); + } + + /* This one causes overlap in 2005-12-19 04:00 UTC version. */ + UTEST_TEST("olap6") { + double case6[][4] = { + {7, 22, 39, 54}, + {7, 33, 0, 59}, + {3, 26, 16, 56}, + {7, 17, 18, 20}, + {1, 59, 11, 26}, + {19, 20, 13, 49}, + {1, 10, 0, 4}, + {47, 52, 1, 3} + }; + test_case(G_N_ELEMENTS(case6), case6); + } + + /* The next two examples caused loops in the version at 2005-12-07 04:00 UTC. */ + UTEST_TEST("loop0") { + double loop0[][4] = { + {13, 16, 6, 27}, + {0, 6, 0, 12}, + {11, 14, 1, 10}, + {12, 39, 5, 24}, + {14, 34, 4, 7}, + {1, 30, 20, 27}, + {1, 6, 1, 2}, + {19, 28, 10, 24}, + {4, 34, 15, 21}, + {7, 13, 13, 34} + }; + test_case(G_N_ELEMENTS(loop0), loop0); + } + + UTEST_TEST("loop1") { + double loop1[][4] = { + {6, 18, 9, 16}, + {8, 26, 10, 13}, + {3, 10, 0, 14}, + {0, 5, 16, 22}, + {1, 8, 11, 21}, + {1, 5, 0, 13}, + {24, 25, 0, 2} + }; + test_case(G_N_ELEMENTS(loop1), loop1); + } + + UTEST_TEST("loop2") { + double loop2[][4] = { + {16, 22, 9, 16}, + {8, 9, 14, 19}, + {17, 25, 8, 13}, + {10, 26, 26, 29}, + {14, 19, 9, 19}, + {0, 18, 3, 12}, + {7, 8, 14, 22}, + {14, 20, 25, 29} + }; + test_case(G_N_ELEMENTS(loop2), loop2); + } + + /* Random cases of up to 10 rectangles, with small non-neg int coords. */ + for (unsigned n = 0; n <= 10; ++n) { + char buf[64]; + sprintf(buf, "random ints with %u rectangles", n); + UTEST_TEST(buf) { + unsigned const fld_size = 8 * n; + double (*coords)[4] = (double (*)[4]) g_malloc(n * 4 * sizeof(double)); + clock_t const clock_stop = clock() + CLOCKS_PER_SEC; + for (unsigned repeat = (n == 0 ? 1 + : n == 1 ? 36 + : (1 << 16) ); repeat--;) { + for (unsigned i = 0; i < n; ++i) { + for (unsigned d = 0; d < 2; ++d) { + //unsigned const start = rand() % fld_size; + //unsigned const end = start + rand() % (fld_size - start); + unsigned const end = 1 + (rand() % (fld_size - 1)); + unsigned const start = rand() % end; + coords[i][2 * d] = start; + coords[i][2 * d + 1] = end; + } + } + test_case(n, coords); + if (clock() >= clock_stop) { + break; + } + } + g_free(coords); + } + } + + return ( utest_end() + ? EXIT_SUCCESS + : EXIT_FAILURE ); +} + + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 : diff --git a/src/removeoverlap/remove_rectangle_overlap.cpp b/src/removeoverlap/remove_rectangle_overlap.cpp new file mode 100755 index 000000000..30dbbaf9e --- /dev/null +++ b/src/removeoverlap/remove_rectangle_overlap.cpp @@ -0,0 +1,109 @@ +#include <iostream> +#include <cassert> +#include "generate-constraints.h" +#include "solve_VPSC.h" +#include "variable.h" +#include "constraint.h" +#ifdef RECTANGLE_OVERLAP_LOGGING +using std::ios; +using std::ofstream; +using std::endl; +#endif + +#define EXTRA_GAP 0.0001 + +double Rectangle::xBorder=0; +double Rectangle::yBorder=0; +/** + * Takes an array of n rectangles and moves them as little as possible + * such that rectangles are separated by at least xBorder horizontally + * and yBorder vertically + * + * Works in three passes: + * 1) removes some overlap horizontally + * 2) removes remaining overlap vertically + * 3) a last horizontal pass removes all overlap starting from original + * x-positions - this corrects the case where rectangles were moved + * too much in the first pass. + */ +void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBorder) { + assert(0 <= n); + try { + // The extra gap avoids numerical imprecision problems + Rectangle::setXBorder(xBorder+EXTRA_GAP); + Rectangle::setYBorder(yBorder+EXTRA_GAP); + double *ws=new double[n]; + for(int i=0;i<n;i++) { + ws[i]=1; + } + Variable **vs; + Constraint **cs; + double *oldX = new double[n]; + int m=generateXConstraints(rs,ws,n,vs,cs,true); + for(int i=0;i<n;i++) { + oldX[i]=vs[i]->desiredPosition; + } + VPSC vpsc_x(vs,n,cs,m); +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Calling VPSC: Horizontal pass 1"<<endl; + f.close(); +#endif + vpsc_x.solve(); + for(int i=0;i<n;i++) { + rs[i]->moveCentreX(vs[i]->position()); + delete vs[i]; + } + delete [] vs; + for(int i = 0; i < m; ++i) { + delete cs[i]; + } + delete [] cs; + // Removing the extra gap here ensures things that were moved to be adjacent to + // one another above are not considered overlapping + Rectangle::setXBorder(Rectangle::xBorder-EXTRA_GAP); + m=generateYConstraints(rs,ws,n,vs,cs); + VPSC vpsc_y(vs,n,cs,m); +#ifdef RECTANGLE_OVERLAP_LOGGING + f.open(LOGFILE,ios::app); + f<<"Calling VPSC: Vertical pass"<<endl; + f.close(); +#endif + vpsc_y.solve(); + for(int i=0;i<n;i++) { + rs[i]->moveCentreY(vs[i]->position()); + rs[i]->moveCentreX(oldX[i]); + delete vs[i]; + } + delete [] vs; + delete [] oldX; + for(int i = 0; i < m; ++i) { + delete cs[i]; + } + delete [] cs; + Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP); + m=generateXConstraints(rs,ws,n,vs,cs,false); + VPSC vpsc_x2(vs,n,cs,m); +#ifdef RECTANGLE_OVERLAP_LOGGING + f.open(LOGFILE,ios::app); + f<<"Calling VPSC: Horizontal pass 2"<<endl; + f.close(); +#endif + vpsc_x2.solve(); + for(int i=0;i<n;i++) { + rs[i]->moveCentreX(vs[i]->position()); + delete vs[i]; + } + delete [] vs; + for(int i = 0; i < m; ++i) { + delete cs[i]; + } + delete [] cs; + delete [] ws; + } catch (char *str) { + std::cerr<<str<<std::endl; + for(int i=0;i<n;i++) { + std::cerr << *rs[i]<<std::endl; + } + } +} diff --git a/src/removeoverlap/remove_rectangle_overlap.h b/src/removeoverlap/remove_rectangle_overlap.h new file mode 100755 index 000000000..9dc84f83a --- /dev/null +++ b/src/removeoverlap/remove_rectangle_overlap.h @@ -0,0 +1,21 @@ +#ifndef REMOVE_RECTANGLE_OVERLAP_H_SEEN +#define REMOVE_RECTANGLE_OVERLAP_H_SEEN + +/** + * \file Declaration of main internal remove-overlaps function. + */ +/* + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +class Rectangle; + +void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBorder); + + +#endif /* !REMOVE_RECTANGLE_OVERLAP_H_SEEN */ diff --git a/src/removeoverlap/removeoverlap.cpp b/src/removeoverlap/removeoverlap.cpp new file mode 100644 index 000000000..9d7beb45f --- /dev/null +++ b/src/removeoverlap/removeoverlap.cpp @@ -0,0 +1,80 @@ +/** \file + * Interface between Inkscape code (SPItem) and remove-overlaps function. + */ +/* +* Authors: +* Tim Dwyer <tgdwyer@gmail.com> +* +* Copyright (C) 2005 Authors +* +* Released under GNU GPL. Read the file 'COPYING' for more information. +*/ +#include "util/glib-list-iterators.h" +#include "sp-item.h" +#include "sp-item-transform.h" +#include "removeoverlap/generate-constraints.h" +#include "removeoverlap/remove_rectangle_overlap.h" + +/** +* Takes a list of inkscape items and moves them as little as possible +* such that rectangular bounding boxes are separated by at least xGap +* horizontally and yGap vertically +*/ +void removeoverlap(GSList const *const items, double const xGap, double const yGap) { + if(!items) { + return; + } + + using Inkscape::Util::GSListConstIterator; + std::list<SPItem *> selected; + selected.insert<GSListConstIterator<SPItem *> >(selected.end(), items, NULL); + if (selected.empty()) return; + int n=selected.size(); + + //Check 2 or more selected objects + if (n < 2) return; + + Rectangle **rs = new Rectangle*[n]; + int i=0; + + NR::Point const gap(xGap, yGap); + for (std::list<SPItem *>::iterator it(selected.begin()); + it != selected.end(); + ++it) + { + using NR::X; using NR::Y; + NR::Rect const item_box(sp_item_bbox_desktop(*it)); + + /* The current algorithm requires widths & heights to be strictly positive. */ + NR::Point min(item_box.min()); + NR::Point max(item_box.max()); + for (unsigned d = 0; d < 2; ++d) { + double const minsize = 1; // arbitrary positive number + if (max[d] - min[d] + gap[d] < minsize) { + double const mid = .5 * (min[d] + max[d]); + min[d] = mid - .5*minsize; + max[d] = mid + .5*minsize; + } else { + min[d] -= .5*gap[d]; + max[d] += .5*gap[d]; + } + } + rs[i++] = new Rectangle(min[X], max[X], + min[Y], max[Y]); + } + removeRectangleOverlap(rs, n, 0.0, 0.0); + i=0; + for (std::list<SPItem *>::iterator it(selected.begin()); + it != selected.end(); + ++it) + { + NR::Rect const item_box(sp_item_bbox_desktop(*it)); + Rectangle *r = rs[i++]; + NR::Point const curr(item_box.midpoint()); + NR::Point const dest(r->getCentreX(), + r->getCentreY()); + sp_item_move_rel(*it, NR::translate(dest - curr)); + delete r; + } + delete [] rs; +} diff --git a/src/removeoverlap/removeoverlap.h b/src/removeoverlap/removeoverlap.h new file mode 100644 index 000000000..b904f52f1 --- /dev/null +++ b/src/removeoverlap/removeoverlap.h @@ -0,0 +1,17 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#ifndef SEEN_REMOVEOVERLAP_H +#define SEEN_REMOVEOVERLAP_H + +void removeoverlap(GSList const *items, double xGap, double yGap); + +#endif // SEEN_REMOVEOVERLAP_H diff --git a/src/removeoverlap/solve_VPSC.cpp b/src/removeoverlap/solve_VPSC.cpp new file mode 100644 index 000000000..296cc415b --- /dev/null +++ b/src/removeoverlap/solve_VPSC.cpp @@ -0,0 +1,265 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#include <cassert> +#include "constraint.h" +#include "block.h" +#include "blocks.h" +#include "solve_VPSC.h" +#ifdef RECTANGLE_OVERLAP_LOGGING +using std::ios; +using std::ofstream; +using std::endl; +#endif + +using std::list; +using std::set; + +VPSC::VPSC(Variable *vs[], const int n, Constraint *cs[], const int m) : cs(cs), m(m) { + //assert(!constraintGraphIsCyclic(vs,n)); + bs=new Blocks(vs,n); +#ifdef RECTANGLE_OVERLAP_LOGGING + printBlocks(); +#endif +} +VPSC::~VPSC() { + delete bs; +} + +// useful in debugging +void VPSC::printBlocks() { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + for(set<Block*>::iterator i=bs->begin();i!=bs->end();i++) { + Block *b=*i; + f<<" "<<*b<<endl; + } + for(int i=0;i<m;i++) { + f<<" "<<*cs[i]<<endl; + } +#endif +} +/** +* Produces a feasible - though not necessarily optimal - solution by +* examining blocks in the partial order defined by the directed acyclic +* graph of constraints. For each block (when processing left to right) we +* maintain the invariant that all constraints to the left of the block +* (incoming constraints) are satisfied. This is done by repeatedly merging +* blocks into bigger blocks across violated constraints (most violated +* first) fixing the position of variables inside blocks relative to one +* another so that constraints internal to the block are satisfied. +*/ +void VPSC::satisfy() { + list<Variable*> *vs=bs->totalOrder(); + for(list<Variable*>::iterator i=vs->begin();i!=vs->end();i++) { + Variable *v=*i; + if(!v->block->deleted) { + bs->mergeLeft(v->block); + } + } + bs->cleanup(); + for(int i=0;i<m;i++) { + if(cs[i]->slack()<-0.0000001) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl; +#endif + assert(cs[i]->slack()>-0.0000001); + throw "Unsatisfied constraint"; + } + } + delete vs; +} + +void VPSC::refine() { + bool solved=false; + // Solve shouldn't loop indefinately + // ... but just to make sure we limit the number of iterations + int maxtries=100; + while(!solved&&maxtries>=0) { + solved=true; + maxtries--; + for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) { + Block *b=*i; + b->setUpInConstraints(); + b->setUpOutConstraints(); + } + for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) { + Block *b=*i; + Constraint *c=b->findMinLM(); + if(c!=NULL && c->lm<0) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Split on constraint: "<<*c<<endl; +#endif + // Split on c + Block *l=NULL, *r=NULL; + bs->split(b,l,r,c); + bs->cleanup(); + // split alters the block set so we have to restart + solved=false; + break; + } + } + } + for(int i=0;i<m;i++) { + if(cs[i]->slack()<-0.0000001) { + assert(cs[i]->slack()>-0.0000001); + throw "Unsatisfied constraint"; + } + } +} +/** + * Calculate the optimal solution. After using satisfy() to produce a + * feasible solution, refine() examines each block to see if further + * refinement is possible by splitting the block. This is done repeatedly + * until no further improvement is possible. + */ +void VPSC::solve() { + satisfy(); + refine(); +} + +/** + * incremental version of solve that should allow refinement after blocks are + * moved. Work in progress. + */ +void VPSC::move_and_split() { + //assert(!blockGraphIsCyclic()); + for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) { + Block *b=*i; + if(!b->deleted) { + b->wposn = b->desiredWeightedPosition(); + b->posn = b->wposn / b->weight; + Variable *v=b->vars->front(); + bs->mergeLeft(b); + // b may be merged away, so get any new block from one of its members + bs->mergeRight(v->block); + } + } + bs->cleanup(); + // assert(!blockGraphIsCyclic()); + refine(); +} + +#include <map> +using std::map; +using std::vector; +struct node { + set<node*> in; + set<node*> out; +}; +/* +// useful in debugging - cycles would be BAD +bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) { + map<Variable*, node*> varmap; + vector<node*> graph; + for(int i=0;i<n;i++) { + node *u=new node; + graph.push_back(u); + varmap[vs[i]]=u; + } + for(int i=0;i<n;i++) { + for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();c++) { + Variable *l=(*c)->left; + varmap[vs[i]]->in.insert(varmap[l]); + } + + for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();c++) { + Variable *r=(*c)->right; + varmap[vs[i]]->out.insert(varmap[r]); + } + } + while(graph.size()>0) { + node *u=NULL; + vector<node*>::iterator i=graph.begin(); + for(;i!=graph.end();i++) { + u=*i; + if(u->in.size()==0) { + break; + } + } + if(i==graph.end() && graph.size()>0) { + //cycle found! + return true; + } else { + graph.erase(i); + for(set<node*>::iterator j=u->out.begin();j!=u->out.end();j++) { + node *v=*j; + v->in.erase(u); + } + delete u; + } + } + for(unsigned i=0; i<graph.size(); i++) { + delete graph[i]; + } + return false; +} + +// useful in debugging - cycles would be BAD +bool VPSC::blockGraphIsCyclic() { + map<Block*, node*> bmap; + vector<node*> graph; + for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) { + Block *b=*i; + node *u=new node; + graph.push_back(u); + bmap[b]=u; + } + for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) { + Block *b=*i; + b->setUpInConstraints(); + Constraint *c=b->findMinInConstraint(); + while(c!=NULL) { + Block *l=c->left->block; + bmap[b]->in.insert(bmap[l]); + b->deleteMinInConstraint(); + c=b->findMinInConstraint(); + } + + b->setUpOutConstraints(); + c=b->findMinOutConstraint(); + while(c!=NULL) { + Block *r=c->right->block; + bmap[b]->out.insert(bmap[r]); + b->deleteMinOutConstraint(); + c=b->findMinOutConstraint(); + } + } + while(graph.size()>0) { + node *u=NULL; + vector<node*>::iterator i=graph.begin(); + for(;i!=graph.end();i++) { + u=*i; + if(u->in.size()==0) { + break; + } + } + if(i==graph.end() && graph.size()>0) { + //cycle found! + return true; + } else { + graph.erase(i); + for(set<node*>::iterator j=u->out.begin();j!=u->out.end();j++) { + node *v=*j; + v->in.erase(u); + } + delete u; + } + } + for(unsigned i=0; i<graph.size(); i++) { + delete graph[i]; + } + return false; +} +*/ + diff --git a/src/removeoverlap/solve_VPSC.h b/src/removeoverlap/solve_VPSC.h new file mode 100644 index 000000000..c7da502fb --- /dev/null +++ b/src/removeoverlap/solve_VPSC.h @@ -0,0 +1,41 @@ +/** +* \brief Remove overlaps function +* +* Authors: +* Tim Dwyer <tgdwyer@gmail.com> +* +* Copyright (C) 2005 Authors +* +* Released under GNU GPL. Read the file 'COPYING' for more information. +*/ + +#ifndef SEEN_REMOVEOVERLAP_SOLVE_VPSC_H +#define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H + +class Variable; +class Constraint; +class Blocks; + +/** + * Variable Placement with Separation Constraints problem instance + */ +class VPSC { +public: + void satisfy(); + void solve(); + + void move_and_split(); + VPSC(Variable *vs[], const int n, Constraint *cs[], const int m); + ~VPSC(); +protected: + Blocks *bs; + void refine(); +private: + void printBlocks(); + bool constraintGraphIsCyclic(Variable *vs[], const int n); + bool blockGraphIsCyclic(); + Constraint **cs; + int m; +}; + +#endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H diff --git a/src/removeoverlap/variable.cpp b/src/removeoverlap/variable.cpp new file mode 100644 index 000000000..0cf2e28a7 --- /dev/null +++ b/src/removeoverlap/variable.cpp @@ -0,0 +1,20 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ +#include "variable.h" +std::ostream& operator <<(std::ostream &os, const Variable &v) { + os << "(" << v.id << "=" << v.position() << ")"; + return os; +} + +#include "block.h" +double Variable::position() const { + return block->posn+offset; +} diff --git a/src/removeoverlap/variable.h b/src/removeoverlap/variable.h new file mode 100644 index 000000000..492e7504a --- /dev/null +++ b/src/removeoverlap/variable.h @@ -0,0 +1,46 @@ +/** + * \brief Remove overlaps function + * + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL. Read the file 'COPYING' for more information. + */ + +#ifndef SEEN_REMOVEOVERLAP_VARIABLE_H +#define SEEN_REMOVEOVERLAP_VARIABLE_H + +#include <vector> +#include <iostream> +class Block; +class Constraint; + +class Variable +{ + friend std::ostream& operator <<(std::ostream &os, const Variable &v); +public: + static const unsigned int _TOSTRINGBUFFSIZE=20; + const int id; // useful in log files + double desiredPosition; + const double weight; + double offset; + Block *block; + bool visited; + std::vector<Constraint*> in; + std::vector<Constraint*> out; + char *toString(); + inline Variable(const int id, const double desiredPos, const double weight) + : id(id) + , desiredPosition(desiredPos) + , weight(weight) + { + } + double position() const; + ~Variable(void){ + in.clear(); + out.clear(); + } +}; +#endif // SEEN_REMOVEOVERLAP_VARIABLE_H |