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 }
133 #endif