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 "libnr/nr-matrix-ops.h"
14 #include "sp-item.h"
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
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;
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 }
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 }
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 }
63 return wh;
64 }
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);
77 Geom::Point wh1 = unclump_wh (item1);
78 Geom::Point wh2 = unclump_wh (item2);
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;
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;
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)));
93 // dist between centers minus angle-adjusted radii
94 double dist_r = (Geom::L2 (c2 - c1) - r1 - r2);
96 double stretch1 = wh1[Geom::Y]/wh1[Geom::X];
97 double stretch2 = wh2[Geom::Y]/wh2[Geom::X];
99 if ((stretch1 > 1.5 || stretch1 < 0.66) && (stretch2 > 1.5 || stretch2 < 0.66)) {
101 std::vector<double> dists;
102 dists.push_back (dist_r);
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 }
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 }
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 }
156 // return the minimum of all dists
157 return *std::min_element(dists.begin(), dists.end());
158 } else {
159 return dist_r;
160 }
161 }
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;
171 for (GSList *i = others; i != NULL; i = i->next) {
172 SPItem *other = SP_ITEM (i->data);
174 if (other == item)
175 continue;
177 n++;
178 sum += unclump_dist (item, other);
179 }
181 if (n != 0)
182 return sum/n;
183 else
184 return 0;
185 }
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;
195 for (GSList *i = others; i != NULL; i = i->next) {
196 SPItem *other = SP_ITEM (i->data);
198 if (other == item)
199 continue;
201 double dist = unclump_dist (item, other);
202 if (dist < min && fabs (dist) < 1e6) {
203 min = dist;
204 closest = other;
205 }
206 }
208 return closest;
209 }
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;
219 for (GSList *i = others; i != NULL; i = i->next) {
220 SPItem *other = SP_ITEM (i->data);
222 if (other == item)
223 continue;
225 double dist = unclump_dist (item, other);
226 if (dist > max && fabs (dist) < 1e6) {
227 max = dist;
228 farest = other;
229 }
230 }
232 return farest;
233 }
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);
246 // perpendicular through closest to the direction to item:
247 Geom::Point perp = Geom::rot90(it - p1);
248 Geom::Point p2 = p1 + perp;
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];
255 // substitute the item into it:
256 double val_item = A * it[Geom::X] + B * it[Geom::Y] + C;
258 GSList *out = NULL;
260 for (GSList *i = rest; i != NULL; i = i->next) {
261 SPItem *other = SP_ITEM (i->data);
263 if (other == item)
264 continue;
266 Geom::Point o = unclump_center (other);
267 double val_other = A * o[Geom::X] + B * o[Geom::Y] + C;
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 }
276 return out;
277 }
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));
289 Geom::Matrix move = Geom::Translate (by);
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 }
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);
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 }
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);
312 Geom::Matrix move = Geom::Translate (by);
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 }
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);
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 }
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();
337 for (GSList *i = items; i != NULL; i = i->next) { // for each original/clone x:
338 SPItem *item = SP_ITEM (i->data);
340 GSList *nei = NULL;
342 GSList *rest = g_slist_copy (items);
343 rest = g_slist_remove (rest, item);
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 }
359 if (g_slist_length (nei) >= 2) {
360 double ave = unclump_average (item, nei);
362 SPItem *closest = unclump_closest (item, nei);
363 SPItem *farest = unclump_farest (item, nei);
365 double dist_closest = unclump_dist (closest, item);
366 double dist_farest = unclump_dist (farest, item);
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);
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 }
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 :