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.

(bzr r803)

1 files changed, 131 insertions, 20 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 <tgdwyer@gmail.com>
  *
  * 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 <cassert>
+#include "pairingheap/PairingHeap.h"
 #include "constraint.h"
 #include "block.h"
 #include "blocks.h"
-#include "pairingheap/PairingHeap.h"
 #ifdef RECTANGLE_OVERLAP_LOGGING
 #include <fstream>
 using std::ios;
@@ -21,6 +23,8 @@ using std::endl;
 #endif
 using std::vector;
 
+typedef vector<Constraint*>::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<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
+	for (vector<Variable*>::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<Constraint*>* &h,bool in) {
 	delete h;
 	h = new PairingHeap<Constraint*>(&compareConstraints);
-	for (vector<Variable*>::iterator i=vars->begin();i!=vars->end();i++) {
+	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++) {
+		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<Constraint*>* &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="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
+#endif
+	double dist = c->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)<<endl;
+#endif
+}
 /**
  * Merges b into this block across c.  Can be either a
  * right merge or a left merge
@@ -83,16 +104,21 @@ void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &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="<<dist<<endl;
+#endif
 	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++) {
+	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);
 	}
+	b->deleted=true;
 }
 
 void Block::mergeIn(Block *b) {
@@ -150,7 +176,7 @@ Constraint *Block::findMinInConstraint() {
 			break;
 		}
 	}
-	for(vector<Constraint*>::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<Constraint*>::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->lm<min_lm->lm) min_lm=c;
+			if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
 		}
 	}
-	for(vector<Constraint*>::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->lm<min_lm->lm) min_lm=c;
+			if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) 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<Constraint*>::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<Constraint*>::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<Constraint*>::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<Constraint*>::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<<endl;
+#endif
+	Constraint *c=findMinLMBetween(vl, vr);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"  going to split on: "<<*c<<endl;
+#endif
+	split(lb,rb,c);
+	deleted = true;
+	return c;
+}
+/**
  * 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 
+ * and the right into r.
  */
-void Block::split(Block *&l, Block *&r, Constraint *c) {
+void Block::split(Block* &l, Block* &r, Constraint* c) {
 	c->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<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
+	for (vector<Variable*>::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<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();v++) {
+	for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();++v) {
 		os<<" "<<**v;
 	}
+	if(b.deleted) {
+		os<<" Deleted!";
+	}
     return os;
 }