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