Inkscape
Vector Graphics Editor
Loading...
Searching...
No Matches
straightener.cpp
Go to the documentation of this file.
1/*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libcola - A library providing force-directed network layout using the
5 * stress-majorization method subject to separation constraints.
6 *
7 * Copyright (C) 2005-2008 Monash University
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
13 * See the file LICENSE.LGPL distributed with the library.
14 *
15 * This library is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
18 *
19 * Author(s): Tim Dwyer
20 *
21*/
22
23/*
24 * Functions to automatically generate constraints for the
25 * rectangular node overlap removal problem.
26 */
27
28#include <set>
29#include <list>
30#include <cassert>
31#include <iostream>
32#include <cmath>
33
34#include "libvpsc/assertions.h"
35#include "libcola/commondefs.h"
36#include "libcola/cola.h"
39
40//#define STRAIGHTENER_DEBUG 1
41
42using std::list;
43using std::make_pair;
44using std::pair;
45using std::set;
46using std::vector;
47using std::copy;
48
49namespace straightener {
50
51 // is point p on line a-b?
52 static bool pointOnLine(double px,double py, double ax, double ay, double bx, double by, double& tx) {
53 double dx=bx-ax;
54 double dy=by-ay;
55 double ty=0;
56 if(fabs(dx)<0.0001&&fabs(dy)<0.0001) {
57 // runty line!
58 tx=px-ax;
59 ty=py-ay;
60 } else {
61 if(fabs(dx)<0.0001) {
62 //vertical line
63 if(fabs(px-ax)<0.01) {
64 tx=(py-ay)/dy;
65 }
66 } else {
67 tx=(px-ax)/dx;
68 }
69 if(fabs(dy)<0.0001) {
70 //horizontal line
71 if(fabs(py-ay)<0.01) {
72 ty=tx;
73 }
74 } else {
75 ty=(py-ay)/dy;
76 }
77 }
78 //printf(" tx=%f,ty=%f\n",tx,ty);
79 if(fabs(tx-ty)<0.001 && tx>=0 && tx<=1) {
80 return true;
81 }
82 return false;
83 }
85 // the first and last points should not be inside this
86 // rectangle - note that we should not be routing around
87 // rectangles directly connected to this route
88 COLA_ASSERT(!rect->inside(xs[0],ys[0]));
89 COLA_ASSERT(!rect->inside(xs[n-1],ys[n-1]));
90 // first, we examine each point and if it is inside the rectangle, we
91 // project to the nearest edge of the rectangle
92 for(unsigned i=1;i<n-1;i++) {
93 double &x=xs[i], &y=ys[i];
94 if(rect->inside(x,y)) {
95 enum ProjectSide {LEFT, BOTTOM, RIGHT, TOP};
96 unsigned projectSide = LEFT;
97 double minDist = x - rect->getMinX();
98 double dist = y - rect->getMinY();
99 if(dist<minDist) {
100 projectSide = BOTTOM;
101 minDist = dist;
102 }
103 dist = rect->getMaxX() - x;
104 if(dist<minDist) {
105 projectSide = RIGHT;
106 minDist = dist;
107 }
108 dist = rect->getMaxY() - y;
109 if(dist<minDist) {
110 projectSide = TOP;
111 minDist = dist;
112 }
113 switch(projectSide) {
114 case LEFT:
115 x=rect->getMinX();
116 break;
117 case BOTTOM:
118 y=rect->getMinY();
119 break;
120 case RIGHT:
121 x=rect->getMaxX();
122 break;
123 case TOP:
124 y=rect->getMaxY();
125 break;
126 }
127
128 }
129 }
130 // the new route is copied into rxs, rys.
131 vector<double> rxs, rys;
132 double prevX=xs[0], prevY=ys[0];
133 rxs.push_back(prevX);
134 rys.push_back(prevY);
135
136 // check each segment in turn to see if it intersects
137 // with the rectangle.
138 // If an intersecting segment is found:
139 // 1) the segment passes right through the rectangle
140 // - we insert new segments routed around the rectangle
141 // 2) the segment terminates inside the rectangle
142 // - we follow connected segments until we find the exit
143 // point, then we insert a route around the rectangle
144 // 3) the segment just touches one side
145 //
146 for(unsigned i=1;i<n;i++) {
147 // we have projected all points to the boundary already so we shouldn't find any inside
148 COLA_ASSERT(!rect->inside(xs[i],ys[i]));
150 rect->lineIntersections(prevX,prevY,
151 xs[i],ys[i],ri);
152 if(ri.intersects) {
153 int count=ri.countIntersections();
154 COLA_ASSERT(count>0); // can't be 0 because we have detected an intersection
155 COLA_ASSERT(count<4); // assumes no zero width or height rects which would be
156 // the only way for a line segment to touch all 4 sides at once
157 if(count==3) { // runs along one side
158 COLA_ASSERT(!rect->inside(xs[i],ys[i]));
159 } else if(count==2) { // passes right through
160 COLA_ASSERT(!rect->inside(xs[i],ys[i]));
161 double x1=0, y1=0, x2=0, y2=0;
162 ri.nearest(prevX, prevY, x1, y1);
163 ri.nearest(xs[i], ys[i], x2, y2);
164 rect->routeAround(x1, y1, x2, y2, rxs, rys);
165 } else if(count==1) {
166 // single intersection, earlier projection step ensures it is on the
167 // perimeter, so nothing to do
168 }
169 }
170 prevX=xs[i];
171 prevY=ys[i];
172 COLA_ASSERT(!rect->inside(prevX,prevY));
173 rxs.push_back(prevX);
174 rys.push_back(prevY);
175 }
176 delete [] xs;
177 delete [] ys;
178 n=rxs.size();
179 COLA_ASSERT(rys.size()==n);
180 xs = new double[n];
181 ys = new double[n];
182 copy(rxs.begin(),rxs.end(),xs);
183 copy(rys.begin(),rys.end(),ys);
184 }
194 void Edge::nodePath(vector<Node*>& nodes, bool allActive = true) {
195 list<unsigned> ds(dummyNodes.size());
196 copy(dummyNodes.begin(),dummyNodes.end(),ds.begin());
197 //printf("Edge::nodePath: (%d,%d) dummyNodes:%d\n",startNode,endNode,ds.size());
198 path.clear();
199 activePath.clear();
200 path.push_back(startNode);
201 activePath.push_back(0);
202 for(unsigned i=1;i<route->n;i++) {
203 //printf(" checking segment %d-%d\n",i-1,i);
204 set<pair<double,unsigned> > pntsOnLineSegment;
205 for(list<unsigned>::iterator j=ds.begin();j!=ds.end();) {
206 double px=nodes[*j]->pos[0];
207 double py=nodes[*j]->pos[1];
208 double ax=route->xs[i-1];
209 double ay=route->ys[i-1];
210 double bx=route->xs[i];
211 double by=route->ys[i];
212 double t=0;
213 list<unsigned>::iterator copyit=j++;
214 //printf(" px=%f, py=%f, ax=%f, ay=%f, bx=%f, by=%f\n",px,py,ax,ay,bx,by);
215 if(pointOnLine(px,py,ax,ay,bx,by,t)) {
216 //printf(" got node %d\n",*copyit);
217 pntsOnLineSegment.insert(make_pair(t,*copyit));
218 ds.erase(copyit);
219 }
220 }
221 for(set<pair<double,unsigned> >::iterator j=pntsOnLineSegment.begin();j!=pntsOnLineSegment.end();j++) {
222 if(allActive && nodes[j->second]->active) {
223 activePath.push_back(path.size());
224 }
225 path.push_back(j->second);
226 }
227 //printf("\n");
228 }
229 activePath.push_back(path.size());
230 path.push_back(endNode);
231 COLA_ASSERT(ds.empty());
232 }
233 void Edge::createRouteFromPath(std::vector<Node *> const & nodes) {
234 Route* r=new Route(path.size());
235#ifdef STRAIGHTENER_DEBUG
236 //printf("Route:");
237#endif
238 for(unsigned i=0;i<path.size();i++) {
239 r->xs[i]=nodes[path[i]]->pos[0];
240 r->ys[i]=nodes[path[i]]->pos[1];
241#ifdef STRAIGHTENER_DEBUG
242 //printf("(%f,%f)",r->xs[i],r->ys[i]);
243#endif
244 }
245#ifdef STRAIGHTENER_DEBUG
246 //printf("\n");
247#endif
248 setRoute(r);
249 }
250
251 typedef enum {Open, Close} EventType;
252 struct Event {
253 EventType type;
254 Node *v;
255 Edge *e;
256 double pos;
257 Event(EventType t, Node *v, double p) : type(t),v(v),e(nullptr),pos(p) {};
258 Event(EventType t, Edge *e, double p) : type(t),v(nullptr),e(e),pos(p) {};
259 };
260 /*
261 * the following relation defines a strict weak ordering over events, i.e.:
262 * irreflexivity: CompareEvents(e,e) == false
263 * antisymetry: CompareEvents(a,b) => !CompareEvents(b,a)
264 * transitivity: CompareEvents(a,b) && CompareEvents(b,c) => CompareEvents(a,c)
265 * transitivity of equivalence:
266 * !CompareEvents(a,b) && !CompareEvents(b,a) && !CompareEvents(b,c) && !CompareEvents(c,b)
267 * => !CompareEvents(a,c) && !CompareEvents(c,a)
268 */
269 struct CompareEvents {
270 bool operator() (Event *const &a, Event *const &b) const {
271 if(a->pos < b->pos) {
272 return true;
273 } else if(a->pos==b->pos) {
274 // All opens should come before closes when at the same position
275 if(a->type==Open && b->type==Close) return true;
276 if(a->type==Close && b->type==Open) return false;
277 // Edge opens at the same position as node opens, edge comes first
278 if(a->type==Open && b->type==Open) {
279 if(a->e && b->v) return true;
280 if(b->e && a->v) return false;
281 }
282 // Edge closes at the same position as node closes, node comes first
283 if(a->type==Close && b->type==Close) {
284 if(a->e && b->v) return false;
285 if(b->e && a->v) return true;
286 }
287 }
288 return false;
289 }
290 };
291
301 void sortNeighbours(const vpsc::Dim dim, Node * v, Node * l, Node * r,
302 const double conjpos, vector<Edge*> const & openEdges,
303 vector<Node *>& L,vector<Node *>& nodes) {
304 double minpos=-DBL_MAX, maxpos=DBL_MAX;
305 if(l!=nullptr) {
306 L.push_back(l);
307 minpos=l->scanpos;
308 }
309 typedef pair<double,Edge*> PosEdgePair;
310 set<PosEdgePair> sortedEdges;
311 for(unsigned i=0;i<openEdges.size();i++) {
312 Edge *e=openEdges[i];
313 vector<double> bs;
314 if(dim==vpsc::HORIZONTAL) {
315 e->xpos(conjpos,bs);
316 } else {
317 e->ypos(conjpos,bs);
318 }
319 //std::cerr << "edge(intersections="<<bs.size()<<":("<<e->startNode<<","<<e->endNode<<"))"<<std::endl;
320 for(vector<double>::iterator it=bs.begin();it!=bs.end();it++) {
321 sortedEdges.insert(make_pair(*it,e));
322 }
323 }
324 for(set<PosEdgePair>::iterator i=sortedEdges.begin();i!=sortedEdges.end();i++) {
325 double pos=i->first;
326 if(pos < minpos) continue;
327 if(pos > v->scanpos) break;
328 // if edge is connected (start or end) to v then skip
329 // need to record start and end positions of edge segment!
330 Edge* e=i->second;
331 if(e->startNode==v->id||e->endNode==v->id) continue;
332 //if(l!=nullptr&&(e->startNode==l->id||e->endNode==l->id)) continue;
333 //cerr << "edge("<<e->startNode<<","<<e->endNode<<",pts="<<e->pts<<")"<<endl;
334 // here, we probably want to search for existing dummy
335 // nodes associated with the same edge within some
336 // range of (pos,conjpos), rather than creating new ones.
337 // Would require some sort of quad-tree structure
338 Node* d=dim==vpsc::HORIZONTAL?
339 new Node(nodes.size(),pos,conjpos,e):
340 new Node(nodes.size(),conjpos,pos,e);
341 L.push_back(d);
342 nodes.push_back(d);
343 }
344 L.push_back(v);
345
346 if(r!=nullptr) {
347 maxpos=r->scanpos;
348 }
349 for(set<PosEdgePair>::iterator i=sortedEdges.begin();i!=sortedEdges.end();i++) {
350 if(i->first < v->scanpos) continue;
351 if(i->first > maxpos) break;
352 double pos=i->first;
353 // if edge is connected (start or end) to v then skip
354 // need to record start and end positions of edge segment!
355 Edge* e=i->second;
356 if(e->startNode==v->id||e->endNode==v->id) continue;
357 //if(r!=nullptr&&(e->startNode==r->id||e->endNode==r->id)) continue;
358 //cerr << "edge("<<e->startNode<<","<<e->endNode<<",pts="<<e->pts<<")"<<endl;
359 Node* d=dim==vpsc::HORIZONTAL?
360 new Node(nodes.size(),pos,conjpos,e):
361 new Node(nodes.size(),conjpos,pos,e);
362 L.push_back(d);
363 nodes.push_back(d);
364 }
365 if(r!=nullptr) {
366 L.push_back(r);
367 }
368 }
369 static double overlap(vpsc::Dim k, Node const *u, Node const *v) {
370 if (u->pos[k] <= v->pos[k] && v->getMin(k) < u->getMax(k))
371 return u->getMax(k) - v->getMin(k);
372 if (v->pos[k] <= u->pos[k] && u->getMin(k) < v->getMax(k))
373 return v->getMax(k) - u->getMin(k);
374 return 0;
375 }
376
378 Node* u, Node* v, vpsc::Dim dim) {
379 double g=u->length[dim]+v->length[dim];
380 g/=2;
381 double sep=v->pos[dim]-u->pos[dim];
382 if(sep < g) {
383 u->active = true;
384 v->active = true;
385 }
386 //cerr << "Constraint: "<< u->id << "+"<<g<<"<="<<v->id<<endl;
387 return new cola::SeparationConstraint(dim, u->id, v->id, g);
388 }
389
390 template <typename T>
392 const vpsc::Dim dim,
393 const EventType type,
394 T *v,
395 double border) {
396 double pos = (type==Open) ? v->getMin((vpsc::Dim)!dim)-border
397 : v->getMax((vpsc::Dim)!dim)+border ;
398 return new Event(type,v,pos);
399 }
410 const vpsc::Dim dim,
411 vector<Node*> & nodes,
412 vector<Edge*> const & edges,
413 vector<cola::SeparationConstraint*>& cs,
414 bool xSkipping = true) {
415 vector<Event*> events;
416 double nodeFudge=-0.01, edgeFudge=0;
417#ifdef STRAIGHTENER_DEBUG
418 cout << (dim==vpsc::HORIZONTAL
419 ?"scanning top to bottom..."
420 :"scanning left to right...")
421 << endl;
422#endif
423 for(unsigned i=0;i<nodes.size();i++) {
424 Node *v=nodes[i];
425 if(v->scan) {
426 v->scanpos=v->pos[dim];
427 events.push_back(createEvent(dim,Open,v,nodeFudge));
428 events.push_back(createEvent(dim,Close,v,nodeFudge));
429 }
430 }
431 for(unsigned i=0;i<edges.size();i++) {
432 Edge *e=edges[i];
433 events.push_back(createEvent(dim,Open,e,edgeFudge));
434 events.push_back(createEvent(dim,Close,e,edgeFudge));
435 }
436 std::sort(events.begin(),events.end(),CompareEvents());
437
438 NodeSet openNodes;
439 vector<Edge*> openEdges;
440 // scan opening and closing events in order
441 for(unsigned i=0;i<events.size();i++) {
442 Event *e=events[i];
443 Node *v=e->v;
444 if(v!=nullptr) {
445 v->open = true;
446#ifdef STRAIGHTENER_DEBUG
447 printf("NEvent@%f,nid=%d,(%f,%f),w=%f,h=%f,openn=%d,opene=%d\n",e->pos,v->id,v->pos[0],v->pos[1],v->length[0],v->length[1],(int)openNodes.size(),(int)openEdges.size());
448#endif
449 Node *l=nullptr, *r=nullptr;
450 if(!openNodes.empty()) {
451 // it points to the first node to the right of v
452 NodeSet::iterator it=openNodes.lower_bound(v);
453 // step left to find the first node to the left of v
454 while(it--!=openNodes.begin()) {
455 if(!xSkipping
456 || dim!=vpsc::HORIZONTAL
457 || overlap(vpsc::HORIZONTAL,*it,v) <= 0
458 || overlap(vpsc::HORIZONTAL,*it,v) <= overlap(vpsc::VERTICAL,*it,v)) {
459 l=*it;
460 break;
461 }
462#ifdef STRAIGHTENER_DEBUG
463 printf("l=%d\n",l->id);
464#endif
465 }
466 it=openNodes.upper_bound(v);
467 while(it!=openNodes.end()) {
468 if(!xSkipping
469 || dim!=vpsc::HORIZONTAL
470 || overlap(vpsc::HORIZONTAL,v,*it) <= 0
471 || overlap(vpsc::HORIZONTAL,v,*it) <= overlap(vpsc::VERTICAL,v,*it)) {
472 r=*it;
473 break;
474 }
475 it++;
476 }
477 }
478 vector<Node*> L;
479 sortNeighbours(dim,v,l,r,e->pos,openEdges,L,nodes);
480#ifdef STRAIGHTENER_DEBUG
481 printf("L=[");
482 for(unsigned i=0;i<L.size();i++) {
483 printf("%d ",L[i]->id);
484 }
485 printf("]\n");
486#endif
487 // for each dummy node w in L:
488 // if w left of v create constraints l<w, w<v
489 // if w right of v create constraints v<w, w<r
490 for(vector<Node*>::iterator i=L.begin();i!=L.end();i++) {
491 Node* w=*i;
492 if(w->dummy) {
493 // node is on an edge
494 Edge *edge=w->edge;
495 if(w->pos[dim]<v->pos[dim]) { // w left of v
496 if(l!=nullptr&&!edge->isEnd(l->id)) {
497 cs.push_back(createConstraint(l,w,dim));
498 }
499 if(!edge->isEnd(v->id)) {
500 cs.push_back(createConstraint(w,v,dim));
501 }
502 } else { // w right of v
503 if(!edge->isEnd(v->id)) {
504 cs.push_back(createConstraint(v,w,dim));
505 }
506 if(r!=nullptr&&!edge->isEnd(r->id)) {
507 cs.push_back(createConstraint(w,r,dim));
508 }
509 }
510 }
511 }
512 if(e->type==Close) {
513 if(l!=nullptr) cs.push_back(createConstraint(l,v,dim));
514 if(r!=nullptr) cs.push_back(createConstraint(v,r,dim));
515 }
516 }
517 if(e->type==Open) {
518 if(v!=nullptr) {
519 openNodes.insert(v);
520 } else {
521#ifdef STRAIGHTENER_DEBUG
522 printf("EdgeOpen@%f,eid=%d,(u,v)=(%d,%d)\n", e->pos,e->e->id,e->e->startNode,e->e->endNode);
523#endif
524 e->e->openInd=openEdges.size();
525 openEdges.push_back(e->e);
526 }
527 } else {
528 // Close
529 if(v!=nullptr) {
530 openNodes.erase(v);
531 v->open=false;
532 } else {
533#ifdef STRAIGHTENER_DEBUG
534 printf("EdgeClose@%f,eid=%d,(u,v)=(%d,%d)\n", e->pos,e->e->id,e->e->startNode,e->e->endNode);
535#endif
536 unsigned i=e->e->openInd;
537 COLA_ASSERT(openEdges.size()>0);
538 openEdges[i]=openEdges[openEdges.size()-1];
539 openEdges[i]->openInd=i;
540 openEdges.resize(openEdges.size()-1);
541 }
542 }
543 delete e;
544 }
545 }
555 const vpsc::Dim dim,
556 vector<straightener::Node*> & nodes,
557 vector<straightener::Edge*> & edges,
558 vector<vpsc::Rectangle*> const & rs,
559 cola::Cluster const & clusterHierarchy,
560 vector<straightener::Cluster*>& sclusters) {
561 sclusters.clear();
562 for(vector<cola::Cluster*>::const_iterator i
563 =clusterHierarchy.clusters.begin();
564 i!=clusterHierarchy.clusters.end(); i++) {
565 if(cola::ConvexCluster* c=dynamic_cast<cola::ConvexCluster*>(*i)) {
567 // compute scanpos based on average position in scan direction
568 sc->scanpos=0;
569 for(set<unsigned>::iterator it= c->nodes.begin();
570 it != c->nodes.end(); ++it) {
571 straightener::Node* u = nodes[*it];
572 sc->scanpos+=u->pos[dim];
573 u->cluster = sc;
574 }
575 sc->scanpos/=c->nodes.size();
576 sclusters.push_back(sc);
577 c->computeBoundary(rs);
578 // create a chain of dummy nodes for the boundary
579 Node* first = new Node(nodes.size(),c->hullX[0],c->hullY[0]);
580 nodes.push_back(first);
581 Node* u = first;
582 unsigned i=1;
583 for(;i<c->hullX.size();i++) {
584 Node* v = new Node(nodes.size(),c->hullX[i],c->hullY[i]);
585 nodes.push_back(v);
586 Edge* e = new Edge(edges.size(),u->id,v->id,
587 c->hullX[i-1],c->hullY[i-1],c->hullX[i],c->hullY[i]);
588 edges.push_back(e);
589 sc->boundary.push_back(e);
590 u=v;
591 }
592 edges.push_back(
593 new Edge(edges.size(),u->id,first->id,
594 c->hullX[i-1],c->hullY[i-1],c->hullX[0],c->hullY[0]));
595 }
596 }
597 }
598
600 {
601 unsigned n=0;
602 for(std::vector<Edge*>::const_iterator e=boundary.begin();
603 e!=boundary.end();e++) {
604 n+=(*e)->getRoute()->n;
605 }
606 colaCluster->hullX.resize(n);
607 colaCluster->hullY.resize(n);
608 unsigned i=0;
609 for(std::vector<Edge*>::const_iterator e=boundary.begin();
610 e!=boundary.end();e++) {
611 Route const * r=(*e)->getRoute();
612 for(unsigned j=0;j<r->n;j++) {
613 colaCluster->hullX[i]=r->xs[j];
614 colaCluster->hullY[i++]=r->ys[j];
615 }
616 }
617 }
619 const double strength,
620 const vpsc::Dim dim,
621 std::vector<vpsc::Rectangle*> const & rs,
622 cola::FixedList const & fixed,
623 std::vector<Edge*> const & edges,
624 vpsc::Variables const & vs,
625 vpsc::Variables & lvs,
626 vpsc::Constraints & lcs,
627 std::valarray<double> &oldCoords,
628 std::valarray<double> &oldG)
629 : strength(strength),
630 dim(dim),
631 fixed(fixed),
632 edges(edges),
633 vs(vs),
634 lvs(lvs)
635 {
636 unsigned n=rs.size();
637 for (unsigned i=0;i<n;i++) {
638 nodes.push_back(new straightener::Node(i,rs[i]));
639 }
640 vector<cola::SeparationConstraint*> cs;
642 // after generateConstraints we have new dummy nodes at the end of snodes and
643 // constraints in cs
644 // need to create variables for dummy nodes in lvs and constraints in lcs
645 N=nodes.size();
646 g.resize(N);
647 coords.resize(N);
648 for(unsigned i=0;i<n;i++) {
649 g[i]=oldG[i];
650 coords[i]=oldCoords[i];
651 }
652 for (unsigned i=n;i<N;i++) {
653 double desiredPos = nodes[i]->pos[dim];
654 lvs.push_back(new vpsc::Variable(i,desiredPos,1));
655 g[i]=0;
656 coords[i]=desiredPos;
657 }
658 for (vector<cola::SeparationConstraint*>::iterator i=cs.begin();i!=cs.end();i++) {
659 unsigned lv=(*i)->left();
660 unsigned rv=(*i)->right();
661 double gap=(*i)->gap;
662 vpsc::Variable* l = lv<n?vs[lv]:lvs[lv-n];
663 vpsc::Variable* r = rv<n?vs[rv]:lvs[rv-n];
664 lcs.push_back(new vpsc::Constraint(l,r,gap));
665 }
666 for(unsigned i=0;i<edges.size();i++) {
667 edges[i]->nodePath(nodes,false);
668 }
669 for_each(cs.begin(),cs.end(),cola::delete_object());
670 }
672 for_each(nodes.begin(),nodes.end(),cola::delete_object());
673 }
675 // hessian matrix:
676 // diagonal: sum dy2/l^3
677 // off-diag: -dy2/l^3
678 for(unsigned i=0;i<edges.size();i++) {
679 //printf("Straightening path:\n");
680 //edges[i]->print();
681 vector<unsigned>& path=edges[i]->path;
682 COLA_ASSERT(path.size()>0);
683 for(unsigned j=1;j<path.size();j++) {
684 unsigned u=path[j-1], v=path[j];
685 double x1=nodes[u]->pos[0], x2=nodes[v]->pos[0],
686 y1=nodes[u]->pos[1], y2=nodes[v]->pos[1];
687 double dx=x1-x2, dy=y1-y2;
688 double dx2=dx*dx, dy2=dy*dy;
689 double l=sqrt(dx2+dy2);
690 if(l<0.0000001) continue;
691 double f=dim==vpsc::HORIZONTAL?dx:dy;
692 f*=strength/l;
693 if(!fixed.check(u)) { g[u]+=f; }
694 if(!fixed.check(v)) { g[v]-=f; }
695 double h=dim==vpsc::HORIZONTAL?dy2:dx2;
696 h*=strength/(l*l*l);
697 H(u,u)+=h;
698 H(v,v)+=h;
699 H(u,v)-=h;
700 H(v,u)-=h;
701 }
702 }
703 }
704 double Straightener::computeStress(std::valarray<double> const &coords) {
705 double stress=0;
706 for(unsigned i=0;i<edges.size();i++) {
707 vector<unsigned>& path=edges[i]->path;
708 COLA_ASSERT(path.size()>0);
709 for(unsigned j=1;j<path.size();j++) {
710 unsigned u=path[j-1], v=path[j];
711 double x1,x2,y1,y2;
712 if(dim==vpsc::HORIZONTAL) {
713 x1=coords[u];
714 x2=coords[v];
715 y1=nodes[u]->pos[1];
716 y2=nodes[v]->pos[1];
717 } else {
718 x1=nodes[u]->pos[0];
719 x2=nodes[v]->pos[0];
720 y1=coords[u];
721 y2=coords[v];
722 }
723 double dx=x1-x2, dy=y1-y2;
724 double dx2=dx*dx, dy2=dy*dy;
725 double l=sqrt(dx2+dy2);
726 stress+=l;
727 }
728 }
729 return strength*stress;
730 }
731 double Straightener::computeStress2(std::valarray<double> const &coords)
732 {
733 COLA_UNUSED(coords);
734
735 double stress=0;
736 for(unsigned i=0;i<edges.size();i++) {
737 double d = edges[i]->idealLength;
738 double weight=1/(d*d);
739 //printf("pathLength=%f\n",pathLength(edges[i],nodes));
740 double sqrtf=fabs(d-pathLength(edges[i],nodes));
741 stress+=weight*sqrtf*sqrtf;
742 }
743 return strength*stress;
744 }
746 // real nodes
747 for (unsigned i=0;i<N;i++) {
748 Node *n=nodes[i];
749 n->pos[dim]=coords[i];
750 }
751 // dummy bend nodes
752 //printf("got %d dummy nodes\n", (int) lvs.size());
753 dummyNodesX.resize(lvs.size());
754 dummyNodesY.resize(lvs.size());
755 for (unsigned i=0;i<lvs.size();i++) {
756 COLA_ASSERT(i+vs.size() < nodes.size());
757 Node *n=nodes[i+vs.size()];
758 dummyNodesX[i]=n->pos[0];
759 dummyNodesY[i]=n->pos[1];
760 }
761 }
763 for(unsigned i=0;i<edges.size();i++) {
764 edges[i]->createRouteFromPath(nodes);
765 edges[i]->dummyNodes.clear();
766 edges[i]->path.clear();
767 }
768 }
769 void setEdgeLengths(double **D, vector<Edge*> & edges) {
770 for(unsigned i=0;i<edges.size();i++) {
771 Edge* e=edges[i];
772 e->idealLength=D[e->startNode][e->endNode];
773 }
774 }
775 double pathLength(Edge const * e, vector<Node*> const & nodes) {
776 double length=0;
777 vector<unsigned> const & path=e->path;
778 for(unsigned i=1;i<path.size();i++) {
779 Node *u=nodes[path[i-1]], *v=nodes[path[i]];
780 double dx=u->pos[0]-v->pos[0];
781 double dy=u->pos[1]-v->pos[1];
782 length+=sqrt(dx*dx+dy*dy);
783 }
784 return length;
785 }
786 double computeStressFromRoutes(double strength, vector<Edge*> & edges) {
787 double stress=0;
788 for(unsigned i=0;i<edges.size();i++) {
789 Edge* e=edges[i];
790 double d = e->idealLength;
791 double weight=1/(d*d);
792 double sqrtf=fabs(d-e->getRoute()->routeLength());
793 stress+=weight*sqrtf*sqrtf;
794 }
795 return strength*stress;
796 }
797}
798
@ LEFT
Definition LivarotDefs.h:87
@ RIGHT
Definition LivarotDefs.h:88
A cluster defines a hierarchical partitioning over the nodes which should be kept disjoint by the lay...
Definition cluster.h:51
std::vector< Cluster * > clusters
Definition cluster.h:116
std::valarray< double > hullY
Definition cluster.h:117
std::valarray< double > hullX
Definition cluster.h:117
Defines a cluster that will be treated as a convex boundary around the child nodes and clusters.
Definition cluster.h:359
bool check(const unsigned i) const
Definition commondefs.h:59
A separation constraint specifies a simple horizontal or vertical spacing constraint between 2 nodes ...
std::vector< Edge * > boundary
cola::ConvexCluster * colaCluster
void ypos(double x, std::vector< double > &ys) const
std::vector< unsigned > path
std::vector< unsigned > dummyNodes
bool isEnd(unsigned n) const
void nodePath(std::vector< Node * > &nodes, bool allActive)
sets up the path information for an edge, i.e.
void xpos(double y, std::vector< double > &xs) const
void setRoute(Route *r)
std::vector< unsigned > activePath
void createRouteFromPath(std::vector< Node * > const &nodes)
Route const * getRoute() const
double getMax(vpsc::Dim d) const
double getMin(vpsc::Dim d) const
std::valarray< double > dummyNodesY
Straightener(const double strength, const vpsc::Dim dim, std::vector< vpsc::Rectangle * > const &rs, cola::FixedList const &fixed, std::vector< Edge * > const &edges, vpsc::Variables const &vs, vpsc::Variables &lvs, vpsc::Constraints &lcs, std::valarray< double > &oldCoords, std::valarray< double > &oldG)
void computeForces(cola::SparseMap &H)
std::valarray< double > dummyNodesX
std::vector< Node * > nodes
std::valarray< double > g
double computeStress2(std::valarray< double > const &coords)
vpsc::Variables const & vs
std::valarray< double > coords
cola::FixedList const & fixed
std::vector< Edge * > const & edges
double computeStress(std::valarray< double > const &coords)
A constraint determines a minimum or exact spacing required between two Variable objects.
Definition constraint.h:45
A rectangle represents a fixed-size shape in the diagram that may be moved to prevent overlaps and sa...
Definition rectangle.h:78
void lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const
double getMaxX() const
Definition rectangle.h:108
bool inside(double x, double y) const
Definition rectangle.h:217
double getMaxY() const
Definition rectangle.h:109
void routeAround(double x1, double y1, double x2, double y2, std::vector< double > &xs, std::vector< double > &ys)
double getMinY() const
Definition rectangle.h:111
double getMinX() const
Definition rectangle.h:110
A variable is comprised of an ideal position, final position and a weight.
Definition variable.h:45
const double w
Definition conic-4.cpp:19
vector< vpsc::Rectangle * > rs
double c[8][4]
size_t v
GType type()
Returns the type used for storing an object of type T inside a value.
Definition value-utils.h:29
static bool pointOnLine(double px, double py, double ax, double ay, double bx, double by, double &tx)
void sortNeighbours(const vpsc::Dim dim, Node *v, Node *l, Node *r, const double conjpos, vector< Edge * > const &openEdges, vector< Node * > &L, vector< Node * > &nodes)
Search along scan line at conjpos for open edges to the left of v as far as l, and to the right of v ...
Event * createEvent(const vpsc::Dim dim, const EventType type, T *v, double border)
void generateClusterBoundaries(const vpsc::Dim dim, vector< straightener::Node * > &nodes, vector< straightener::Edge * > &edges, vector< vpsc::Rectangle * > const &rs, cola::Cluster const &clusterHierarchy, vector< straightener::Cluster * > &sclusters)
set up straightener clusters.
double computeStressFromRoutes(double strength, vector< Edge * > &edges)
void generateConstraints(const vpsc::Dim dim, vector< Node * > &nodes, vector< Edge * > const &edges, vector< cola::SeparationConstraint * > &cs, bool xSkipping=true)
Generates constraints to prevent node/edge and edge/edge intersections.
static double overlap(vpsc::Dim k, Node const *u, Node const *v)
std::set< Node *, CmpNodePos > NodeSet
double pathLength(Edge const *e, vector< Node * > const &nodes)
void setEdgeLengths(double **D, vector< Edge * > &edges)
static cola::SeparationConstraint * createConstraint(Node *u, Node *v, vpsc::Dim dim)
Dim
Indicates the x- or y-dimension.
Definition rectangle.h:41
@ HORIZONTAL
The x-dimension (0).
Definition rectangle.h:43
@ VERTICAL
The y-dimension (1).
Definition rectangle.h:47
std::vector< vpsc::Variable * > Variables
A vector of pointers to Variable objects.
std::vector< vpsc::Constraint * > Constraints
A vector of pointers to Constraint objects.
unsigned long weight
Definition quantize.cpp:37
unsigned long bs
Definition quantize.cpp:38
Edges edges(Path const &p, Crossings const &cr, unsigned ix)
Definition sanitize.cpp:36
void rerouteAround(vpsc::Rectangle *rect)
double routeLength() const
void nearest(double x, double y, double &xi, double &yi)
double border