From 6af8609f35d86944763dc80141002c548984b2ed Mon Sep 17 00:00:00 2001 From: tgdwyer Date: Wed, 10 May 2006 07:13:45 +0000 Subject: [PATCH] Apparently a problem was reported with one of the test cases. I can't reproduce the problem, however solve_VPSC code in inkscape was getting quite out of date with that in www.sf.net/projects/adaptagrams. I've updated the code, which may fix the problem, or at least if it's reported again then I'll know it's still an issue. --- src/removeoverlap/block.cpp | 151 ++++++++++-- src/removeoverlap/block.h | 19 +- src/removeoverlap/blocks.cpp | 15 +- src/removeoverlap/blocks.h | 10 +- src/removeoverlap/constraint.cpp | 28 ++- src/removeoverlap/constraint.h | 13 +- src/removeoverlap/generate-constraints.cpp | 29 ++- src/removeoverlap/generate-constraints.h | 10 +- .../remove_rectangle_overlap-test.cpp | 2 +- .../remove_rectangle_overlap.cpp | 45 ++-- src/removeoverlap/remove_rectangle_overlap.h | 4 +- src/removeoverlap/removeoverlap.cpp | 6 +- src/removeoverlap/removeoverlap.h | 2 +- src/removeoverlap/solve_VPSC.cpp | 230 ++++++++++++++---- src/removeoverlap/solve_VPSC.h | 56 +++-- src/removeoverlap/variable.cpp | 7 +- src/removeoverlap/variable.h | 17 +- 17 files changed, 475 insertions(+), 169 deletions(-) diff --git a/src/removeoverlap/block.cpp b/src/removeoverlap/block.cpp index 7a2ab53af..042d9fc3c 100644 --- a/src/removeoverlap/block.cpp +++ b/src/removeoverlap/block.cpp @@ -1,18 +1,20 @@ /** - * \brief Remove overlaps function + * \brief A block is a group of variables that must be moved together to improve + * the goal function without violating already active constraints. + * The variables in a block are spanned by a tree of active constraints. * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include +#include "pairingheap/PairingHeap.h" #include "constraint.h" #include "block.h" #include "blocks.h" -#include "pairingheap/PairingHeap.h" #ifdef RECTANGLE_OVERLAP_LOGGING #include using std::ios; @@ -21,6 +23,8 @@ using std::endl; #endif using std::vector; +typedef vector::iterator Cit; + void Block::addVariable(Variable *v) { v->block=this; vars->push_back(v); @@ -43,7 +47,7 @@ Block::Block(Variable *v) { double Block::desiredWeightedPosition() { double wp = 0; - for (vector::iterator v=vars->begin();v!=vars->end();v++) { + for (vector::iterator v=vars->begin();v!=vars->end();++v) { wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight; } return wp; @@ -63,10 +67,10 @@ void Block::setUpOutConstraints() { void Block::setUpConstraintHeap(PairingHeap* &h,bool in) { delete h; h = new PairingHeap(&compareConstraints); - for (vector::iterator i=vars->begin();i!=vars->end();i++) { + for (vector::iterator i=vars->begin();i!=vars->end();++i) { Variable *v=*i; vector *cs=in?&(v->in):&(v->out); - for (vector::iterator j=cs->begin();j!=cs->end();j++) { + for (Cit j=cs->begin();j!=cs->end();++j) { Constraint *c=*j; c->timeStamp=blockTimeCtr; if (c->left->block != this && in || c->right->block != this && !in) { @@ -75,6 +79,23 @@ void Block::setUpConstraintHeap(PairingHeap* &h,bool in) { } } } +void Block::merge(Block* b, Constraint* c) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging on: "<<*c<<",c->left->offset="<left->offset<<",c->right->offset="<right->offset<right->offset - c->left->offset - c->gap; + Block *l=c->left->block; + Block *r=c->right->block; + if (vars->size() < b->vars->size()) { + r->merge(l,c,dist); + } else { + l->merge(r,c,-dist); + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" merged block="<<(b->deleted?*this:*b)<* &h,bool in) { * @param distance separation required to satisfy c */ void Block::merge(Block *b, Constraint *c, double dist) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging: "<<*b<<"dist="<active=true; wposn+=b->wposn-dist*b->weight; weight+=b->weight; posn=wposn/weight; - for(vector::iterator i=b->vars->begin();i!=b->vars->end();i++) { + for(vector::iterator i=b->vars->begin();i!=b->vars->end();++i) { Variable *v=*i; v->block=this; v->offset+=dist; vars->push_back(v); } + b->deleted=true; } void Block::mergeIn(Block *b) { @@ -150,7 +176,7 @@ Constraint *Block::findMinInConstraint() { break; } } - for(vector::iterator i=outOfDate.begin();i!=outOfDate.end();i++) { + for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) { v=*i; v->timeStamp=blockTimeCtr; in->insert(v); @@ -197,35 +223,92 @@ inline bool Block::canFollowRight(Constraint *c, Variable *last) { // in min_lm double Block::compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm) { double dfdv=v->weight*(v->position() - v->desiredPosition); - for(vector::iterator it=v->out.begin();it!=v->out.end();it++) { + for(Cit 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->lmlm) min_lm=c; + if(!c->equality&&(min_lm==NULL||c->lmlm)) min_lm=c; } } - for(vector::iterator it=v->in.begin();it!=v->in.end();it++) { + for(Cit 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->lmlm) min_lm=c; + if(!c->equality&&(min_lm==NULL||c->lmlm)) min_lm=c; } } return dfdv; } + +// computes dfdv for each variable and uses the sum of dfdv on either side of +// the constraint c to compute the lagrangian multiplier lm_c. +// The top level v and r are variables between which we want to find the +// constraint with the smallest lm. +// When we find r we pass NULL to subsequent recursive calls, +// thus r=NULL indicates constraints are not on the shortest path. +// Similarly, m is initially NULL and is only assigned a value if the next +// variable to be visited is r or if a possible min constraint is returned from +// a nested call (rather than NULL). +// Then, the search for the m with minimum lm occurs as we return from +// the recursion (checking only constraints traversed left-to-right +// in order to avoid creating any new violations). +// We also do not consider equality constraints as potential split points +Block::Pair Block::compute_dfdv_between(Variable* r, Variable* v, Variable* u, + Direction dir = NONE, bool changedDirection = false) { + double dfdv=v->weight*(v->position() - v->desiredPosition); + Constraint *m=NULL; + for(Cit it(v->in.begin());it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + if(dir==RIGHT) { + changedDirection = true; + } + if(c->left==r) { + r=NULL; + if(!c->equality) m=c; + } + Pair p=compute_dfdv_between(r,c->left,v, + LEFT,changedDirection); + dfdv -= c->lm = -p.first; + if(r && p.second) + m = p.second; + } + } + for(Cit it(v->out.begin());it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + if(dir==LEFT) { + changedDirection = true; + } + if(c->right==r) { + r=NULL; + if(!c->equality) m=c; + } + Pair p=compute_dfdv_between(r,c->right,v, + RIGHT,changedDirection); + dfdv += c->lm = p.first; + if(r && p.second) + m = changedDirection && !c->equality && c->lm < p.second->lm + ? c + : p.second; + } + } + return Pair(dfdv,m); +} + // 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::iterator it=v->out.begin();it!=v->out.end();it++) { + for(Cit 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::iterator it=v->in.begin();it!=v->in.end();it++) { + for(Cit it=v->in.begin();it!=v->in.end();++it) { Constraint *c=*it; if(canFollowLeft(c,u)) { c->lm=0; @@ -243,26 +326,51 @@ Constraint *Block::findMinLM() { compute_dfdv(vars->front(),NULL,min_lm); return min_lm; } +Constraint *Block::findMinLMBetween(Variable* lv, Variable* rv) { + Constraint *min_lm=NULL; + reset_active_lm(vars->front(),NULL); + min_lm=compute_dfdv_between(rv,lv,NULL).second; + 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::iterator c=v->in.begin();c!=v->in.end();c++) { + for (Cit c=v->in.begin();c!=v->in.end();++c) { if (canFollowLeft(*c,u)) populateSplitBlock(b, (*c)->left, v); } - for (vector::iterator c=v->out.begin();c!=v->out.end();c++) { + for (Cit c=v->out.begin();c!=v->out.end();++c) { if (canFollowRight(*c,u)) populateSplitBlock(b, (*c)->right, v); } } +/** + * Block needs to be split because of a violated constraint between vl and vr. + * We need to search the active constraint tree between l and r and find the constraint + * with min lagrangrian multiplier and split at that point. + * Returns the split constraint + */ +Constraint* Block::splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb) { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" need to split between: "<<*vl<<" and "<<*vr<active=false; l=new Block(); populateSplitBlock(l,c->left,c->right); @@ -276,7 +384,7 @@ void Block::split(Block *&l, Block *&r, Constraint *c) { */ double Block::cost() { double c = 0; - for (vector::iterator v=vars->begin();v!=vars->end();v++) { + for (vector::iterator v=vars->begin();v!=vars->end();++v) { double diff = (*v)->position() - (*v)->desiredPosition; c += (*v)->weight * diff * diff; } @@ -285,8 +393,11 @@ double Block::cost() { ostream& operator <<(ostream &os, const Block &b) { os<<"Block:"; - for(vector::iterator v=b.vars->begin();v!=b.vars->end();v++) { + for(vector::iterator v=b.vars->begin();v!=b.vars->end();++v) { os<<" "<<**v; } + if(b.deleted) { + os<<" Deleted!"; + } return os; } diff --git a/src/removeoverlap/block.h b/src/removeoverlap/block.h index 7905309bb..997009a55 100644 --- a/src/removeoverlap/block.h +++ b/src/removeoverlap/block.h @@ -1,12 +1,14 @@ /** - * \brief Remove overlaps function + * \brief A block is a group of variables that must be moved together to improve + * the goal function without violating already active constraints. + * The variables in a block are spanned by a tree of active constraints. * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #ifndef SEEN_REMOVEOVERLAP_BLOCK_H @@ -29,16 +31,19 @@ public: double wposn; Block(Variable *v=NULL); ~Block(void); - Constraint *findMinLM(); - Constraint *findMinInConstraint(); - Constraint *findMinOutConstraint(); + Constraint* findMinLM(); + Constraint* findMinLMBetween(Variable* lv, Variable* rv); + Constraint* findMinInConstraint(); + Constraint* findMinOutConstraint(); void deleteMinInConstraint(); void deleteMinOutConstraint(); double desiredWeightedPosition(); void merge(Block *b, Constraint *c, double dist); + void merge(Block *b, Constraint *c); void mergeIn(Block *b); void mergeOut(Block *b); void split(Block *&l, Block *&r, Constraint *c); + Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb); void setUpInConstraints(); void setUpOutConstraints(); double cost(); @@ -47,8 +52,12 @@ public: PairingHeap *in; PairingHeap *out; private: + typedef enum {NONE, LEFT, RIGHT} Direction; + typedef std::pair Pair; void reset_active_lm(Variable *v, Variable *u); double compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm); + Pair compute_dfdv_between( + Variable*, Variable*, Variable*, Direction, bool); bool canFollowLeft(Constraint *c, Variable *last); bool canFollowRight(Constraint *c, Variable *last); void populateSplitBlock(Block *b, Variable *v, Variable *u); diff --git a/src/removeoverlap/blocks.cpp b/src/removeoverlap/blocks.cpp index 13da8e15e..62b7e99f5 100644 --- a/src/removeoverlap/blocks.cpp +++ b/src/removeoverlap/blocks.cpp @@ -10,7 +10,7 @@ * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include "blocks.h" @@ -30,7 +30,7 @@ using std::copy; long blockTimeCtr; -Blocks::Blocks(Variable *vs[], const int n) : vs(vs),nvs(n) { +Blocks::Blocks(const int n, Variable *vs[]) : vs(vs),nvs(n) { blockTimeCtr=0; for(int i=0;i::iterator i=begin();i!=end();i++) { + for(set::iterator i=begin();i!=end();++i) { delete *i; } clear(); @@ -66,7 +66,7 @@ list *Blocks::totalOrder() { void Blocks::dfsVisit(Variable *v, list *order) { v->visited=true; vector::iterator it=v->out.begin(); - for(;it!=v->out.end();it++) { + for(;it!=v->out.end();++it) { Constraint *c=*it; if(!c->right->visited) { dfsVisit(c->right, order); @@ -149,9 +149,8 @@ void Blocks::removeBlock(Block *doomed) { //erase(doomed); } void Blocks::cleanup() { - vector bcopy(size()); - copy(begin(),end(),bcopy.begin()); - for(vector::iterator i=bcopy.begin();i!=bcopy.end();i++) { + vector bcopy(begin(),end()); + for(vector::iterator i=bcopy.begin();i!=bcopy.end();++i) { Block *b=*i; if(b->deleted) { erase(b); @@ -189,7 +188,7 @@ void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) { */ double Blocks::cost() { double c = 0; - for(set::iterator i=begin();i!=end();i++) { + for(set::iterator i=begin();i!=end();++i) { c += (*i)->cost(); } return c; diff --git a/src/removeoverlap/blocks.h b/src/removeoverlap/blocks.h index 437af6310..1a603eb41 100644 --- a/src/removeoverlap/blocks.h +++ b/src/removeoverlap/blocks.h @@ -1,12 +1,16 @@ /** - * \brief Remove overlaps function + * \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 * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #ifndef SEEN_REMOVEOVERLAP_BLOCKS_H @@ -30,7 +34,7 @@ class Constraint; class Blocks : public std::set { public: - Blocks(Variable *vs[], const int n); + Blocks(const int n, Variable *vs[]); ~Blocks(void); void mergeLeft(Block *r); void mergeRight(Block *l); diff --git a/src/removeoverlap/constraint.cpp b/src/removeoverlap/constraint.cpp index bb889c4d9..7c200878b 100644 --- a/src/removeoverlap/constraint.cpp +++ b/src/removeoverlap/constraint.cpp @@ -1,29 +1,47 @@ /** - * \brief Remove overlaps function + * \brief A constraint determines a minimum or exact spacing required between + * two variables. * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include "constraint.h" #include -Constraint::Constraint(Variable *left, Variable *right, double gap) +Constraint::Constraint(Variable *left, Variable *right, double gap, bool equality) : left(left), right(right), gap(gap), timeStamp(0), active(false), - visited(false) + visited(false), + equality(equality) { left->out.push_back(this); right->in.push_back(this); } +Constraint::~Constraint() { + Constraints::iterator i; + for(i=left->out.begin(); i!=left->out.end(); i++) { + if(*i==this) break; + } + left->out.erase(i); + for(i=right->in.begin(); i!=right->in.end(); i++) { + if(*i==this) break; + } + right->in.erase(i); +} std::ostream& operator <<(std::ostream &os, const Constraint &c) { - os<<*c.left<<"+"<block->timeStamp<<",cts="< * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #ifndef SEEN_REMOVEOVERLAP_CONSTRAINT_H @@ -23,13 +24,13 @@ public: Variable *right; double gap; double lm; - Constraint(Variable *left, Variable *right, double gap); - ~Constraint(void){}; - inline double slack() const { return right->position() - gap - left->position(); } - //inline bool operator<(Constraint const &o) const { return slack() < o.slack(); } + Constraint(Variable *left, Variable *right, double gap, bool equality=false); + ~Constraint(); + inline double Constraint::slack() const { return right->position() - gap - left->position(); } long timeStamp; bool active; bool visited; + bool equality; }; #include #include "block.h" diff --git a/src/removeoverlap/generate-constraints.cpp b/src/removeoverlap/generate-constraints.cpp index a8bfe28e7..312ad960b 100644 --- a/src/removeoverlap/generate-constraints.cpp +++ b/src/removeoverlap/generate-constraints.cpp @@ -1,12 +1,13 @@ /** - * \brief Remove overlaps function + * \brief Functions to automatically generate constraints for the + * rectangular node overlap removal problem. * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include @@ -58,11 +59,11 @@ struct Node { void setNeighbours(NodeSet *left, NodeSet *right) { leftNeighbours=left; rightNeighbours=right; - for(NodeSet::iterator i=left->begin();i!=left->end();i++) { + 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++) { + for(NodeSet::iterator i=right->begin();i!=right->end();++i) { Node *v=*(i); v->addLeftNeighbour(this); } @@ -116,7 +117,7 @@ NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) { NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) { NodeSet *rightv = new NodeSet; NodeSet::iterator i=scanline.find(v); - for(i++;i!=scanline.end(); i++) { + for(++i;i!=scanline.end(); ++i) { Node *u=*(i); if(u->r->overlapX(v->r)<=0) { rightv->insert(u); @@ -159,17 +160,15 @@ int compare_events(const void *a, const void *b) { } /** - * Prepares variables and constraints in order to apply VPSC horizontally. + * 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. */ -int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs, bool useNeighbourLists) { +int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists) { events=new Event*[2*n]; int i,m,ctr=0; - vector constraints; - vars=new Variable*[n]; for(i=0;igetCentreX(),weights[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()); @@ -177,6 +176,7 @@ int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variabl qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events ); NodeSet scanline; + vector constraints; for(i=0;i<2*n;i++) { Event *e=events[i]; Node *v=e->v; @@ -247,21 +247,20 @@ int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variabl } /** - * Prepares variables and constraints in order to apply VPSC vertically to remove ALL overlap. + * Prepares constraints in order to apply VPSC vertically to remove ALL overlap. */ -int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs) { +int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs) { events=new Event*[2*n]; int ctr=0,i,m; - vector constraints; - vars=new Variable*[n]; for(i=0;igetCentreY(),weights[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 constraints; for(i=0;i<2*n;i++) { Event *e=events[i]; Node *v=e->v; diff --git a/src/removeoverlap/generate-constraints.h b/src/removeoverlap/generate-constraints.h index ad9ccb1f9..56ee9536a 100644 --- a/src/removeoverlap/generate-constraints.h +++ b/src/removeoverlap/generate-constraints.h @@ -1,14 +1,14 @@ /** - * \brief Remove overlaps function + * \brief Functions to automatically generate constraints for the + * rectangular node overlap removal problem. * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ - #ifndef SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H #define SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H #include @@ -71,8 +71,8 @@ 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 generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists); +int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs); -int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vs, Constraint **&cs); #endif // SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H diff --git a/src/removeoverlap/remove_rectangle_overlap-test.cpp b/src/removeoverlap/remove_rectangle_overlap-test.cpp index 9999d027e..87cf4cbb0 100644 --- a/src/removeoverlap/remove_rectangle_overlap-test.cpp +++ b/src/removeoverlap/remove_rectangle_overlap-test.cpp @@ -60,7 +60,7 @@ test_case(unsigned const n_rects, double const rect2coords[][4]) rect2coords[i][2], rect2coords[i][3]); } - removeRectangleOverlap(rs, n_rects, 0.0, 0.0); + removeRectangleOverlap(n_rects,rs,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] ))); diff --git a/src/removeoverlap/remove_rectangle_overlap.cpp b/src/removeoverlap/remove_rectangle_overlap.cpp index 9f98d5811..6f6ace03a 100755 --- a/src/removeoverlap/remove_rectangle_overlap.cpp +++ b/src/removeoverlap/remove_rectangle_overlap.cpp @@ -1,3 +1,14 @@ +/** + * \brief remove overlaps between a set of rectangles. + * + * Authors: + * Tim Dwyer + * + * Copyright (C) 2005 Authors + * + * Released under GNU LGPL. Read the file 'COPYING' for more information. + */ + #include #include #include "generate-constraints.h" @@ -28,24 +39,23 @@ double Rectangle::yBorder=0; * 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) { +void removeRectangleOverlap(unsigned n, Rectangle *rs[], 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]; + Variable **vs=new Variable*[n]; for(int i=0;idesiredPosition; } - VPSC vpsc_x(vs,n,cs,m); + VPSC vpsc_x(n,vs,m,cs); #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"Calling VPSC: Horizontal pass 1"<moveCentreX(vs[i]->position()); - delete vs[i]; } - delete [] vs; for(int i = 0; i < m; ++i) { delete cs[i]; } @@ -64,8 +72,8 @@ void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBord // 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); + m=generateYConstraints(n,rs,vs,cs); + VPSC vpsc_y(n,vs,m,cs); #ifdef RECTANGLE_OVERLAP_LOGGING f.open(LOGFILE,ios::app); f<<"Calling VPSC: Vertical pass"<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); + m=generateXConstraints(n,rs,vs,cs,false); + VPSC vpsc_x2(n,vs,m,cs); #ifdef RECTANGLE_OVERLAP_LOGGING f.open(LOGFILE,ios::app); f<<"Calling VPSC: Horizontal pass 2"<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) { + } catch (char const *str) { std::cerr< selected; selected.insert >(selected.end(), items, NULL); if (selected.empty()) return; - int n=selected.size(); + unsigned n=selected.size(); //Check 2 or more selected objects if (n < 2) return; @@ -62,7 +62,7 @@ void removeoverlap(GSList const *const items, double const xGap, double const yG rs[i++] = new Rectangle(min[X], max[X], min[Y], max[Y]); } - removeRectangleOverlap(rs, n, 0.0, 0.0); + removeRectangleOverlap(n, rs, 0.0, 0.0); i=0; for (std::list::iterator it(selected.begin()); it != selected.end(); diff --git a/src/removeoverlap/removeoverlap.h b/src/removeoverlap/removeoverlap.h index b904f52f1..2fb26e794 100644 --- a/src/removeoverlap/removeoverlap.h +++ b/src/removeoverlap/removeoverlap.h @@ -6,7 +6,7 @@ * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #ifndef SEEN_REMOVEOVERLAP_H diff --git a/src/removeoverlap/solve_VPSC.cpp b/src/removeoverlap/solve_VPSC.cpp index f2a7f0e85..21865c518 100644 --- a/src/removeoverlap/solve_VPSC.cpp +++ b/src/removeoverlap/solve_VPSC.cpp @@ -1,12 +1,13 @@ /** - * \brief Remove overlaps function + * \brief Solve an instance of the "Variable Placement with Separation + * Constraints" problem. * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include @@ -14,6 +15,8 @@ #include "block.h" #include "blocks.h" #include "solve_VPSC.h" +#include +#include #ifdef RECTANGLE_OVERLAP_LOGGING #include using std::ios; @@ -21,14 +24,22 @@ using std::ofstream; using std::endl; #endif +using std::ostringstream; 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); +IncVPSC::IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]) + : VPSC(n,vs,m,cs) { + inactive.assign(cs,cs+m); + for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) { + (*i)->active=false; + } +} +VPSC::VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]) : cs(cs), m(m), vs(vs) { + bs=new Blocks(n, vs); #ifdef RECTANGLE_OVERLAP_LOGGING printBlocks(); + assert(!constraintGraphIsCyclic(n,vs)); #endif } VPSC::~VPSC() { @@ -39,11 +50,11 @@ VPSC::~VPSC() { void VPSC::printBlocks() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); - for(set::iterator i=bs->begin();i!=bs->end();i++) { + for(set::iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; f<<" "<<*b< *vs=bs->totalOrder(); - for(list::iterator i=vs->begin();i!=vs->end();i++) { + for(list::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;islack()<-0.0000001) { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); @@ -84,16 +95,16 @@ 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; + unsigned maxtries=100; while(!solved&&maxtries>=0) { solved=true; maxtries--; - for(set::const_iterator i=bs->begin();i!=bs->end();i++) { + for(set::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; b->setUpInConstraints(); b->setUpOutConstraints(); } - for(set::const_iterator i=bs->begin();i!=bs->end();i++) { + for(set::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; Constraint *c=b->findMinLM(); if(c!=NULL && c->lm<0) { @@ -111,7 +122,7 @@ void VPSC::refine() { } } } - for(int i=0;islack()<-0.0000001) { assert(cs[i]->slack()>-0.0000001); throw "Unsatisfied constraint"; @@ -129,26 +140,163 @@ void VPSC::solve() { refine(); } +void IncVPSC::solve() { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"solve_inc()..."<cost(); + do { + lastcost=cost; + satisfy(); + splitBlocks(); + cost = bs->cost(); +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" cost="<0.0001); +} /** - * incremental version of solve that should allow refinement after blocks are - * moved. Work in progress. + * incremental version of satisfy that allows refinement after blocks are + * moved. + * + * - move blocks to new positions + * - repeatedly merge across most violated constraint until no more + * violated constraints exist + * + * Note: there is a special case to handle when the most violated constraint + * is between two variables in the same block. Then, we must split the block + * over an active constraint between the two variables. We choose the + * constraint with the most negative lagrangian multiplier. */ -void VPSC::move_and_split() { - //assert(!blockGraphIsCyclic()); - for(set::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); +void IncVPSC::satisfy() { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"satisfy_inc()..."<equality || v->slack()<-0.000001)) { + assert(!v->active); + Block *lb = v->left->block, *rb = v->right->block; + if(lb != rb) { + lb->merge(rb,v); + } else { + if(splitCtr++>10000) { + throw "Cycle Error!"; + } + // constraint is within block, need to split first + inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb)); + lb->merge(rb,v); + bs->insert(lb); } } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" finished merges."<cleanup(); + for(unsigned i=0;islack()<-0.0000001) { + //assert(cs[i]->slack()>-0.0000001); + ostringstream s; + s<<"Unsatisfied constraint: "<<*v; + throw s.str().c_str(); + } + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" finished cleanup."<::const_iterator i(bs->begin());i!=bs->end();++i) { + Block *b = *i; + b->wposn = b->desiredWeightedPosition(); + b->posn = b->wposn / b->weight; + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" moved blocks."<::const_iterator i(bs->begin());i!=bs->end();++i) { + Block* b = *i; + Constraint* v=b->findMinLM(); + if(v!=NULL && v->lm < -0.0000001) { + assert(!v->equality); +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" found split point: "<<*v<<" lm="<lm<left->block, *l=NULL, *r=NULL; + assert(v->left->block == v->right->block); + double pos = b->posn; + b->split(l,r,v); + l->posn=r->posn=pos; + l->wposn = l->posn * l->weight; + r->wposn = r->posn * r->weight; + bs->insert(l); + bs->insert(r); + b->deleted=true; + inactive.push_back(v); +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" new blocks: "<<*l<<" and "<<*r<cleanup(); - // assert(!blockGraphIsCyclic()); - refine(); +} + +/** + * Scan constraint list for the most violated constraint, or the first equality + * constraint + */ +Constraint* IncVPSC::mostViolated(ConstraintList &l) { + double minSlack = DBL_MAX; + Constraint* v=NULL; +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Looking for most violated..."<slack(); + if(c->equality || slack < minSlack) { + minSlack=slack; + v=c; + deletePoint=i; + if(c->equality) break; + } + } + // Because the constraint list is not order dependent we just + // move the last element over the deletePoint and resize + // downwards. There is always at least 1 element in the + // vector because of search. + if(deletePoint != end && (minSlack<-0.0000001||v->equality)) { + *deletePoint = l[l.size()-1]; + l.resize(l.size()-1); + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" most violated is: "<<*v< @@ -158,23 +306,22 @@ struct node { set in; set out; }; -/* // useful in debugging - cycles would be BAD -bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) { +bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) { map varmap; vector graph; - for(int i=0;i::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();c++) { + for(unsigned i=0;i::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::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();c++) { + for(vector::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) { Variable *r=(*c)->right; varmap[vs[i]]->out.insert(varmap[r]); } @@ -182,7 +329,7 @@ bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) { while(graph.size()>0) { node *u=NULL; vector::iterator i=graph.begin(); - for(;i!=graph.end();i++) { + for(;i!=graph.end();++i) { u=*i; if(u->in.size()==0) { break; @@ -193,14 +340,14 @@ bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) { return true; } else { graph.erase(i); - for(set::iterator j=u->out.begin();j!=u->out.end();j++) { + for(set::iterator j=u->out.begin();j!=u->out.end();++j) { node *v=*j; v->in.erase(u); } delete u; } } - for(unsigned i=0; i bmap; vector graph; - for(set::const_iterator i=bs->begin();i!=bs->end();i++) { + for(set::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::const_iterator i=bs->begin();i!=bs->end();i++) { + for(set::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; b->setUpInConstraints(); Constraint *c=b->findMinInConstraint(); @@ -239,7 +386,7 @@ bool VPSC::blockGraphIsCyclic() { while(graph.size()>0) { node *u=NULL; vector::iterator i=graph.begin(); - for(;i!=graph.end();i++) { + for(;i!=graph.end();++i) { u=*i; if(u->in.size()==0) { break; @@ -250,7 +397,7 @@ bool VPSC::blockGraphIsCyclic() { return true; } else { graph.erase(i); - for(set::iterator j=u->out.begin();j!=u->out.end();j++) { + for(set::iterator j=u->out.begin();j!=u->out.end();++j) { node *v=*j; v->in.erase(u); } @@ -262,5 +409,4 @@ bool VPSC::blockGraphIsCyclic() { } return false; } -*/ diff --git a/src/removeoverlap/solve_VPSC.h b/src/removeoverlap/solve_VPSC.h index c7da502fb..9f6244a5a 100644 --- a/src/removeoverlap/solve_VPSC.h +++ b/src/removeoverlap/solve_VPSC.h @@ -1,17 +1,18 @@ /** -* \brief Remove overlaps function -* -* Authors: -* Tim Dwyer -* -* Copyright (C) 2005 Authors -* -* Released under GNU GPL. Read the file 'COPYING' for more information. -*/ - + * \brief Solve an instance of the "Variable Placement with Separation + * Constraints" problem. + * + * Authors: + * Tim Dwyer + * + * Copyright (C) 2005 Authors + * + * Released under GNU LGPL. Read the file 'COPYING' for more information. + */ #ifndef SEEN_REMOVEOVERLAP_SOLVE_VPSC_H #define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H +#include class Variable; class Constraint; class Blocks; @@ -21,21 +22,36 @@ class Blocks; */ class VPSC { public: - void satisfy(); - void solve(); + virtual void satisfy(); + virtual void solve(); - void move_and_split(); - VPSC(Variable *vs[], const int n, Constraint *cs[], const int m); - ~VPSC(); + VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]); + virtual ~VPSC(); + Constraint** getConstraints() { return cs; } + Variable** getVariables() { return vs; } protected: Blocks *bs; - void refine(); -private: + Constraint **cs; + unsigned m; + Variable **vs; void printBlocks(); - bool constraintGraphIsCyclic(Variable *vs[], const int n); +private: + void refine(); + bool constraintGraphIsCyclic(const unsigned n, Variable *vs[]); bool blockGraphIsCyclic(); - Constraint **cs; - int m; }; +class IncVPSC : public VPSC { +public: + unsigned splitCnt; + void satisfy(); + void solve(); + void moveBlocks(); + void splitBlocks(); + IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]); +private: + typedef std::vector ConstraintList; + ConstraintList inactive; + Constraint* mostViolated(ConstraintList &l); +}; #endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H diff --git a/src/removeoverlap/variable.cpp b/src/removeoverlap/variable.cpp index 0cf2e28a7..1890f788e 100644 --- a/src/removeoverlap/variable.cpp +++ b/src/removeoverlap/variable.cpp @@ -1,12 +1,11 @@ /** - * \brief Remove overlaps function * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include "variable.h" std::ostream& operator <<(std::ostream &os, const Variable &v) { @@ -14,7 +13,3 @@ std::ostream& operator <<(std::ostream &os, const Variable &v) { 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 index e682dd7df..86e16737e 100644 --- a/src/removeoverlap/variable.h +++ b/src/removeoverlap/variable.h @@ -1,14 +1,12 @@ /** - * \brief Remove overlaps function * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ - #ifndef SEEN_REMOVEOVERLAP_VARIABLE_H #define SEEN_REMOVEOVERLAP_VARIABLE_H @@ -16,30 +14,35 @@ #include class Block; class Constraint; +#include "block.h" +typedef std::vector Constraints; 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 in; - std::vector out; + Constraints in; + Constraints out; char *toString(); inline Variable(const int id, const double desiredPos, const double weight) : id(id) , desiredPosition(desiredPos) , weight(weight) , offset(0) + , block(NULL) , visited(false) { } - double position() const; + inline double Variable::position() const { + return block->posn+offset; + } + //double position() const; ~Variable(void){ in.clear(); out.clear(); -- 2.39.5