src/dialogs/unclump.cpp

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