52 static bool pointOnLine(
double px,
double py,
double ax,
double ay,
double bx,
double by,
double& tx) {
56 if(fabs(dx)<0.0001&&fabs(dy)<0.0001) {
63 if(fabs(px-ax)<0.01) {
71 if(fabs(py-ay)<0.01) {
79 if(fabs(tx-ty)<0.001 && tx>=0 && tx<=1) {
92 for(
unsigned i=1;i<
n-1;i++) {
93 double &x=
xs[i], &y=
ys[i];
95 enum ProjectSide {
LEFT, BOTTOM,
RIGHT, TOP};
96 unsigned projectSide =
LEFT;
97 double minDist = x - rect->
getMinX();
98 double dist = y - rect->
getMinY();
100 projectSide = BOTTOM;
113 switch(projectSide) {
131 vector<double> rxs, rys;
132 double prevX=
xs[0], prevY=
ys[0];
133 rxs.push_back(prevX);
134 rys.push_back(prevY);
146 for(
unsigned i=1;i<
n;i++) {
154 COLA_ASSERT(count>0);
155 COLA_ASSERT(count<4);
159 }
else if(count==2) {
161 double x1=0, y1=0, x2=0, y2=0;
162 ri.
nearest(prevX, prevY, x1, y1);
165 }
else if(count==1) {
172 COLA_ASSERT(!rect->
inside(prevX,prevY));
173 rxs.push_back(prevX);
174 rys.push_back(prevY);
179 COLA_ASSERT(rys.size()==
n);
182 copy(rxs.begin(),rxs.end(),
xs);
183 copy(rys.begin(),rys.end(),
ys);
202 for(
unsigned i=1;i<
route->
n;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];
213 list<unsigned>::iterator copyit=j++;
217 pntsOnLineSegment.insert(make_pair(t,*copyit));
221 for(
set<pair<double,unsigned> >::iterator j=pntsOnLineSegment.begin();j!=pntsOnLineSegment.end();j++) {
222 if(allActive && nodes[j->second]->active) {
225 path.push_back(j->second);
231 COLA_ASSERT(ds.empty());
235#ifdef STRAIGHTENER_DEBUG
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
245#ifdef STRAIGHTENER_DEBUG
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) {};
269 struct CompareEvents {
270 bool operator() (Event *
const &a, Event *
const &b)
const {
271 if(a->pos < b->pos) {
273 }
else if(a->pos==b->pos) {
275 if(a->type==
Open && b->type==
Close)
return true;
276 if(a->type==
Close && b->type==
Open)
return false;
278 if(a->type==
Open && b->type==
Open) {
279 if(a->e && b->v)
return true;
280 if(b->e && a->v)
return false;
284 if(a->e && b->v)
return false;
285 if(b->e && a->v)
return true;
302 const double conjpos, vector<Edge*>
const & openEdges,
303 vector<Node *>& L,vector<Node *>& nodes) {
304 double minpos=-DBL_MAX, maxpos=DBL_MAX;
309 typedef pair<double,Edge*> PosEdgePair;
310 set<PosEdgePair> sortedEdges;
311 for(
unsigned i=0;i<openEdges.size();i++) {
312 Edge *e=openEdges[i];
320 for(vector<double>::iterator it=
bs.begin();it!=
bs.end();it++) {
321 sortedEdges.insert(make_pair(*it,e));
324 for(set<PosEdgePair>::iterator i=sortedEdges.begin();i!=sortedEdges.end();i++) {
326 if(pos < minpos)
continue;
327 if(pos > v->scanpos)
break;
339 new Node(nodes.size(),pos,conjpos,e):
340 new Node(nodes.size(),conjpos,pos,e);
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;
360 new Node(nodes.size(),pos,conjpos,e):
361 new Node(nodes.size(),conjpos,pos,e);
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);
379 double g=u->
length[dim]+v->length[dim];
381 double sep=v->pos[dim]-u->
pos[dim];
390 template <
typename T>
398 return new Event(type,v,pos);
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
419 ?
"scanning top to bottom..."
420 :
"scanning left to right...")
423 for(
unsigned i=0;i<nodes.size();i++) {
426 v->scanpos=v->pos[dim];
431 for(
unsigned i=0;i<
edges.size();i++) {
436 std::sort(events.begin(),events.end(),CompareEvents());
439 vector<Edge*> openEdges;
441 for(
unsigned i=0;i<events.size();i++) {
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());
449 Node *l=
nullptr, *r=
nullptr;
450 if(!openNodes.empty()) {
452 NodeSet::iterator it=openNodes.lower_bound(v);
454 while(it--!=openNodes.begin()) {
462#ifdef STRAIGHTENER_DEBUG
463 printf(
"l=%d\n",l->
id);
466 it=openNodes.upper_bound(v);
467 while(it!=openNodes.end()) {
480#ifdef STRAIGHTENER_DEBUG
482 for(
unsigned i=0;i<L.size();i++) {
483 printf(
"%d ",L[i]->
id);
490 for(vector<Node*>::iterator i=L.begin();i!=L.end();i++) {
495 if(
w->pos[dim]<v->pos[dim]) {
496 if(l!=
nullptr&&!edge->
isEnd(l->
id)) {
499 if(!edge->
isEnd(v->id)) {
503 if(!edge->
isEnd(v->id)) {
506 if(r!=
nullptr&&!edge->
isEnd(r->id)) {
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);
524 e->e->openInd=openEdges.size();
525 openEdges.push_back(e->e);
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);
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);
556 vector<straightener::Node*> & nodes,
557 vector<straightener::Edge*> &
edges,
558 vector<vpsc::Rectangle*>
const &
rs,
560 vector<straightener::Cluster*>& sclusters) {
562 for(vector<cola::Cluster*>::const_iterator i
564 i!=clusterHierarchy.
clusters.end(); i++) {
569 for(set<unsigned>::iterator it=
c->nodes.begin();
570 it !=
c->nodes.end(); ++it) {
576 sclusters.push_back(sc);
577 c->computeBoundary(
rs);
579 Node* first =
new Node(nodes.size(),
c->hullX[0],
c->hullY[0]);
580 nodes.push_back(first);
583 for(;i<
c->hullX.size();i++) {
584 Node* v =
new Node(nodes.size(),
c->hullX[i],
c->hullY[i]);
587 c->hullX[i-1],
c->hullY[i-1],
c->hullX[i],
c->hullY[i]);
594 c->hullX[i-1],
c->hullY[i-1],
c->hullX[0],
c->hullY[0]));
602 for(std::vector<Edge*>::const_iterator e=
boundary.begin();
604 n+=(*e)->getRoute()->n;
609 for(std::vector<Edge*>::const_iterator e=
boundary.begin();
611 Route const * r=(*e)->getRoute();
612 for(
unsigned j=0;j<r->
n;j++) {
619 const double strength,
621 std::vector<vpsc::Rectangle*>
const &
rs,
623 std::vector<Edge*>
const &
edges,
627 std::valarray<double> &oldCoords,
628 std::valarray<double> &oldG)
629 : strength(strength),
636 unsigned n=
rs.size();
637 for (
unsigned i=0;i<n;i++) {
640 vector<cola::SeparationConstraint*> cs;
648 for(
unsigned i=0;i<n;i++) {
652 for (
unsigned i=n;i<
N;i++) {
653 double desiredPos =
nodes[i]->pos[
dim];
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;
666 for(
unsigned i=0;i<
edges.size();i++) {
678 for(
unsigned i=0;i<
edges.size();i++) {
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],
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;
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];
723 double dx=x1-x2, dy=y1-y2;
724 double dx2=dx*dx, dy2=dy*dy;
725 double l=sqrt(dx2+dy2);
736 for(
unsigned i=0;i<
edges.size();i++) {
737 double d =
edges[i]->idealLength;
741 stress+=
weight*sqrtf*sqrtf;
747 for (
unsigned i=0;i<
N;i++) {
755 for (
unsigned i=0;i<
lvs.size();i++) {
756 COLA_ASSERT(i+
vs.size() <
nodes.size());
763 for(
unsigned i=0;i<
edges.size();i++) {
765 edges[i]->dummyNodes.clear();
766 edges[i]->path.clear();
770 for(
unsigned i=0;i<
edges.size();i++) {
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);
788 for(
unsigned i=0;i<
edges.size();i++) {
793 stress+=
weight*sqrtf*sqrtf;
795 return strength*stress;
A cluster defines a hierarchical partitioning over the nodes which should be kept disjoint by the lay...
std::vector< Cluster * > clusters
std::valarray< double > hullY
std::valarray< double > hullX
Defines a cluster that will be treated as a convex boundary around the child nodes and clusters.
bool check(const unsigned i) const
A separation constraint specifies a simple horizontal or vertical spacing constraint between 2 nodes ...
std::vector< Edge * > boundary
cola::ConvexCluster * colaCluster
void updateActualBoundary()
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
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)
void updateNodePositions()
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.
A rectangle represents a fixed-size shape in the diagram that may be moved to prevent overlaps and sa...
void lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const
bool inside(double x, double y) const
void routeAround(double x1, double y1, double x2, double y2, std::vector< double > &xs, std::vector< double > &ys)
A variable is comprised of an ideal position, final position and a weight.
vector< vpsc::Rectangle * > rs
GType type()
Returns the type used for storing an object of type T inside a value.
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.
@ HORIZONTAL
The x-dimension (0).
@ VERTICAL
The y-dimension (1).
std::vector< vpsc::Variable * > Variables
A vector of pointers to Variable objects.
std::vector< vpsc::Constraint * > Constraints
A vector of pointers to Constraint objects.
Edges edges(Path const &p, Crossings const &cr, unsigned ix)
void rerouteAround(vpsc::Rectangle *rect)
double routeLength() const
void nearest(double x, double y, double &xi, double &yi)