lib/autoroute.c

   1 /* Dia -- a diagram creation/manipulation program -*- c -*-
   2  * Copyright (C) 2002 Alexander Larsson
   3  *
   4  * autoroute.c -- Automatic layout of connections.
   5  * Copyright (C) 2003 Lars Clausen
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20  */
  21
  22 #include "config.h"
  23
  24 #include "object.h"
  25 #include "connectionpoint.h"
  26 #include "orth_conn.h"
  27 #include "autoroute.h"
  28
  29 #define MAX_BADNESS 10000.0
  30 /** Add badness if a line is shorter than this distance. */
  31 #define MIN_DIST 1.0
  32 /** The maximum badness that can be given for a line being too short. */
  33 #define MAX_SMALL_BADNESS 10.0
  34 /** The badness given for having extra segments. */
  35 #define EXTRA_SEGMENT_BADNESS 10.0
  36
  37 static real calculate_badness(Point *ps, guint num_points);
  38
  39 static real autoroute_layout_parallel(Point *to,
  40                                         guint *num_points, Point **points);
  41 static real autoroute_layout_orthogonal(Point *to,
  42                                           int enddir,
  43                                           guint *num_points, Point **points);
  44 static real autoroute_layout_opposite(Point *to,
  45                                         guint *num_points, Point **points);
  46 static Point autolayout_adjust_for_gap(Point *pos, int dir, ConnectionPoint *cp);
  47 static guint autolayout_normalize_points(guint startdir, guint enddir,
  48                                          Point start, Point end,
  49                                          Point *newend);
  50 static Point *autolayout_unnormalize_points(guint dir,
  51                                             Point start,
  52                                             Point *points,
  53                                             guint num_points);
  54
  55 /** Calculate a 'pleasing' route between two connection points.
  56  * If a good route is found, updates the given OrthConn with the values
  57  *   and returns TRUE.
  58  * Otherwise, the OrthConn is untouched, and the function returns FALSE.
  59  * Handles are not updated by this operation.
  60  */
  61 gboolean
  62 autoroute_layout_orthconn(OrthConn *conn,
  63                           ConnectionPoint *startconn, ConnectionPoint *endconn)
  64 {
  65   real min_badness = MAX_BADNESS;
  66   Point *best_layout = NULL;
  67   guint best_num_points = 0;
  68   int startdir, enddir;
  69
  70   int fromdir, todir;
  71   Point frompos, topos;
  72
  73   frompos = conn->points[0];
  74   topos = conn->points[conn->numpoints-1];
  75   if (startconn != NULL) {
  76     fromdir = startconn->directions;
  77     frompos = startconn->pos;
  78   }
  79   else fromdir = DIR_NORTH|DIR_EAST|DIR_SOUTH|DIR_WEST;
  80   if (endconn != NULL) {
  81     todir = endconn->directions;
  82     topos = endconn->pos;
  83   }
  84   else todir = DIR_NORTH|DIR_EAST|DIR_SOUTH|DIR_WEST;
  85
  86   for (startdir = DIR_NORTH; startdir <= DIR_WEST; startdir *= 2) {
  87     for (enddir = DIR_NORTH; enddir <= DIR_WEST; enddir *= 2) {
  88       if ((fromdir & startdir) &&
  89           (todir & enddir)) {
  90         real this_badness;
  91         Point *this_layout = NULL;
  92         guint this_num_points;
  93         guint normal_enddir;
  94         Point startpoint, endpoint;
  95         Point otherpoint;
  96         startpoint = autolayout_adjust_for_gap(&frompos, startdir, startconn);
  97         endpoint = autolayout_adjust_for_gap(&topos, enddir, endconn);
  98         /*
  99         printf("Startdir %d enddir %d orgstart %.2f, %.2f orgend %.2f, %.2f start %.2f, %.2f end %.2f, %.2f\n",
 100                startdir, enddir,
 101                frompos.x, frompos.y,
 102                topos.x, topos.y,
 103                startpoint.x, startpoint.y,
 104                endpoint.x, endpoint.y);
 105         */
 106         normal_enddir = autolayout_normalize_points(startdir, enddir,
 107                                                     startpoint, endpoint,
 108                                                     &otherpoint);
 109         if (normal_enddir == DIR_NORTH ) {
 110           this_badness = autoroute_layout_parallel(&otherpoint,
 111                                                    &this_num_points,
 112                                                    &this_layout);
 113         } else if (normal_enddir == DIR_SOUTH) {
 114           this_badness = autoroute_layout_opposite(&otherpoint,
 115                                                    &this_num_points,
 116                                                    &this_layout);
 117         } else {
 118           this_badness = autoroute_layout_orthogonal(&otherpoint,
 119                                                      normal_enddir,
 120                                                      &this_num_points,
 121                                                      &this_layout);
 122         }
 123         if (this_layout != NULL) {
 124           if (this_badness-min_badness < -0.00001) {
 125             /*
 126             printf("Dir %d to %d badness %f < %f\n", startdir, enddir,
 127                    this_badness, min_badness);
 128             */
 129             min_badness = this_badness;
 130             if (best_layout != NULL) g_free(best_layout);
 131             best_layout = autolayout_unnormalize_points(startdir, startpoint,
 132                                                         this_layout,
 133                                                         this_num_points);
 134             best_num_points = this_num_points;
 135           } else {
 136               g_free(this_layout);
 137           }
 138         }
 139       }
 140     }
 141   }
 142
 143   if (min_badness < MAX_BADNESS) {
 144     orthconn_set_points(conn, best_num_points, best_layout);
 145     return TRUE;
 146   } else {
 147     g_free(best_layout);
 148     return FALSE;
 149   }
 150 }
 151
 152 /** Returns the basic badness of a length */
 153 static real
 154 length_badness(real len)
 155 {
 156   if (len < MIN_DIST) {
 157     /* This should be zero at MIN_DIST and MAX_SMALL_BADNESS at 0 */
 158     return 2*MAX_SMALL_BADNESS/(1.0+len/MIN_DIST) - MAX_SMALL_BADNESS;
 159   } else {
 160     return len-MIN_DIST;
 161   }
 162 }
 163
 164 /** Returns the accumulated badness of a layout */
 165 static real
 166 calculate_badness(Point *ps, guint num_points)
 167 {
 168   real badness;
 169   int i;
 170   badness = (num_points-1)*EXTRA_SEGMENT_BADNESS;
 171   for (i = 0; i < num_points-1; i++) {
 172     real this_badness;
 173     real len = distance_point_point_manhattan(&ps[i], &ps[i+1]);
 174     this_badness = length_badness(len);
 175     badness += this_badness;
 176   }
 177   return badness;
 178 }
 179
 180 /** Adjust one end of an orthconn for gaps */
 181 static Point
 182 autolayout_adjust_for_gap(Point *pos, int dir, ConnectionPoint *cp)
 183 {
 184   DiaObject *object;
 185   Point dir_other;
 186   /* Do absolute gaps here, once it's defined */
 187
 188   if (!connpoint_is_autogap(cp)) {
 189     return *pos;
 190   }
 191
 192   object  = cp->object;
 193
 194   dir_other.x = pos->x;
 195   dir_other.y = pos->y;
 196   switch (dir) {
 197   case DIR_NORTH:
 198     dir_other.y += 2 * (object->bounding_box.top - pos->y);
 199     break;
 200   case DIR_SOUTH:
 201     dir_other.y += 2 * (object->bounding_box.bottom - pos->y);
 202     break;
 203   case DIR_EAST:
 204     dir_other.x += 2 * (object->bounding_box.right - pos->x);
 205     break;
 206   case DIR_WEST:
 207     dir_other.x += 2 * (object->bounding_box.left - pos->x);
 208     break;
 209   default:
 210     g_warning("Impossible direction %d\n", dir);
 211   }
 212   return calculate_object_edge(pos, &dir_other, object);
 213 }
 214
 215 static real
 216 autoroute_layout_parallel(Point *to, guint *num_points, Point **points)
 217 {
 218   Point *ps = NULL;
 219   if (fabs(to->x) > MIN_DIST) {
 220     real top = MIN(-MIN_DIST, to->y-MIN_DIST);
 221     /*
 222     printf("Doing parallel layout: Wide\n");
 223     */
 224     *num_points = 4;
 225     ps = g_new0(Point, *num_points);
 226     /* points[0] is 0,0 */
 227     ps[1].y = top;
 228     ps[2].x = to->x;
 229     ps[2].y = top;
 230     ps[3] = *to;
 231   } else if (to->y > 0) { /* Close together, end below */
 232     real top = -MIN_DIST;
 233     real off = to->x+MIN_DIST*(to->x>0?1.0:-1.0);
 234     real bottom = to->y-MIN_DIST;
 235     /*
 236     printf("Doing parallel layout: Narrow\n");
 237     */
 238     *num_points = 6;
 239     ps = g_new0(Point, *num_points);
 240     /* points[0] is 0,0 */
 241     ps[1].y = top;
 242     ps[2].x = off;
 243     ps[2].y = top;
 244     ps[3].x = off;
 245     ps[3].y = bottom;
 246     ps[4].x = to->x;
 247     ps[4].y = bottom;
 248     ps[5] = *to;
 249   } else {
 250     real top = to->y-MIN_DIST;
 251     real off = MIN_DIST*(to->x>0?-1.0:1.0);
 252     real bottom = -MIN_DIST;
 253     /*
 254     printf("Doing parallel layout: Narrow\n");
 255     */
 256     *num_points = 6;
 257     ps = g_new0(Point, *num_points);
 258     /* points[0] is 0,0 */
 259     ps[1].y = bottom;
 260     ps[2].x = off;
 261     ps[2].y = bottom;
 262     ps[3].x = off;
 263     ps[3].y = top;
 264     ps[4].x = to->x;
 265     ps[4].y = top;
 266     ps[5] = *to;
 267   }
 268   *points = ps;
 269   return calculate_badness(ps, *num_points);
 270 }
 271
 272 static real
 273 autoroute_layout_orthogonal(Point *to, int enddir,
 274                             guint *num_points, Point **points)
 275 {
 276   /* This one doesn't consider enddir yet, not more complex layouts. */
 277   Point *ps = NULL;
 278   real dirmult = (enddir==DIR_WEST?1.0:-1.0);
 279   if (to->y < -MIN_DIST) {
 280     if (dirmult*to->x > MIN_DIST) {
 281       /*
 282       printf("Doing orthogonal layout: Three-way\n");
 283       */
 284       *num_points = 3;
 285       ps = g_new0(Point, *num_points);
 286       /* points[0] is 0,0 */
 287       ps[1].y = to->y;
 288       ps[2] = *to;
 289     } else {
 290       real off;
 291       if (dirmult*to->x > 0) off = -dirmult*MIN_DIST;
 292       else off = -dirmult*(MIN_DIST+fabs(to->x));
 293       *num_points = 5;
 294       ps = g_new0(Point, *num_points);
 295       ps[1].y = -MIN_DIST;
 296       ps[2].x = off;
 297       ps[2].y = -MIN_DIST;
 298       ps[3].x = off;
 299       ps[3].y = to->y;
 300       ps[4] = *to;
 301     }
 302   } else {
 303     if (dirmult*to->x > 2*MIN_DIST) {
 304       real mid = to->x/2;
 305       *num_points = 5;
 306       ps = g_new0(Point, *num_points);
 307       ps[1].y = -MIN_DIST;
 308       ps[2].x = mid;
 309       ps[2].y = -MIN_DIST;
 310       ps[3].x = mid;
 311       ps[3].y = to->y;
 312       ps[4] = *to;
 313     } else {
 314       real off;
 315       if (dirmult*to->x > 0) off = -dirmult*MIN_DIST;
 316       else off = -dirmult*(MIN_DIST+fabs(to->x));
 317       *num_points = 5;
 318       ps = g_new0(Point, *num_points);
 319       ps[1].y = -MIN_DIST;
 320       ps[2].x = off;
 321       ps[2].y = -MIN_DIST;
 322       ps[3].x = off;
 323       ps[3].y = to->y;
 324       ps[4] = *to;
 325     }
 326   }
 327   /*
 328   printf("Doing orthogonal layout\n");
 329   */
 330   *points = ps;
 331   return calculate_badness(ps, *num_points);
 332 }
 333
 334 static real
 335 autoroute_layout_opposite(Point *to, guint *num_points, Point **points)
 336 {
 337   Point *ps = NULL;
 338   if (to->y < -MIN_DIST) {
 339     *num_points = 4;
 340     ps = g_new0(Point, *num_points);
 341     if (fabs(to->x) < 0.00000001) {
 342       ps[2] = ps[3] = *to;
 343       *points = ps;
 344       return length_badness(fabs(to->y))+2*EXTRA_SEGMENT_BADNESS;
 345     } else {
 346       real mid = to->y/2;
 347       /*
 348         printf("Doing opposite layout: Three-way\n");
 349       */
 350       /* points[0] is 0,0 */
 351       ps[1].y = mid;
 352       ps[2].x = to->x;
 353       ps[2].y = mid;
 354       ps[3] = *to;
 355       *points = ps;
 356       return 2*length_badness(fabs(mid))+2*EXTRA_SEGMENT_BADNESS;
 357     }
 358   } else if (fabs(to->x) > 2*MIN_DIST) {
 359     real mid = to->x/2;
 360     /*
 361     printf("Doing opposite layout: Doorhanger\n");
 362     */
 363     *num_points = 6;
 364     ps = g_new0(Point, *num_points);
 365     /* points[0] is 0,0 */
 366     ps[1].y = -MIN_DIST;
 367     ps[2].x = mid;
 368     ps[2].y = -MIN_DIST;
 369     ps[3].x = mid;
 370     ps[3].y = to->y+MIN_DIST;
 371     ps[4].x = to->x;
 372     ps[4].y = to->y+MIN_DIST;
 373     ps[5] = *to;
 374   } else {
 375     real off = MIN_DIST*(to->x>0?-1.0:1.0);
 376     /*
 377     printf("Doing opposite layout: Overlap\n");
 378     */
 379     *num_points = 6;
 380     ps = g_new0(Point, *num_points);
 381     ps[1].y = -MIN_DIST;
 382     ps[2].x = off;
 383     ps[2].y = -MIN_DIST;
 384     ps[3].x = off;
 385     ps[3].y = to->y+MIN_DIST;
 386     ps[4].x = to->x;
 387     ps[4].y = to->y+MIN_DIST;
 388     ps[5] = *to;
 389   }
 390   *points = ps;
 391   return calculate_badness(ps, *num_points);
 392 }
 393
 394 static void
 395 point_rotate_cw(Point *p) {
 396   real tmp = p->x;
 397   p->x = -p->y;
 398   p->y = tmp;
 399 }
 400
 401 static void
 402 point_rotate_ccw(Point *p) {
 403   real tmp = p->x;
 404   p->x = p->y;
 405   p->y = -tmp;
 406 }
 407
 408 static void
 409 point_rotate_180(Point *p) {
 410   p->x = -p->x;
 411   p->y = -p->y;
 412 }
 413
 414 /** Normalizes the directions and points to make startdir be north and
 415  * the starting point be 0,0.
 416  * Normalized points are put in newstart and newend.
 417  * Returns the new enddir.
 418  */
 419 static guint
 420 autolayout_normalize_points(guint startdir, guint enddir,
 421                             Point start, Point end, Point *newend)
 422 {
 423   newend->x = end.x-start.x;
 424   newend->y = end.y-start.y;
 425   if (startdir == DIR_NORTH) {
 426     return enddir;
 427   } else if (startdir == DIR_EAST) {
 428     point_rotate_ccw(newend);
 429     if (enddir == DIR_NORTH) return DIR_WEST;
 430     return enddir/2;
 431   } else if (startdir == DIR_WEST) {
 432     point_rotate_cw(newend);
 433     if (enddir == DIR_WEST) return DIR_NORTH;
 434     return enddir*2;
 435   } else { /* startdir == DIR_SOUTH */
 436     point_rotate_180(newend);
 437     if (enddir < DIR_SOUTH) return enddir*4;
 438     else return enddir/4;
 439   }
 440   /* Insert handling of other stuff here */
 441   return enddir;
 442 }
 443
 444 /** Reverses the normalizing process of autolayout_normalize_points.
 445  * Returns the new array of points, freeing the old one if necessary.
 446  */
 447 static Point *
 448 autolayout_unnormalize_points(guint startdir,
 449                               Point start,
 450                               Point *points,
 451                               guint num_points)
 452 {
 453   Point *newpoints = g_new(Point, num_points);
 454   int i;
 455   if (startdir == DIR_NORTH) {
 456     for (i = 0; i < num_points; i++) {
 457       newpoints[i] = points[i];
 458       point_add(&newpoints[i], &start);
 459     }
 460   } else if (startdir == DIR_WEST) {
 461     for (i = 0; i < num_points; i++) {
 462       newpoints[i] = points[i];
 463       point_rotate_ccw(&newpoints[i]);
 464       point_add(&newpoints[i], &start);
 465     }
 466   } else if (startdir == DIR_SOUTH) {
 467     for (i = 0; i < num_points; i++) {
 468       newpoints[i] = points[i];
 469       point_rotate_180(&newpoints[i]);
 470       point_add(&newpoints[i], &start);
 471     }
 472   } else if (startdir == DIR_EAST) {
 473     for (i = 0; i < num_points; i++) {
 474       newpoints[i] = points[i];
 475       point_rotate_cw(&newpoints[i]);
 476       point_add(&newpoints[i], &start);
 477     }
 478   }
 479   g_free(points);
 480   return newpoints;
 481 }