#ifndef COLA_H #define COLA_H #include <utility> #include <iterator> #include <vector> #include <algorithm> #include <cmath> #include <iostream> #include <cassert> #include "gradient_projection.h" #include "straightener.h" typedef vector<unsigned> Cluster; typedef vector<Cluster*> Clusters; 00017 namespace vpsc { class Rectangle; } namespace cola { using vpsc::Rectangle; typedef pair<unsigned, unsigned> Edge; // a graph component with a list of node_ids giving indices for some larger list of nodes // for the nodes in this component, and a list of edges - node indices relative to this component class Component { public: vector<unsigned> node_ids; vector<Rectangle*> rects; vector<Edge> edges; SimpleConstraints scx, scy; virtual ~Component(); void moveRectangles(double x, double y); Rectangle* getBoundingBox(); }; // for a graph of n nodes, return connected components void connectedComponents( const vector<Rectangle*> &rs, const vector<Edge> &es, const SimpleConstraints &scx, const SimpleConstraints &scy, vector<Component*> &components); // move the contents of each component so that the components do not // overlap. void separateComponents(const vector<Component*> &components); // defines references to three variables for which the goal function // will be altered to prefer points u-b-v are in a linear arrangement // such that b is placed at u+t(v-u). struct LinearConstraint { LinearConstraint(unsigned u, unsigned v, unsigned b, double w, double frac_ub, double frac_bv, double* X, double* Y) : u(u),v(v),b(b),w(w),frac_ub(frac_ub),frac_bv(frac_bv), tAtProjection(true) { assert(frac_ub<=1.0); assert(frac_bv<=1.0); assert(frac_ub>=0); assert(frac_bv>=0); if(tAtProjection) { double uvx = X[v] - X[u], uvy = Y[v] - Y[u], vbx = X[b] - X[u], vby = Y[b] - Y[u]; t = uvx * vbx + uvy * vby; t/= uvx * uvx + uvy * uvy; // p is the projection point of b on line uv //double px = scalarProj * uvx + X[u]; //double py = scalarProj * uvy + Y[u]; // take t=|up|/|uv| } else { double numerator=X[b]-X[u]; double denominator=X[v]-X[u]; if(fabs(denominator)<0.001) { // if line is close to vertical then use Y coords to compute T numerator=Y[b]-Y[u]; denominator=Y[v]-Y[u]; } if(fabs(denominator)<0.0001) { denominator=1; } t=numerator/denominator; } duu=(1-t)*(1-t); duv=t*(1-t); dub=t-1; dvv=t*t; dvb=-t; dbb=1; //printf("New LC: t=%f\n",t); } unsigned u; unsigned v; unsigned b; double w; // weight double t; // 2nd partial derivatives of the goal function // (X[b] - (1-t) X[u] - t X[v])^2 double duu; double duv; double dub; double dvv; double dvb; double dbb; // Length of each segment as a fraction of the total edge length double frac_ub; double frac_bv; bool tAtProjection; }; typedef vector<LinearConstraint*> LinearConstraints; class TestConvergence { public: double old_stress; TestConvergence(const double& tolerance = 0.001, const unsigned maxiterations = 1000) : tolerance(tolerance), maxiterations(maxiterations) { reset(); } virtual ~TestConvergence() {} virtual bool operator()(double new_stress, double* X, double* Y) { //std::cout<<"iteration="<<iterations<<", new_stress="<<new_stress<<std::endl; if (old_stress == DBL_MAX) { old_stress = new_stress; if(++iterations>=maxiterations) {; return true; } else { return false; } } bool converged = fabs(new_stress - old_stress) / (new_stress + 1e-10) < tolerance || ++iterations > maxiterations; old_stress = new_stress; return converged; } void reset() { old_stress = DBL_MAX; iterations = 0; } private: const double tolerance; const unsigned maxiterations; unsigned iterations; }; static TestConvergence defaultTest(0.0001,100); class ConstrainedMajorizationLayout { public: ConstrainedMajorizationLayout( vector<Rectangle*>& rs, vector<Edge>& es, double* eweights, double idealLength, TestConvergence& done=defaultTest); void moveBoundingBoxes() { for(unsigned i=0;i<lapSize;i++) { boundingBoxes[i]->moveCentreX(X[i]); boundingBoxes[i]->moveCentreY(Y[i]); } } void setupConstraints( AlignmentConstraints* acsx, AlignmentConstraints* acsy, bool avoidOverlaps, PageBoundaryConstraints* pbcx = NULL, PageBoundaryConstraints* pbcy = NULL, SimpleConstraints* scx = NULL, SimpleConstraints* scy = NULL, Clusters* cs = NULL, vector<straightener::Edge*>* straightenEdges = NULL); void addLinearConstraints(LinearConstraints* linearConstraints); void setupDummyVars(); virtual ~ConstrainedMajorizationLayout() { if(boundingBoxes) { delete [] boundingBoxes; } if(constrainedLayout) { delete gpX; delete gpY; } for(unsigned i=0;i<lapSize;i++) { delete [] lap2[i]; delete [] Dij[i]; } delete [] lap2; delete [] Dij; delete [] X; delete [] Y; } bool run(); void straighten(vector<straightener::Edge*>&, Dim); bool avoidOverlaps; bool constrainedLayout; private: double euclidean_distance(unsigned i, unsigned j) { return sqrt( (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j])); } double compute_stress(double **Dij); void majlayout(double** Dij,GradientProjection* gp, double* coords); void majlayout(double** Dij,GradientProjection* gp, double* coords, double* b); unsigned n; // is lapSize + dummyVars unsigned lapSize; // lapSize is the number of variables for actual nodes double** lap2; // graph laplacian double** Q; // quadratic terms matrix used in computations double** Dij; double tol; TestConvergence& done; Rectangle** boundingBoxes; double *X, *Y; Clusters* clusters; double edge_length; LinearConstraints *linearConstraints; GradientProjection *gpX, *gpY; vector<straightener::Edge*>* straightenEdges; }; } #endif // COLA_H // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4