Code

Fixed directory for inkscape executable.
[inkscape.git] / 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  */
11 #include <algorithm>
12 #include <map>
13 #include "sp-item.h"
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
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;
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     }
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 }
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     }
62     return wh;
63 }
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);
76         Geom::Point wh1 = unclump_wh (item1);
77         Geom::Point wh2 = unclump_wh (item2);
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;
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;
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)));
92         // dist between centers minus angle-adjusted radii
93         double dist_r =  (Geom::L2 (c2 - c1) - r1 - r2);
95         double stretch1 = wh1[Geom::Y]/wh1[Geom::X];
96         double stretch2 = wh2[Geom::Y]/wh2[Geom::X];
98         if ((stretch1 > 1.5 || stretch1 < 0.66) && (stretch2 > 1.5 || stretch2 < 0.66)) {
100                 std::vector<double> dists;
101                 dists.push_back (dist_r);
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                 }
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                 }
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                 }
155                 // return the minimum of all dists
156                 return *std::min_element(dists.begin(), dists.end());
157         } else {
158                 return dist_r;
159         }
162 /**
163 Average unclump_dist from item to others
164 */
165 double unclump_average (SPItem *item, GSList *others)
167     int n = 0;
168     double sum = 0;
170     for (GSList *i = others; i != NULL; i = i->next) {
171         SPItem *other = SP_ITEM (i->data);
173         if (other == item)
174             continue;
176         n++;
177         sum += unclump_dist (item, other);
178     }
180     if (n != 0)
181         return sum/n;
182     else
183         return 0;
186 /**
187 Closest to item among others
188  */
189 SPItem *unclump_closest (SPItem *item, GSList *others)
191     double min = HUGE_VAL;
192     SPItem *closest = NULL;
194     for (GSList *i = others; i != NULL; i = i->next) {
195         SPItem *other = SP_ITEM (i->data);
197         if (other == item)
198             continue;
200         double dist = unclump_dist (item, other);
201         if (dist < min && fabs (dist) < 1e6) {
202             min = dist;
203             closest = other;
204         }
205     }
207     return closest;
210 /**
211 Most distant from item among others
212  */
213 SPItem *unclump_farest (SPItem *item, GSList *others)
215     double max = -HUGE_VAL;
216     SPItem *farest = NULL;
218     for (GSList *i = others; i != NULL; i = i->next) {
219         SPItem *other = SP_ITEM (i->data);
221         if (other == item)
222             continue;
224         double dist = unclump_dist (item, other);
225         if (dist > max && fabs (dist) < 1e6) {
226             max = dist;
227             farest = other;
228         }
229     }
231     return farest;
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)
242     Geom::Point it = unclump_center (item);
243     Geom::Point p1 = unclump_center (closest);
245     // perpendicular through closest to the direction to item:
246     Geom::Point perp = Geom::rot90(it - p1);
247     Geom::Point p2 = p1 + perp;
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];
254     // substitute the item into it:
255     double val_item = A * it[Geom::X] + B * it[Geom::Y] + C;
257     GSList *out = NULL;
259     for (GSList *i = rest; i != NULL; i = i->next) {
260         SPItem *other = SP_ITEM (i->data);
262         if (other == item)
263             continue;
265         Geom::Point o = unclump_center (other);
266         double val_other = A * o[Geom::X] + B * o[Geom::Y] + C;
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     }
275     return out;
278 /**
279 Moves \a what away from \a from by \a dist
280  */
281 void
282 unclump_push (SPItem *from, SPItem *what, double dist)
284     Geom::Point it = unclump_center (what);
285     Geom::Point p = unclump_center (from);
286     Geom::Point by = dist * Geom::unit_vector (- (p - it));
288     Geom::Matrix move = Geom::Translate (by);
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     }
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);
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);
301 /**
302 Moves \a what towards \a to by \a dist
303  */
304 void
305 unclump_pull (SPItem *to, SPItem *what, double dist)
307     Geom::Point it = unclump_center (what);
308     Geom::Point p = unclump_center (to);
309     Geom::Point by = dist * Geom::unit_vector (p - it);
311     Geom::Matrix move = Geom::Translate (by);
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     }
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);
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);
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)
333     c_cache.clear();
334     wh_cache.clear();
336     for (GSList *i = items; i != NULL; i = i->next) { //  for each original/clone x: 
337         SPItem *item = SP_ITEM (i->data);
339         GSList *nei = NULL;
341         GSList *rest = g_slist_copy (items);
342         rest = g_slist_remove (rest, item);
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         } 
358         if (g_slist_length (nei) >= 2) {
359             double ave = unclump_average (item, nei);
361             SPItem *closest = unclump_closest (item, nei);
362             SPItem *farest = unclump_farest (item, nei);
364             double dist_closest = unclump_dist (closest, item);
365             double dist_farest = unclump_dist (farest, item);
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);
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     }
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 :