From 05674ae147c14ec4ec74b2b6771e04e0c82209b8 Mon Sep 17 00:00:00 2001 From: Emden Gansner Date: Tue, 25 Sep 2012 16:59:44 -0400 Subject: [PATCH] Use splines=curved for curved edges; move the code to routespl.c in common; make sure edge midpoint function works for curved edges; allow curved edge in dot --- lib/common/const.h | 11 +-- lib/common/render.h | 1 + lib/common/routespl.c | 135 +++++++++++++++++++++++++++++++++ lib/common/splines.c | 3 +- lib/common/utils.c | 4 +- lib/dotgen/dotsplines.c | 20 +++-- lib/neatogen/multispline.c | 2 +- lib/neatogen/neatoprocs.h | 1 - lib/neatogen/neatosplines.c | 144 +----------------------------------- 9 files changed, 167 insertions(+), 154 deletions(-) diff --git a/lib/common/const.h b/lib/common/const.h index 9935cae9b..62a8eeb58 100644 --- a/lib/common/const.h +++ b/lib/common/const.h @@ -254,7 +254,7 @@ #define LT_RECD (2 << 1) /* Flags stored in GD_flags - * Bit(s): 0 HAS_CLUSt_EDGE + * Bit(s): 0 HAS_CLUST_EDGE * 1-3 ET_ * 4 NEW_RANK */ @@ -262,10 +262,11 @@ /* edge types */ #define ET_NONE (0 << 1) #define ET_LINE (1 << 1) -#define ET_PLINE (2 << 1) -#define ET_ORTHO (3 << 1) -#define ET_SPLINE (4 << 1) -#define ET_COMPOUND (5 << 1) +#define ET_CURVED (2 << 1) +#define ET_PLINE (3 << 1) +#define ET_ORTHO (4 << 1) +#define ET_SPLINE (5 << 1) +#define ET_COMPOUND (6 << 1) /* New ranking is used */ #define NEW_RANK (1 << 4) diff --git a/lib/common/render.h b/lib/common/render.h index ab83308b7..b04d8d77c 100644 --- a/lib/common/render.h +++ b/lib/common/render.h @@ -86,6 +86,7 @@ extern "C" { pointf p), pointf * sp, boolean left_inside); extern shape_desc *bind_shape(char *name, node_t *); + extern void makeStraightEdge(graph_t * g, edge_t * e, int edgetype, splineInfo * info); extern void clip_and_install(edge_t * fe, node_t * hn, pointf * ps, int pn, splineInfo * info); extern char* charsetToStr (int c); diff --git a/lib/common/routespl.c b/lib/common/routespl.c index 70e19390c..ec41a8ed5 100644 --- a/lib/common/routespl.c +++ b/lib/common/routespl.c @@ -879,3 +879,138 @@ static void printpath(path * pp) pp->end.constrained ? "constrained" : "not constrained"); } +static pointf get_centroid(Agraph_t *g) +{ + int cnt = 0; + static pointf sum = {0.0, 0.0}; + static Agraph_t *save; + Agnode_t *n; + + sum.x = (GD_bb(g).LL.x + GD_bb(g).UR.x) / 2.0; + sum.y = (GD_bb(g).LL.y + GD_bb(g).UR.y) / 2.0; + return sum; + + if (save == g) return sum; + save = g; + for (n = agfstnode(g); n; n = agnxtnode(g,n)) { + sum.x += ND_pos(n)[0]; + sum.y += ND_pos(n)[1]; + cnt++; + } + sum.x = sum.x / cnt; + sum.y = sum.y / cnt; + return sum; +} + +static void bend(pointf spl[4], pointf centroid) +{ + pointf midpt,a; + double r; + double dist,dx,dy; + + midpt.x = (spl[0].x + spl[3].x)/2.0; + midpt.y = (spl[0].y + spl[3].y)/2.0; + dx = (spl[3].x - spl[0].x); + dy = (spl[3].y - spl[0].y); + dist = sqrt(dx*dx + dy*dy); + r = dist/5.0; + { + double vX = centroid.x - midpt.x; + double vY = centroid.y - midpt.y; + double magV = sqrt(vX*vX + vY*vY); + a.x = midpt.x - vX / magV * r; /* + would be closest point */ + a.y = midpt.y - vY / magV * r; + } + /* this can be improved */ + spl[1].x = spl[2].x = a.x; + spl[1].y = spl[2].y = a.y; +} + +/* makeStraightEdge: + * + * FIX: handle ports on boundary? + */ +void +makeStraightEdge(graph_t * g, edge_t * e, int et, splineInfo* sinfo) +{ + pointf dumb[4]; + node_t *n = agtail(e); + node_t *head = aghead(e); + int e_cnt = ED_count(e); + int curved = (et == ET_CURVED); + pointf perp; + pointf del; + edge_t *e0; + int i, j, xstep, dx; + double l_perp; + pointf dumber[4]; + pointf p, q; + + p = dumb[1] = dumb[0] = add_pointf(ND_coord(n), ED_tail_port(e).p); + q = dumb[2] = dumb[3] = add_pointf(ND_coord(head), ED_head_port(e).p); + if ((e_cnt == 1) || Concentrate) { + if (curved) bend(dumb,get_centroid(g)); + clip_and_install(e, aghead(e), dumb, 4, sinfo); + addEdgeLabels(g, e, p, q); + return; + } + + e0 = e; + if (APPROXEQPT(dumb[0], dumb[3], MILLIPOINT)) { + /* degenerate case */ + dumb[1] = dumb[0]; + dumb[2] = dumb[3]; + del.x = 0; + del.y = 0; + } + else { + perp.x = dumb[0].y - dumb[3].y; + perp.y = dumb[3].x - dumb[0].x; + l_perp = LEN(perp.x, perp.y); + xstep = GD_nodesep(g->root); + dx = xstep * (e_cnt - 1) / 2; + dumb[1].x = dumb[0].x + (dx * perp.x) / l_perp; + dumb[1].y = dumb[0].y + (dx * perp.y) / l_perp; + dumb[2].x = dumb[3].x + (dx * perp.x) / l_perp; + dumb[2].y = dumb[3].y + (dx * perp.y) / l_perp; + del.x = -xstep * perp.x / l_perp; + del.y = -xstep * perp.y / l_perp; + } + + for (i = 0; i < e_cnt; i++) { + if (aghead(e0) == head) { + p = dumb[0]; + q = dumb[3]; + for (j = 0; j < 4; j++) { + dumber[j] = dumb[j]; + } + } else { + p = dumb[3]; + q = dumb[0]; + for (j = 0; j < 4; j++) { + dumber[3 - j] = dumb[j]; + } + } + if (et == ET_PLINE) { + Ppoint_t pts[4]; + Ppolyline_t spl, line; + + line.pn = 4; + line.ps = pts; + for (j=0; j < 4; j++) { + pts[j] = dumber[j]; + } + make_polyline (line, &spl); + clip_and_install(e0, aghead(e0), spl.ps, spl.pn, sinfo); + } + else + clip_and_install(e0, aghead(e0), dumber, 4, sinfo); + + addEdgeLabels(g, e0, p, q); + e0 = ED_to_virt(e0); + dumb[1].x += del.x; + dumb[1].y += del.y; + dumb[2].x += del.x; + dumb[2].y += del.y; + } +} diff --git a/lib/common/splines.c b/lib/common/splines.c index 996375a50..d08f39af1 100644 --- a/lib/common/splines.c +++ b/lib/common/splines.c @@ -1329,7 +1329,7 @@ edgeMidpoint (graph_t* g, edge_t * e) if (APPROXEQPT(p, q, MILLIPOINT)) { /* degenerate spline */ spf = p; } - else if (et == ET_SPLINE) { + else if ((et == ET_SPLINE) || (et == ET_CURVED)) { d.x = (q.x + p.x) / 2.; d.y = (p.y + q.y) / 2.; spf = dotneato_closest(ED_spl(e), d); @@ -1493,3 +1493,4 @@ splines *getsplinepoints(edge_t * e) agnameof(agtail(e)), agnameof(aghead(e))); return sp; } + diff --git a/lib/common/utils.c b/lib/common/utils.c index 58ff9ac02..66a46adb4 100644 --- a/lib/common/utils.c +++ b/lib/common/utils.c @@ -1832,7 +1832,9 @@ int edgeType (char* s, int dflt) break; case 'c' : case 'C' : - if (!strcasecmp (s+1, "ompound")) + if (!strcasecmp (s+1, "urved")) + et = ET_CURVED; + else if (!strcasecmp (s+1, "ompound")) et = ET_COMPOUND; break; case 'f' : diff --git a/lib/dotgen/dotsplines.c b/lib/dotgen/dotsplines.c index efe42d1d1..df1cf240d 100644 --- a/lib/dotgen/dotsplines.c +++ b/lib/dotgen/dotsplines.c @@ -284,6 +284,18 @@ static void _dot_splines(graph_t * g, int normalize) #endif /* WITH_CGRAPH */ if (et == ET_NONE) return; + if (et == ET_CURVED) { + resetRW (g); + if (GD_has_labels(g) & EDGE_LABEL) { + agerr (AGWARN, "edge labels with splines=curved not supported in dot - use xlabels\n"); + } + for (n = agfstnode (g); n; n = agnxtnode(g, n)) { + for (e = agfstout(g, n); e; e = agnxtout(g,e)) { + makeStraightEdge(g, e, et, &sinfo); + } + } + goto finish; + } #ifdef ORTHO if (et == ET_ORTHO) { resetRW (g); @@ -475,9 +487,7 @@ static void _dot_splines(graph_t * g, int normalize) if (normalize) edge_normalize(g); -#ifdef ORTHO finish : -#endif /* vladimir: place port labels */ /* FIX: head and tail labels are not part of cluster bbox */ if ((E_headlabel || E_taillabel) && (E_labelangle || E_labeldistance)) { @@ -510,16 +520,16 @@ finish : /* end vladimir */ #ifdef ORTHO - if (et != ET_ORTHO) { + if ((et != ET_ORTHO) && (et != ET_CURVED)) { +#else + if (et != ET_CURVED) { #endif free(edges); free(P->boxes); free(P); free(sd.Rank_box); routesplinesterm(); -#ifdef ORTHO } -#endif State = GVSPLINES; EdgeLabelsDone = 1; } diff --git a/lib/neatogen/multispline.c b/lib/neatogen/multispline.c index cfe62e6a3..db7cd0028 100644 --- a/lib/neatogen/multispline.c +++ b/lib/neatogen/multispline.c @@ -881,7 +881,7 @@ genroute(graph_t* g, tripoly_t * trip, int s, int t, edge_t * e, int doPolyline) } if (pl.pn == 2) { - makeStraightEdge(agraphof(head), e, doPolyline); + makeStraightEdge(agraphof(head), e, doPolyline, &sinfo); goto finish; } diff --git a/lib/neatogen/neatoprocs.h b/lib/neatogen/neatoprocs.h index 95534a8a1..46c9f6228 100644 --- a/lib/neatogen/neatoprocs.h +++ b/lib/neatogen/neatoprocs.h @@ -44,7 +44,6 @@ extern "C" { extern void jitter3d(Agnode_t *, int); extern void jitter_d(Agnode_t *, int, int); extern Ppoly_t *makeObstacle(node_t * n, expand_t* ); - extern void makeStraightEdge(graph_t * g, edge_t * e, int doPolyline); extern void makeSelfArcs(path * P, edge_t * e, int stepx); extern void makeSpline(graph_t*, edge_t *, Ppoly_t **, int, boolean); extern void make_spring(graph_t *, Agnode_t *, Agnode_t *, double); diff --git a/lib/neatogen/neatosplines.c b/lib/neatogen/neatosplines.c index 281ba04e4..42455b1da 100644 --- a/lib/neatogen/neatosplines.c +++ b/lib/neatogen/neatosplines.c @@ -31,8 +31,6 @@ extern double drand48(void); extern void printvis(vconfig_t * cp); extern int in_poly(Ppoly_t argpoly, Ppoint_t q); -static pointf get_centroid(Agraph_t *g); -static void bend(pointf[],pointf); static boolean spline_merge(node_t * n) @@ -256,95 +254,6 @@ void makeSelfArcs(path * P, edge_t * e, int stepx) } } -/* makeStraightEdge: - * - * FIX: handle ports on boundary? - */ -void -makeStraightEdge(graph_t * g, edge_t * e, int doPolyline) -{ - pointf dumb[4]; - node_t *n = agtail(e); - node_t *head = aghead(e); - int e_cnt = ED_count(e); - int curved = mapbool(agget(e,"curved")); - pointf perp; - pointf del; - edge_t *e0; - int i, j, xstep, dx; - double l_perp; - pointf dumber[4]; - pointf p, q; - - p = dumb[1] = dumb[0] = add_pointf(ND_coord(n), ED_tail_port(e).p); - q = dumb[2] = dumb[3] = add_pointf(ND_coord(head), ED_head_port(e).p); - if ((e_cnt == 1) || Concentrate) { - if (curved) bend(dumb,get_centroid(g)); - clip_and_install(e, aghead(e), dumb, 4, &sinfo); - addEdgeLabels(g, e, p, q); - return; - } - - e0 = e; - if (APPROXEQPT(dumb[0], dumb[3], MILLIPOINT)) { - /* degenerate case */ - dumb[1] = dumb[0]; - dumb[2] = dumb[3]; - del.x = 0; - del.y = 0; - } - else { - perp.x = dumb[0].y - dumb[3].y; - perp.y = dumb[3].x - dumb[0].x; - l_perp = LEN(perp.x, perp.y); - xstep = GD_nodesep(g->root); - dx = xstep * (e_cnt - 1) / 2; - dumb[1].x = dumb[0].x + (dx * perp.x) / l_perp; - dumb[1].y = dumb[0].y + (dx * perp.y) / l_perp; - dumb[2].x = dumb[3].x + (dx * perp.x) / l_perp; - dumb[2].y = dumb[3].y + (dx * perp.y) / l_perp; - del.x = -xstep * perp.x / l_perp; - del.y = -xstep * perp.y / l_perp; - } - - for (i = 0; i < e_cnt; i++) { - if (aghead(e0) == head) { - p = dumb[0]; - q = dumb[3]; - for (j = 0; j < 4; j++) { - dumber[j] = dumb[j]; - } - } else { - p = dumb[3]; - q = dumb[0]; - for (j = 0; j < 4; j++) { - dumber[3 - j] = dumb[j]; - } - } - if (doPolyline) { - Ppoint_t pts[4]; - Ppolyline_t spl, line; - - line.pn = 4; - line.ps = pts; - for (j=0; j < 4; j++) { - pts[j] = dumber[j]; - } - make_polyline (line, &spl); - clip_and_install(e0, aghead(e0), spl.ps, spl.pn, &sinfo); - } - else - clip_and_install(e0, aghead(e0), dumber, 4, &sinfo); - - addEdgeLabels(g, e0, p, q); - e0 = ED_to_virt(e0); - dumb[1].x += del.x; - dumb[1].y += del.y; - dumb[2].x += del.x; - dumb[2].y += del.y; - } -} - /* makeObstacle: * Given a node, return an obstacle reflecting the * node's geometry. pmargin specifies how much space to allow @@ -596,6 +505,7 @@ void makeSpline(graph_t* g, edge_t * e, Ppoly_t ** obs, int npoly, boolean chkPt * remain in the cluster's bounding box and, conversely, a cluster's box * is not altered to reflect intra-cluster edges. * If Nop > 1 and the spline exists, it is just copied. + * NOTE: if edgetype = ET_NONE, we shouldn't be here. */ static int _spline_edges(graph_t * g, expand_t* pmargin, int edgetype) { @@ -612,7 +522,7 @@ static int _spline_edges(graph_t * g, expand_t* pmargin, int edgetype) int legal = 0; /* build configuration */ - if (edgetype != ET_LINE) { + if (edgetype >= ET_PLINE) { obs = N_NEW(agnnodes(g), Ppoly_t *); for (n = agfstnode(g); n; n = agnxtnode(g, n)) { obp = makeObstacle(n, pmargin); @@ -680,7 +590,7 @@ static int _spline_edges(graph_t * g, expand_t* pmargin, int edgetype) int fail = 0; if ((ED_path(e).pn == 2) && !BOUNDARY_PORT(e)) /* if a straight line can connect the ends */ - makeStraightEdge(g, e, edgetype == ET_PLINE); + makeStraightEdge(g, e, edgetype, &sinfo); else { if (!rtr) rtr = mkRouter (obs, npoly); fail = makeMultiSpline(g, e, rtr, edgetype == ET_PLINE); @@ -703,7 +613,7 @@ static int _spline_edges(graph_t * g, expand_t* pmargin, int edgetype) e0 = ED_to_virt(e0); } } else { - makeStraightEdge(g, e, 0); + makeStraightEdge(g, e, edgetype, &sinfo); } } } @@ -1037,49 +947,3 @@ void neato_set_aspect(graph_t * g) } } -static pointf get_centroid(Agraph_t *g) -{ - int cnt = 0; - static pointf sum = {0.0, 0.0}; - static Agraph_t *save; - Agnode_t *n; - -sum.x = (GD_bb(g).LL.x + GD_bb(g).UR.x) / 2.0; -sum.y = (GD_bb(g).LL.y + GD_bb(g).UR.y) / 2.0; -return sum; - - if (save == g) return sum; - save = g; - for (n = agfstnode(g); n; n = agnxtnode(g,n)) { - sum.x += ND_pos(n)[0]; - sum.y += ND_pos(n)[1]; - cnt++; - } - sum.x = sum.x / cnt; - sum.y = sum.y / cnt; - return sum; -} - -static void bend(pointf spl[4], pointf centroid) -{ - pointf midpt,a; - double r; - double dist,dx,dy; - - midpt.x = (spl[0].x + spl[3].x)/2.0; - midpt.y = (spl[0].y + spl[3].y)/2.0; - dx = (spl[3].x - spl[0].x); - dy = (spl[3].y - spl[0].y); - dist = sqrt(dx*dx + dy*dy); - r = dist/5.0; - { - double vX = centroid.x - midpt.x; - double vY = centroid.y - midpt.y; - double magV = sqrt(vX*vX + vY*vY); - a.x = midpt.x - vX / magV * r; /* + would be closest point */ - a.y = midpt.y - vY / magV * r; - } - /* this can be improved */ - spl[1].x = spl[2].x = a.x; - spl[1].y = spl[2].y = a.y; -} -- 2.40.0