diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:24:48 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:24:48 +0000 |
commit | cca66b9ec4e494c1d919bff0f71a820d8afab1fa (patch) | |
tree | 146f39ded1c938019e1ed42d30923c2ac9e86789 /src/3rdparty/adaptagrams/libcola/straightener.cpp | |
parent | Initial commit. (diff) | |
download | inkscape-upstream.tar.xz inkscape-upstream.zip |
Adding upstream version 1.2.2.upstream/1.2.2upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/3rdparty/adaptagrams/libcola/straightener.cpp')
-rw-r--r-- | src/3rdparty/adaptagrams/libcola/straightener.cpp | 798 |
1 files changed, 798 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libcola/straightener.cpp b/src/3rdparty/adaptagrams/libcola/straightener.cpp new file mode 100644 index 0000000..dc22d18 --- /dev/null +++ b/src/3rdparty/adaptagrams/libcola/straightener.cpp @@ -0,0 +1,798 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libcola - A library providing force-directed network layout using the + * stress-majorization method subject to separation constraints. + * + * Copyright (C) 2005-2008 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * See the file LICENSE.LGPL distributed with the library. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * Author(s): Tim Dwyer + * +*/ + +/* + * Functions to automatically generate constraints for the + * rectangular node overlap removal problem. + */ + +#include <set> +#include <list> +#include <cassert> +#include <iostream> +#include <cmath> + +#include "libvpsc/assertions.h" +#include "libcola/commondefs.h" +#include "libcola/cola.h" +#include "libcola/compound_constraints.h" +#include "libcola/straightener.h" + +//#define STRAIGHTENER_DEBUG 1 + +using std::list; +using std::make_pair; +using std::pair; +using std::set; +using std::vector; +using std::copy; + +namespace straightener { + + // is point p on line a-b? + static bool pointOnLine(double px,double py, double ax, double ay, double bx, double by, double& tx) { + double dx=bx-ax; + double dy=by-ay; + double ty=0; + if(fabs(dx)<0.0001&&fabs(dy)<0.0001) { + // runty line! + tx=px-ax; + ty=py-ay; + } else { + if(fabs(dx)<0.0001) { + //vertical line + if(fabs(px-ax)<0.01) { + tx=(py-ay)/dy; + } + } else { + tx=(px-ax)/dx; + } + if(fabs(dy)<0.0001) { + //horizontal line + if(fabs(py-ay)<0.01) { + ty=tx; + } + } else { + ty=(py-ay)/dy; + } + } + //printf(" tx=%f,ty=%f\n",tx,ty); + if(fabs(tx-ty)<0.001 && tx>=0 && tx<=1) { + return true; + } + return false; + } + void Route::rerouteAround(vpsc::Rectangle* rect) { + // the first and last points should not be inside this + // rectangle - note that we should not be routing around + // rectangles directly connected to this route + COLA_ASSERT(!rect->inside(xs[0],ys[0])); + COLA_ASSERT(!rect->inside(xs[n-1],ys[n-1])); + // first, we examine each point and if it is inside the rectangle, we + // project to the nearest edge of the rectangle + for(unsigned i=1;i<n-1;i++) { + double &x=xs[i], &y=ys[i]; + if(rect->inside(x,y)) { + enum ProjectSide {LEFT, BOTTOM, RIGHT, TOP}; + unsigned projectSide = LEFT; + double minDist = x - rect->getMinX(); + double dist = y - rect->getMinY(); + if(dist<minDist) { + projectSide = BOTTOM; + minDist = dist; + } + dist = rect->getMaxX() - x; + if(dist<minDist) { + projectSide = RIGHT; + minDist = dist; + } + dist = rect->getMaxY() - y; + if(dist<minDist) { + projectSide = TOP; + minDist = dist; + } + switch(projectSide) { + case LEFT: + x=rect->getMinX(); + break; + case BOTTOM: + y=rect->getMinY(); + break; + case RIGHT: + x=rect->getMaxX(); + break; + case TOP: + y=rect->getMaxY(); + break; + } + + } + } + // the new route is copied into rxs, rys. + vector<double> rxs, rys; + double prevX=xs[0], prevY=ys[0]; + rxs.push_back(prevX); + rys.push_back(prevY); + + // check each segment in turn to see if it intersects + // with the rectangle. + // If an intersecting segment is found: + // 1) the segment passes right through the rectangle + // - we insert new segments routed around the rectangle + // 2) the segment terminates inside the rectangle + // - we follow connected segments until we find the exit + // point, then we insert a route around the rectangle + // 3) the segment just touches one side + // + for(unsigned i=1;i<n;i++) { + // we have projected all points to the boundary already so we shouldn't find any inside + COLA_ASSERT(!rect->inside(xs[i],ys[i])); + vpsc::RectangleIntersections ri; + rect->lineIntersections(prevX,prevY, + xs[i],ys[i],ri); + if(ri.intersects) { + int count=ri.countIntersections(); + COLA_ASSERT(count>0); // can't be 0 because we have detected an intersection + COLA_ASSERT(count<4); // assumes no zero width or height rects which would be + // the only way for a line segment to touch all 4 sides at once + if(count==3) { // runs along one side + COLA_ASSERT(!rect->inside(xs[i],ys[i])); + } else if(count==2) { // passes right through + COLA_ASSERT(!rect->inside(xs[i],ys[i])); + double x1=0, y1=0, x2=0, y2=0; + ri.nearest(prevX, prevY, x1, y1); + ri.nearest(xs[i], ys[i], x2, y2); + rect->routeAround(x1, y1, x2, y2, rxs, rys); + } else if(count==1) { + // single intersection, earlier projection step ensures it is on the + // perimeter, so nothing to do + } + } + prevX=xs[i]; + prevY=ys[i]; + COLA_ASSERT(!rect->inside(prevX,prevY)); + rxs.push_back(prevX); + rys.push_back(prevY); + } + delete [] xs; + delete [] ys; + n=rxs.size(); + COLA_ASSERT(rys.size()==n); + xs = new double[n]; + ys = new double[n]; + copy(rxs.begin(),rxs.end(),xs); + copy(rys.begin(),rys.end(),ys); + } + /** + * sets up the path information for an edge, + * i.e. nodes are added to the path list in the order they appear on the + * edge, from startNode to endNode. + * activePath contains at least the first and last node in the edge. + * If allActive is true then + * activePath list is also set up with a subset of nodes from path, each of + * which is active (a start/end node or involved in a violated constraint). + */ + void Edge::nodePath(vector<Node*>& nodes, bool allActive = true) { + list<unsigned> ds(dummyNodes.size()); + copy(dummyNodes.begin(),dummyNodes.end(),ds.begin()); + //printf("Edge::nodePath: (%d,%d) dummyNodes:%d\n",startNode,endNode,ds.size()); + path.clear(); + activePath.clear(); + path.push_back(startNode); + activePath.push_back(0); + for(unsigned i=1;i<route->n;i++) { + //printf(" checking segment %d-%d\n",i-1,i); + set<pair<double,unsigned> > pntsOnLineSegment; + for(list<unsigned>::iterator j=ds.begin();j!=ds.end();) { + double px=nodes[*j]->pos[0]; + double py=nodes[*j]->pos[1]; + double ax=route->xs[i-1]; + double ay=route->ys[i-1]; + double bx=route->xs[i]; + double by=route->ys[i]; + double t=0; + list<unsigned>::iterator copyit=j++; + //printf(" px=%f, py=%f, ax=%f, ay=%f, bx=%f, by=%f\n",px,py,ax,ay,bx,by); + if(pointOnLine(px,py,ax,ay,bx,by,t)) { + //printf(" got node %d\n",*copyit); + pntsOnLineSegment.insert(make_pair(t,*copyit)); + ds.erase(copyit); + } + } + for(set<pair<double,unsigned> >::iterator j=pntsOnLineSegment.begin();j!=pntsOnLineSegment.end();j++) { + if(allActive && nodes[j->second]->active) { + activePath.push_back(path.size()); + } + path.push_back(j->second); + } + //printf("\n"); + } + activePath.push_back(path.size()); + path.push_back(endNode); + COLA_ASSERT(ds.empty()); + } + void Edge::createRouteFromPath(std::vector<Node *> const & nodes) { + Route* r=new Route(path.size()); +#ifdef STRAIGHTENER_DEBUG + //printf("Route:"); +#endif + for(unsigned i=0;i<path.size();i++) { + r->xs[i]=nodes[path[i]]->pos[0]; + r->ys[i]=nodes[path[i]]->pos[1]; +#ifdef STRAIGHTENER_DEBUG + //printf("(%f,%f)",r->xs[i],r->ys[i]); +#endif + } +#ifdef STRAIGHTENER_DEBUG + //printf("\n"); +#endif + setRoute(r); + } + + typedef enum {Open, Close} EventType; + struct Event { + EventType type; + Node *v; + Edge *e; + double pos; + Event(EventType t, Node *v, double p) : type(t),v(v),e(nullptr),pos(p) {}; + Event(EventType t, Edge *e, double p) : type(t),v(nullptr),e(e),pos(p) {}; + }; + /* + * the following relation defines a strict weak ordering over events, i.e.: + * irreflexivity: CompareEvents(e,e) == false + * antisymetry: CompareEvents(a,b) => !CompareEvents(b,a) + * transitivity: CompareEvents(a,b) && CompareEvents(b,c) => CompareEvents(a,c) + * transitivity of equivalence: + * !CompareEvents(a,b) && !CompareEvents(b,a) && !CompareEvents(b,c) && !CompareEvents(c,b) + * => !CompareEvents(a,c) && !CompareEvents(c,a) + */ + struct CompareEvents { + bool operator() (Event *const &a, Event *const &b) const { + if(a->pos < b->pos) { + return true; + } else if(a->pos==b->pos) { + // All opens should come before closes when at the same position + if(a->type==Open && b->type==Close) return true; + if(a->type==Close && b->type==Open) return false; + // Edge opens at the same position as node opens, edge comes first + if(a->type==Open && b->type==Open) { + if(a->e && b->v) return true; + if(b->e && a->v) return false; + } + // Edge closes at the same position as node closes, node comes first + if(a->type==Close && b->type==Close) { + if(a->e && b->v) return false; + if(b->e && a->v) return true; + } + } + return false; + } + }; + + /** + * Search along scan line at conjpos for open edges to the left of v + * as far as l, and to the right of v as far as r. + * The result is a list of nodes L (including l,v,r and a bunch of + * new dummy nodes for each edge intersected - excluding edges + * connected to v). + * The new dummy nodes are also added to the end of the canonical + * node list: nodes. + */ + 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) { + double minpos=-DBL_MAX, maxpos=DBL_MAX; + if(l!=nullptr) { + L.push_back(l); + minpos=l->scanpos; + } + typedef pair<double,Edge*> PosEdgePair; + set<PosEdgePair> sortedEdges; + for(unsigned i=0;i<openEdges.size();i++) { + Edge *e=openEdges[i]; + vector<double> bs; + if(dim==vpsc::HORIZONTAL) { + e->xpos(conjpos,bs); + } else { + e->ypos(conjpos,bs); + } + //std::cerr << "edge(intersections="<<bs.size()<<":("<<e->startNode<<","<<e->endNode<<"))"<<std::endl; + for(vector<double>::iterator it=bs.begin();it!=bs.end();it++) { + sortedEdges.insert(make_pair(*it,e)); + } + } + for(set<PosEdgePair>::iterator i=sortedEdges.begin();i!=sortedEdges.end();i++) { + double pos=i->first; + if(pos < minpos) continue; + if(pos > v->scanpos) break; + // if edge is connected (start or end) to v then skip + // need to record start and end positions of edge segment! + Edge* e=i->second; + if(e->startNode==v->id||e->endNode==v->id) continue; + //if(l!=nullptr&&(e->startNode==l->id||e->endNode==l->id)) continue; + //cerr << "edge("<<e->startNode<<","<<e->endNode<<",pts="<<e->pts<<")"<<endl; + // here, we probably want to search for existing dummy + // nodes associated with the same edge within some + // range of (pos,conjpos), rather than creating new ones. + // Would require some sort of quad-tree structure + Node* d=dim==vpsc::HORIZONTAL? + new Node(nodes.size(),pos,conjpos,e): + new Node(nodes.size(),conjpos,pos,e); + L.push_back(d); + nodes.push_back(d); + } + L.push_back(v); + + if(r!=nullptr) { + maxpos=r->scanpos; + } + for(set<PosEdgePair>::iterator i=sortedEdges.begin();i!=sortedEdges.end();i++) { + if(i->first < v->scanpos) continue; + if(i->first > maxpos) break; + double pos=i->first; + // if edge is connected (start or end) to v then skip + // need to record start and end positions of edge segment! + Edge* e=i->second; + if(e->startNode==v->id||e->endNode==v->id) continue; + //if(r!=nullptr&&(e->startNode==r->id||e->endNode==r->id)) continue; + //cerr << "edge("<<e->startNode<<","<<e->endNode<<",pts="<<e->pts<<")"<<endl; + Node* d=dim==vpsc::HORIZONTAL? + new Node(nodes.size(),pos,conjpos,e): + new Node(nodes.size(),conjpos,pos,e); + L.push_back(d); + nodes.push_back(d); + } + if(r!=nullptr) { + L.push_back(r); + } + } + static double overlap(vpsc::Dim k, Node const *u, Node const *v) { + if (u->pos[k] <= v->pos[k] && v->getMin(k) < u->getMax(k)) + return u->getMax(k) - v->getMin(k); + if (v->pos[k] <= u->pos[k] && u->getMin(k) < v->getMax(k)) + return v->getMax(k) - u->getMin(k); + return 0; + } + + static cola::SeparationConstraint* createConstraint( + Node* u, Node* v, vpsc::Dim dim) { + double g=u->length[dim]+v->length[dim]; + g/=2; + double sep=v->pos[dim]-u->pos[dim]; + if(sep < g) { + u->active = true; + v->active = true; + } + //cerr << "Constraint: "<< u->id << "+"<<g<<"<="<<v->id<<endl; + return new cola::SeparationConstraint(dim, u->id, v->id, g); + } + + template <typename T> + Event* createEvent( + const vpsc::Dim dim, + const EventType type, + T *v, + double border) { + double pos = (type==Open) ? v->getMin((vpsc::Dim)!dim)-border + : v->getMax((vpsc::Dim)!dim)+border ; + return new Event(type,v,pos); + } + /** + * Generates constraints to prevent node/edge and edge/edge intersections. + * Can be invoked to generate either horizontal or vertical constraints + * depending on dim parameter. + * For horizontal constraints, a vertical scan (from top to bottom) is + * conducted, looking for node/edge boundaries, and then searching along + * the horizontal limit of that boundary for intersections with other + * nodes/edges. + */ + void generateConstraints( + const vpsc::Dim dim, + vector<Node*> & nodes, + vector<Edge*> const & edges, + vector<cola::SeparationConstraint*>& cs, + bool xSkipping = true) { + vector<Event*> events; + double nodeFudge=-0.01, edgeFudge=0; +#ifdef STRAIGHTENER_DEBUG + cout << (dim==vpsc::HORIZONTAL + ?"scanning top to bottom..." + :"scanning left to right...") + << endl; +#endif + for(unsigned i=0;i<nodes.size();i++) { + Node *v=nodes[i]; + if(v->scan) { + v->scanpos=v->pos[dim]; + events.push_back(createEvent(dim,Open,v,nodeFudge)); + events.push_back(createEvent(dim,Close,v,nodeFudge)); + } + } + for(unsigned i=0;i<edges.size();i++) { + Edge *e=edges[i]; + events.push_back(createEvent(dim,Open,e,edgeFudge)); + events.push_back(createEvent(dim,Close,e,edgeFudge)); + } + std::sort(events.begin(),events.end(),CompareEvents()); + + NodeSet openNodes; + vector<Edge*> openEdges; + // scan opening and closing events in order + for(unsigned i=0;i<events.size();i++) { + Event *e=events[i]; + Node *v=e->v; + if(v!=nullptr) { + v->open = true; +#ifdef STRAIGHTENER_DEBUG + 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()); +#endif + Node *l=nullptr, *r=nullptr; + if(!openNodes.empty()) { + // it points to the first node to the right of v + NodeSet::iterator it=openNodes.lower_bound(v); + // step left to find the first node to the left of v + while(it--!=openNodes.begin()) { + if(!xSkipping + || dim!=vpsc::HORIZONTAL + || overlap(vpsc::HORIZONTAL,*it,v) <= 0 + || overlap(vpsc::HORIZONTAL,*it,v) <= overlap(vpsc::VERTICAL,*it,v)) { + l=*it; + break; + } +#ifdef STRAIGHTENER_DEBUG + printf("l=%d\n",l->id); +#endif + } + it=openNodes.upper_bound(v); + while(it!=openNodes.end()) { + if(!xSkipping + || dim!=vpsc::HORIZONTAL + || overlap(vpsc::HORIZONTAL,v,*it) <= 0 + || overlap(vpsc::HORIZONTAL,v,*it) <= overlap(vpsc::VERTICAL,v,*it)) { + r=*it; + break; + } + it++; + } + } + vector<Node*> L; + sortNeighbours(dim,v,l,r,e->pos,openEdges,L,nodes); +#ifdef STRAIGHTENER_DEBUG + printf("L=["); + for(unsigned i=0;i<L.size();i++) { + printf("%d ",L[i]->id); + } + printf("]\n"); +#endif + // for each dummy node w in L: + // if w left of v create constraints l<w, w<v + // if w right of v create constraints v<w, w<r + for(vector<Node*>::iterator i=L.begin();i!=L.end();i++) { + Node* w=*i; + if(w->dummy) { + // node is on an edge + Edge *edge=w->edge; + if(w->pos[dim]<v->pos[dim]) { // w left of v + if(l!=nullptr&&!edge->isEnd(l->id)) { + cs.push_back(createConstraint(l,w,dim)); + } + if(!edge->isEnd(v->id)) { + cs.push_back(createConstraint(w,v,dim)); + } + } else { // w right of v + if(!edge->isEnd(v->id)) { + cs.push_back(createConstraint(v,w,dim)); + } + if(r!=nullptr&&!edge->isEnd(r->id)) { + cs.push_back(createConstraint(w,r,dim)); + } + } + } + } + if(e->type==Close) { + if(l!=nullptr) cs.push_back(createConstraint(l,v,dim)); + if(r!=nullptr) cs.push_back(createConstraint(v,r,dim)); + } + } + if(e->type==Open) { + if(v!=nullptr) { + openNodes.insert(v); + } else { +#ifdef STRAIGHTENER_DEBUG + printf("EdgeOpen@%f,eid=%d,(u,v)=(%d,%d)\n", e->pos,e->e->id,e->e->startNode,e->e->endNode); +#endif + e->e->openInd=openEdges.size(); + openEdges.push_back(e->e); + } + } else { + // Close + if(v!=nullptr) { + openNodes.erase(v); + v->open=false; + } else { +#ifdef STRAIGHTENER_DEBUG + printf("EdgeClose@%f,eid=%d,(u,v)=(%d,%d)\n", e->pos,e->e->id,e->e->startNode,e->e->endNode); +#endif + unsigned i=e->e->openInd; + COLA_ASSERT(openEdges.size()>0); + openEdges[i]=openEdges[openEdges.size()-1]; + openEdges[i]->openInd=i; + openEdges.resize(openEdges.size()-1); + } + } + delete e; + } + } + /** + * set up straightener clusters. + * For each cola::cluster c: + * create a straightener::cluster sc + * set each node in c to belong to sc + * set scanpos based on avg pos in scan dir + * create a chain of dummy nodes for cluster boundary + */ + 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) { + sclusters.clear(); + for(vector<cola::Cluster*>::const_iterator i + =clusterHierarchy.clusters.begin(); + i!=clusterHierarchy.clusters.end(); i++) { + if(cola::ConvexCluster* c=dynamic_cast<cola::ConvexCluster*>(*i)) { + straightener::Cluster* sc=new straightener::Cluster(c); + // compute scanpos based on average position in scan direction + sc->scanpos=0; + for(set<unsigned>::iterator it= c->nodes.begin(); + it != c->nodes.end(); ++it) { + straightener::Node* u = nodes[*it]; + sc->scanpos+=u->pos[dim]; + u->cluster = sc; + } + sc->scanpos/=c->nodes.size(); + sclusters.push_back(sc); + c->computeBoundary(rs); + // create a chain of dummy nodes for the boundary + Node* first = new Node(nodes.size(),c->hullX[0],c->hullY[0]); + nodes.push_back(first); + Node* u = first; + unsigned i=1; + for(;i<c->hullX.size();i++) { + Node* v = new Node(nodes.size(),c->hullX[i],c->hullY[i]); + nodes.push_back(v); + Edge* e = new Edge(edges.size(),u->id,v->id, + c->hullX[i-1],c->hullY[i-1],c->hullX[i],c->hullY[i]); + edges.push_back(e); + sc->boundary.push_back(e); + u=v; + } + edges.push_back( + new Edge(edges.size(),u->id,first->id, + c->hullX[i-1],c->hullY[i-1],c->hullX[0],c->hullY[0])); + } + } + } + + void Cluster::updateActualBoundary() + { + unsigned n=0; + for(std::vector<Edge*>::const_iterator e=boundary.begin(); + e!=boundary.end();e++) { + n+=(*e)->getRoute()->n; + } + colaCluster->hullX.resize(n); + colaCluster->hullY.resize(n); + unsigned i=0; + for(std::vector<Edge*>::const_iterator e=boundary.begin(); + e!=boundary.end();e++) { + Route const * r=(*e)->getRoute(); + for(unsigned j=0;j<r->n;j++) { + colaCluster->hullX[i]=r->xs[j]; + colaCluster->hullY[i++]=r->ys[j]; + } + } + } + Straightener::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) + : strength(strength), + dim(dim), + fixed(fixed), + edges(edges), + vs(vs), + lvs(lvs) + { + unsigned n=rs.size(); + for (unsigned i=0;i<n;i++) { + nodes.push_back(new straightener::Node(i,rs[i])); + } + vector<cola::SeparationConstraint*> cs; + straightener::generateConstraints(dim,nodes,edges,cs); + // after generateConstraints we have new dummy nodes at the end of snodes and + // constraints in cs + // need to create variables for dummy nodes in lvs and constraints in lcs + N=nodes.size(); + g.resize(N); + coords.resize(N); + for(unsigned i=0;i<n;i++) { + g[i]=oldG[i]; + coords[i]=oldCoords[i]; + } + for (unsigned i=n;i<N;i++) { + double desiredPos = nodes[i]->pos[dim]; + lvs.push_back(new vpsc::Variable(i,desiredPos,1)); + g[i]=0; + coords[i]=desiredPos; + } + for (vector<cola::SeparationConstraint*>::iterator i=cs.begin();i!=cs.end();i++) { + unsigned lv=(*i)->left(); + unsigned rv=(*i)->right(); + double gap=(*i)->gap; + vpsc::Variable* l = lv<n?vs[lv]:lvs[lv-n]; + vpsc::Variable* r = rv<n?vs[rv]:lvs[rv-n]; + lcs.push_back(new vpsc::Constraint(l,r,gap)); + } + for(unsigned i=0;i<edges.size();i++) { + edges[i]->nodePath(nodes,false); + } + for_each(cs.begin(),cs.end(),cola::delete_object()); + } + Straightener::~Straightener() { + for_each(nodes.begin(),nodes.end(),cola::delete_object()); + } + void Straightener::computeForces(cola::SparseMap &H) { + // hessian matrix: + // diagonal: sum dy2/l^3 + // off-diag: -dy2/l^3 + for(unsigned i=0;i<edges.size();i++) { + //printf("Straightening path:\n"); + //edges[i]->print(); + vector<unsigned>& path=edges[i]->path; + COLA_ASSERT(path.size()>0); + for(unsigned j=1;j<path.size();j++) { + unsigned u=path[j-1], v=path[j]; + double x1=nodes[u]->pos[0], x2=nodes[v]->pos[0], + y1=nodes[u]->pos[1], y2=nodes[v]->pos[1]; + double dx=x1-x2, dy=y1-y2; + double dx2=dx*dx, dy2=dy*dy; + double l=sqrt(dx2+dy2); + if(l<0.0000001) continue; + double f=dim==vpsc::HORIZONTAL?dx:dy; + f*=strength/l; + if(!fixed.check(u)) { g[u]+=f; } + if(!fixed.check(v)) { g[v]-=f; } + double h=dim==vpsc::HORIZONTAL?dy2:dx2; + h*=strength/(l*l*l); + H(u,u)+=h; + H(v,v)+=h; + H(u,v)-=h; + H(v,u)-=h; + } + } + } + double Straightener::computeStress(std::valarray<double> const &coords) { + double stress=0; + for(unsigned i=0;i<edges.size();i++) { + vector<unsigned>& path=edges[i]->path; + COLA_ASSERT(path.size()>0); + for(unsigned j=1;j<path.size();j++) { + unsigned u=path[j-1], v=path[j]; + double x1,x2,y1,y2; + if(dim==vpsc::HORIZONTAL) { + x1=coords[u]; + x2=coords[v]; + y1=nodes[u]->pos[1]; + y2=nodes[v]->pos[1]; + } else { + x1=nodes[u]->pos[0]; + x2=nodes[v]->pos[0]; + y1=coords[u]; + y2=coords[v]; + } + double dx=x1-x2, dy=y1-y2; + double dx2=dx*dx, dy2=dy*dy; + double l=sqrt(dx2+dy2); + stress+=l; + } + } + return strength*stress; + } + double Straightener::computeStress2(std::valarray<double> const &coords) + { + COLA_UNUSED(coords); + + double stress=0; + for(unsigned i=0;i<edges.size();i++) { + double d = edges[i]->idealLength; + double weight=1/(d*d); + //printf("pathLength=%f\n",pathLength(edges[i],nodes)); + double sqrtf=fabs(d-pathLength(edges[i],nodes)); + stress+=weight*sqrtf*sqrtf; + } + return strength*stress; + } + void Straightener::updateNodePositions() { + // real nodes + for (unsigned i=0;i<N;i++) { + Node *n=nodes[i]; + n->pos[dim]=coords[i]; + } + // dummy bend nodes + //printf("got %d dummy nodes\n", (int) lvs.size()); + dummyNodesX.resize(lvs.size()); + dummyNodesY.resize(lvs.size()); + for (unsigned i=0;i<lvs.size();i++) { + COLA_ASSERT(i+vs.size() < nodes.size()); + Node *n=nodes[i+vs.size()]; + dummyNodesX[i]=n->pos[0]; + dummyNodesY[i]=n->pos[1]; + } + } + void Straightener::finalizeRoutes() { + for(unsigned i=0;i<edges.size();i++) { + edges[i]->createRouteFromPath(nodes); + edges[i]->dummyNodes.clear(); + edges[i]->path.clear(); + } + } + void setEdgeLengths(double **D, vector<Edge*> & edges) { + for(unsigned i=0;i<edges.size();i++) { + Edge* e=edges[i]; + e->idealLength=D[e->startNode][e->endNode]; + } + } + double pathLength(Edge const * e, vector<Node*> const & nodes) { + double length=0; + vector<unsigned> const & path=e->path; + for(unsigned i=1;i<path.size();i++) { + Node *u=nodes[path[i-1]], *v=nodes[path[i]]; + double dx=u->pos[0]-v->pos[0]; + double dy=u->pos[1]-v->pos[1]; + length+=sqrt(dx*dx+dy*dy); + } + return length; + } + double computeStressFromRoutes(double strength, vector<Edge*> & edges) { + double stress=0; + for(unsigned i=0;i<edges.size();i++) { + Edge* e=edges[i]; + double d = e->idealLength; + double weight=1/(d*d); + double sqrtf=fabs(d-e->getRoute()->routeLength()); + stress+=weight*sqrtf*sqrtf; + } + return strength*stress; + } +} + |