src/libcola/straightener.h

   1 /*
   2 ** vim: set cindent
   3 ** vim: ts=4 sw=4 et tw=0 wm=0
   4 */
   5 #ifndef STRAIGHTENER_H
   6 #define STRAIGHTENER_H
   7 #include <set>
   8 #include <libvpsc/generate-constraints.h>
   9 #include "gradient_projection.h"
  10 namespace straightener {
  11     struct Route {
  12         Route(unsigned n) : n(n), xs(new double[n]), ys(new double[n]) {}
  13         ~Route() {
  14             delete [] xs;
  15             delete [] ys;
  16         }
  17         void boundingBox(double &xmin,double &ymin,double &xmax,double &ymax) {
  18             xmin=ymin=DBL_MAX;
  19             xmax=ymax=-DBL_MAX;
  20             for(unsigned i=0;i<n;i++) {
  21                 xmin=min(xmin,xs[i]);
  22                 xmax=max(xmax,xs[i]);
  23                 ymin=min(ymin,ys[i]);
  24                 ymax=max(ymax,ys[i]);
  25             }
  26         }
  27         unsigned n;
  28         double *xs;
  29         double *ys;
  30     };
  31     class Node;
  32     struct Edge {
  33         unsigned id;
  34         unsigned openInd; // position in openEdges
  35         unsigned startNode, endNode;
  36         Route* route;
  37         double xmin, xmax, ymin, ymax;
  38         vector<unsigned> dummyNodes;
  39         vector<unsigned> path;
  40         Edge(unsigned id, unsigned start, unsigned end, Route* route)
  41         : id(id), startNode(start), endNode(end), route(route)
  42         {
  43             route->boundingBox(xmin,ymin,xmax,ymax);
  44         }
  45         ~Edge() {
  46             delete route;
  47         }
  48         void setRoute(Route* r) {
  49             delete route;
  50             route=r;
  51             route->boundingBox(xmin,ymin,xmax,ymax);
  52         }
  53         bool isEnd(unsigned n) {
  54             if(startNode==n||endNode==n) return true;
  55             return false;
  56         }
  57         void nodePath(vector<Node*>& nodes);
  58         void createRouteFromPath(double* X, double* Y) {
  59             Route* r=new Route(path.size());
  60             for(unsigned i=0;i<path.size();i++) {
  61                 r->xs[i]=X[path[i]];
  62                 r->ys[i]=Y[path[i]];
  63             }
  64             setRoute(r);
  65         }
  66         void xpos(double y, vector<double>& xs) {
  67             // search line segments for intersection points with y pos
  68             for(unsigned i=1;i<route->n;i++) {
  69                 double ax=route->xs[i-1], bx=route->xs[i], ay=route->ys[i-1], by=route->ys[i];
  70                 double r=(y-ay)/(by-ay);
  71                 // as long as y is between ay and by then r>0
  72                 if(r>0&&r<=1) {
  73                     xs.push_back(ax+(bx-ax)*r);
  74                 }
  75             }
  76         }
  77         void ypos(double x, vector<double>& ys) {
  78             // search line segments for intersection points with x pos
  79             for(unsigned i=1;i<route->n;i++) {
  80                 double ax=route->xs[i-1], bx=route->xs[i], ay=route->ys[i-1], by=route->ys[i];
  81                 double r=(x-ax)/(bx-ax);
  82                 // as long as y is between ax and bx then r>0
  83                 if(r>0&&r<=1) {
  84                     ys.push_back(ay+(by-ay)*r);
  85                 }
  86             }
  87         }
  88     };
  89     class Node {
  90     public:
  91         unsigned id;
  92         double x,y;
  93         double scanpos;
  94         double width, height;
  95         double xmin, xmax, ymin, ymax;
  96         Edge *edge;
  97         bool dummy;
  98         double weight;
  99         bool open;
 100         Node(unsigned id, vpsc::Rectangle* r) :
 101             id(id),x(r->getCentreX()),y(r->getCentreY()), width(r->width()), height(r->height()),
 102             xmin(x-width/2),xmax(x+width/2),
 103             ymin(y-height/2),ymax(y+height/2),
 104             edge(NULL),dummy(false),weight(-0.1),open(false) { }
 105     private:
 106         friend void sortNeighbours(Node* v, Node* l, Node* r,
 107             double conjpos, vector<Edge*>& openEdges,
 108             vector<Node*>& L,vector<Node*>& nodes, Dim dim);
 109         Node(unsigned id, double x, double y, Edge* e) :
 110             id(id),x(x),y(y), width(4), height(width),
 111             xmin(x-width/2),xmax(x+width/2),
 112             ymin(y-height/2),ymax(y+height/2),
 113             edge(e),dummy(true),weight(-0.1)  {
 114                 e->dummyNodes.push_back(id);
 115             }
 116     };
 117     struct CmpNodePos {
 118         bool operator() (const Node* u, const Node* v) const {
 119             if (u->scanpos < v->scanpos) {
 120                 return true;
 121             }
 122             if (v->scanpos < u->scanpos) {
 123                 return false;
 124             }
 125             return u < v;
 126         }
 127     };
 128     typedef std::set<Node*,CmpNodePos> NodeSet;
 129     void generateConstraints(vector<Node*>& nodes, vector<Edge*>& edges,vector<SimpleConstraint*>& cs, Dim dim);
 130     void nodePath(Edge& e,vector<Node*>& nodes, vector<unsigned>& path);
 131 }
 132
 133 #endif