src/unclump.cpp

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