src/unclump.cpp

   1 /** @file
   2  * @brief Unclumping objects
   3  */
   4 /* Authors:
   5  *   bulia byak
   6  *
   7  * Copyright (C) 2005 Authors
   8  * Released under GNU GPL, read the file 'COPYING' for more information
   9  */
  10
  11 #include <algorithm>
  12 #include <map>
  13 #include "sp-item.h"
  14
  15
  16 // Taking bbox of an item is an expensive operation, and we need to do it many times, so here we
  17 // cache the centers, widths, and heights of items
  18
  19 //FIXME: make a class with these cashes as members instead of globals
  20 std::map<const gchar *, Geom::Point> c_cache;
  21 std::map<const gchar *, Geom::Point> wh_cache;
  22
  23 /**
  24 Center of bbox of item
  25 */
  26 Geom::Point
  27 unclump_center (SPItem *item)
  28 {
  29     std::map<const gchar *, Geom::Point>::iterator i = c_cache.find(SP_OBJECT_ID(item));
  30     if ( i != c_cache.end() ) {
  31         return i->second;
  32     }
  33
  34     Geom::OptRect r = item->getBounds(sp_item_i2d_affine(item));
  35     if (r) {
  36         Geom::Point const c = r->midpoint();
  37         c_cache[SP_OBJECT_ID(item)] = c;
  38         return c;
  39     } else {
  40         // FIXME
  41         return Geom::Point(0, 0);
  42     }
  43 }
  44
  45 Geom::Point
  46 unclump_wh (SPItem *item)
  47 {
  48     Geom::Point wh;
  49     std::map<const gchar *, Geom::Point>::iterator i = wh_cache.find(SP_OBJECT_ID(item));
  50     if ( i != wh_cache.end() ) {
  51         wh = i->second;
  52     } else {
  53         Geom::OptRect r = item->getBounds(sp_item_i2d_affine(item));
  54         if (r) {
  55             wh = r->dimensions();
  56             wh_cache[SP_OBJECT_ID(item)] = wh;
  57         } else {
  58             wh = Geom::Point(0, 0);
  59         }
  60     }
  61
  62     return wh;
  63 }
  64
  65 /**
  66 Distance between "edges" of item1 and item2. An item is considered to be an ellipse inscribed into its w/h,
  67 so its radius (distance from center to edge) depends on the w/h and the angle towards the other item.
  68 May be negative if the edge of item1 is between the center and the edge of item2.
  69 */
  70 double
  71 unclump_dist (SPItem *item1, SPItem *item2)
  72 {
  73         Geom::Point c1 = unclump_center (item1);
  74         Geom::Point c2 = unclump_center (item2);
  75
  76         Geom::Point wh1 = unclump_wh (item1);
  77         Geom::Point wh2 = unclump_wh (item2);
  78
  79         // angle from each item's center to the other's, unsqueezed by its w/h, normalized to 0..pi/2
  80         double a1 = atan2 ((c2 - c1)[Geom::Y], (c2 - c1)[Geom::X] * wh1[Geom::Y]/wh1[Geom::X]);
  81         a1 = fabs (a1);
  82         if (a1 > M_PI/2) a1 = M_PI - a1;
  83
  84         double a2 = atan2 ((c1 - c2)[Geom::Y], (c1 - c2)[Geom::X] * wh2[Geom::Y]/wh2[Geom::X]);
  85         a2 = fabs (a2);
  86         if (a2 > M_PI/2) a2 = M_PI - a2;
  87
  88         // get the radius of each item for the given angle
  89         double r1 = 0.5 * (wh1[Geom::X] + (wh1[Geom::Y] - wh1[Geom::X]) * (a1/(M_PI/2)));
  90         double r2 = 0.5 * (wh2[Geom::X] + (wh2[Geom::Y] - wh2[Geom::X]) * (a2/(M_PI/2)));
  91
  92         // dist between centers minus angle-adjusted radii
  93         double dist_r =  (Geom::L2 (c2 - c1) - r1 - r2);
  94
  95         double stretch1 = wh1[Geom::Y]/wh1[Geom::X];
  96         double stretch2 = wh2[Geom::Y]/wh2[Geom::X];
  97
  98         if ((stretch1 > 1.5 || stretch1 < 0.66) && (stretch2 > 1.5 || stretch2 < 0.66)) {
  99
 100                 std::vector<double> dists;
 101                 dists.push_back (dist_r);
 102
 103                 // If both objects are not circle-like, find dists between four corners
 104                 std::vector<Geom::Point> c1_points(2);
 105                 {
 106                         double y_closest;
 107                         if (c2[Geom::Y] > c1[Geom::Y] + wh1[Geom::Y]/2) {
 108                                 y_closest = c1[Geom::Y] + wh1[Geom::Y]/2;
 109                         } else if (c2[Geom::Y] < c1[Geom::Y] - wh1[Geom::Y]/2) {
 110                                 y_closest = c1[Geom::Y] - wh1[Geom::Y]/2;
 111                         } else {
 112                                 y_closest = c2[Geom::Y];
 113                         }
 114                         c1_points[0] = Geom::Point (c1[Geom::X], y_closest);
 115                         double x_closest;
 116                         if (c2[Geom::X] > c1[Geom::X] + wh1[Geom::X]/2) {
 117                                 x_closest = c1[Geom::X] + wh1[Geom::X]/2;
 118                         } else if (c2[Geom::X] < c1[Geom::X] - wh1[Geom::X]/2) {
 119                                 x_closest = c1[Geom::X] - wh1[Geom::X]/2;
 120                         } else {
 121                                 x_closest = c2[Geom::X];
 122                         }
 123                         c1_points[1] = Geom::Point (x_closest, c1[Geom::Y]);
 124                 }
 125
 126
 127                 std::vector<Geom::Point> c2_points(2);
 128                 {
 129                         double y_closest;
 130                         if (c1[Geom::Y] > c2[Geom::Y] + wh2[Geom::Y]/2) {
 131                                 y_closest = c2[Geom::Y] + wh2[Geom::Y]/2;
 132                         } else if (c1[Geom::Y] < c2[Geom::Y] - wh2[Geom::Y]/2) {
 133                                 y_closest = c2[Geom::Y] - wh2[Geom::Y]/2;
 134                         } else {
 135                                 y_closest = c1[Geom::Y];
 136                         }
 137                         c2_points[0] = Geom::Point (c2[Geom::X], y_closest);
 138                         double x_closest;
 139                         if (c1[Geom::X] > c2[Geom::X] + wh2[Geom::X]/2) {
 140                                 x_closest = c2[Geom::X] + wh2[Geom::X]/2;
 141                         } else if (c1[Geom::X] < c2[Geom::X] - wh2[Geom::X]/2) {
 142                                 x_closest = c2[Geom::X] - wh2[Geom::X]/2;
 143                         } else {
 144                                 x_closest = c1[Geom::X];
 145                         }
 146                         c2_points[1] = Geom::Point (x_closest, c2[Geom::Y]);
 147                 }
 148
 149                 for (int i = 0; i < 2; i ++) {
 150                         for (int j = 0; j < 2; j ++) {
 151                                 dists.push_back (Geom::L2 (c1_points[i] - c2_points[j]));
 152                         }
 153                 }
 154
 155                 // return the minimum of all dists
 156                 return *std::min_element(dists.begin(), dists.end());
 157         } else {
 158                 return dist_r;
 159         }
 160 }
 161
 162 /**
 163 Average unclump_dist from item to others
 164 */
 165 double unclump_average (SPItem *item, GSList *others)
 166 {
 167     int n = 0;
 168     double sum = 0;
 169
 170     for (GSList *i = others; i != NULL; i = i->next) {
 171         SPItem *other = SP_ITEM (i->data);
 172
 173         if (other == item)
 174             continue;
 175
 176         n++;
 177         sum += unclump_dist (item, other);
 178     }
 179
 180     if (n != 0)
 181         return sum/n;
 182     else
 183         return 0;
 184 }
 185
 186 /**
 187 Closest to item among others
 188  */
 189 SPItem *unclump_closest (SPItem *item, GSList *others)
 190 {
 191     double min = HUGE_VAL;
 192     SPItem *closest = NULL;
 193
 194     for (GSList *i = others; i != NULL; i = i->next) {
 195         SPItem *other = SP_ITEM (i->data);
 196
 197         if (other == item)
 198             continue;
 199
 200         double dist = unclump_dist (item, other);
 201         if (dist < min && fabs (dist) < 1e6) {
 202             min = dist;
 203             closest = other;
 204         }
 205     }
 206
 207     return closest;
 208 }
 209
 210 /**
 211 Most distant from item among others
 212  */
 213 SPItem *unclump_farest (SPItem *item, GSList *others)
 214 {
 215     double max = -HUGE_VAL;
 216     SPItem *farest = NULL;
 217
 218     for (GSList *i = others; i != NULL; i = i->next) {
 219         SPItem *other = SP_ITEM (i->data);
 220
 221         if (other == item)
 222             continue;
 223
 224         double dist = unclump_dist (item, other);
 225         if (dist > max && fabs (dist) < 1e6) {
 226             max = dist;
 227             farest = other;
 228         }
 229     }
 230
 231     return farest;
 232 }
 233
 234 /**
 235 Removes from the \a rest list those items that are "behind" \a closest as seen from \a item,
 236 i.e. those on the other side of the line through \a closest perpendicular to the direction from \a
 237 item to \a closest. Returns a newly created list which must be freed.
 238  */
 239 GSList *
 240 unclump_remove_behind (SPItem *item, SPItem *closest, GSList *rest)
 241 {
 242     Geom::Point it = unclump_center (item);
 243     Geom::Point p1 = unclump_center (closest);
 244
 245     // perpendicular through closest to the direction to item:
 246     Geom::Point perp = Geom::rot90(it - p1);
 247     Geom::Point p2 = p1 + perp;
 248
 249     // get the standard Ax + By + C = 0 form for p1-p2:
 250     double A = p1[Geom::Y] - p2[Geom::Y];
 251     double B = p2[Geom::X] - p1[Geom::X];
 252     double C = p2[Geom::Y] * p1[Geom::X] - p1[Geom::Y] * p2[Geom::X];
 253
 254     // substitute the item into it:
 255     double val_item = A * it[Geom::X] + B * it[Geom::Y] + C;
 256
 257     GSList *out = NULL;
 258
 259     for (GSList *i = rest; i != NULL; i = i->next) {
 260         SPItem *other = SP_ITEM (i->data);
 261
 262         if (other == item)
 263             continue;
 264
 265         Geom::Point o = unclump_center (other);
 266         double val_other = A * o[Geom::X] + B * o[Geom::Y] + C;
 267
 268         if (val_item * val_other <= 1e-6) {
 269             // different signs, which means item and other are on the different sides of p1-p2 line; skip
 270         } else {
 271             out = g_slist_prepend (out, other);
 272         }
 273     }
 274
 275     return out;
 276 }
 277
 278 /**
 279 Moves \a what away from \a from by \a dist
 280  */
 281 void
 282 unclump_push (SPItem *from, SPItem *what, double dist)
 283 {
 284     Geom::Point it = unclump_center (what);
 285     Geom::Point p = unclump_center (from);
 286     Geom::Point by = dist * Geom::unit_vector (- (p - it));
 287
 288     Geom::Matrix move = Geom::Translate (by);
 289
 290     std::map<const gchar *, Geom::Point>::iterator i = c_cache.find(SP_OBJECT_ID(what));
 291     if ( i != c_cache.end() ) {
 292         i->second *= move;
 293     }
 294
 295     //g_print ("push %s at %g,%g from %g,%g by %g,%g, dist %g\n", SP_OBJECT_ID(what), it[Geom::X],it[Geom::Y], p[Geom::X],p[Geom::Y], by[Geom::X],by[Geom::Y], dist);
 296
 297     sp_item_set_i2d_affine(what, sp_item_i2d_affine(what) * move);
 298     sp_item_write_transform(what, SP_OBJECT_REPR(what), what->transform, NULL);
 299 }
 300
 301 /**
 302 Moves \a what towards \a to by \a dist
 303  */
 304 void
 305 unclump_pull (SPItem *to, SPItem *what, double dist)
 306 {
 307     Geom::Point it = unclump_center (what);
 308     Geom::Point p = unclump_center (to);
 309     Geom::Point by = dist * Geom::unit_vector (p - it);
 310
 311     Geom::Matrix move = Geom::Translate (by);
 312
 313     std::map<const gchar *, Geom::Point>::iterator i = c_cache.find(SP_OBJECT_ID(what));
 314     if ( i != c_cache.end() ) {
 315         i->second *= move;
 316     }
 317
 318     //g_print ("pull %s at %g,%g to %g,%g by %g,%g, dist %g\n", SP_OBJECT_ID(what), it[Geom::X],it[Geom::Y], p[Geom::X],p[Geom::Y], by[Geom::X],by[Geom::Y], dist);
 319
 320     sp_item_set_i2d_affine(what, sp_item_i2d_affine(what) * move);
 321     sp_item_write_transform(what, SP_OBJECT_REPR(what), what->transform, NULL);
 322 }
 323
 324
 325 /**
 326 Unclumps the items in \a items, reducing local unevenness in their distribution. Produces an effect
 327 similar to "engraver dots". The only distribution which is unchanged by unclumping is a hexagonal
 328 grid. May be called repeatedly for stronger effect.
 329  */
 330 void
 331 unclump (GSList *items)
 332 {
 333     c_cache.clear();
 334     wh_cache.clear();
 335
 336     for (GSList *i = items; i != NULL; i = i->next) { //  for each original/clone x:
 337         SPItem *item = SP_ITEM (i->data);
 338
 339         GSList *nei = NULL;
 340
 341         GSList *rest = g_slist_copy (items);
 342         rest = g_slist_remove (rest, item);
 343
 344         while (rest != NULL) {
 345             SPItem *closest = unclump_closest (item, rest);
 346             if (closest) {
 347                 nei = g_slist_prepend (nei, closest);
 348                 rest = g_slist_remove (rest, closest);
 349                 GSList *new_rest = unclump_remove_behind (item, closest, rest);
 350                 g_slist_free (rest);
 351                 rest = new_rest;
 352             } else {
 353                 g_slist_free (rest);
 354                 break;
 355             }
 356         }
 357
 358         if (g_slist_length (nei) >= 2) {
 359             double ave = unclump_average (item, nei);
 360
 361             SPItem *closest = unclump_closest (item, nei);
 362             SPItem *farest = unclump_farest (item, nei);
 363
 364             double dist_closest = unclump_dist (closest, item);
 365             double dist_farest = unclump_dist (farest, item);
 366
 367             //g_print ("NEI %d for item %s    closest %s at %g  farest %s at %g  ave %g\n", g_slist_length(nei), SP_OBJECT_ID(item), SP_OBJECT_ID(closest), dist_closest, SP_OBJECT_ID(farest), dist_farest, ave);
 368
 369             if (fabs (ave) < 1e6 && fabs (dist_closest) < 1e6 && fabs (dist_farest) < 1e6) { // otherwise the items are bogus
 370                 // increase these coefficients to make unclumping more aggressive and less stable
 371                 // the pull coefficient is a bit bigger to counteract the long-term expansion trend
 372                 unclump_push (closest, item, 0.3 * (ave - dist_closest));
 373                 unclump_pull (farest, item, 0.35 * (dist_farest - ave));
 374             }
 375         }
 376     }
 377 }
 378
 379 /*
 380   Local Variables:
 381   mode:c++
 382   c-file-style:"stroustrup"
 383   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 384   indent-tabs-mode:nil
 385   fill-column:99
 386   End:
 387 */
 388 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :