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 */
13 #include <algorithm>
14 #include <map>
15 #include "sp-item.h"
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
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;
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 }
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 }
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 }
64 return wh;
65 }
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);
78 Geom::Point wh1 = unclump_wh (item1);
79 Geom::Point wh2 = unclump_wh (item2);
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;
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;
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)));
94 // dist between centers minus angle-adjusted radii
95 double dist_r = (Geom::L2 (c2 - c1) - r1 - r2);
97 double stretch1 = wh1[Geom::Y]/wh1[Geom::X];
98 double stretch2 = wh2[Geom::Y]/wh2[Geom::X];
100 if ((stretch1 > 1.5 || stretch1 < 0.66) && (stretch2 > 1.5 || stretch2 < 0.66)) {
102 std::vector<double> dists;
103 dists.push_back (dist_r);
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 }
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 }
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 }
157 // return the minimum of all dists
158 return *std::min_element(dists.begin(), dists.end());
159 } else {
160 return dist_r;
161 }
162 }
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;
172 for (GSList *i = others; i != NULL; i = i->next) {
173 SPItem *other = SP_ITEM (i->data);
175 if (other == item)
176 continue;
178 n++;
179 sum += unclump_dist (item, other);
180 }
182 if (n != 0)
183 return sum/n;
184 else
185 return 0;
186 }
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;
196 for (GSList *i = others; i != NULL; i = i->next) {
197 SPItem *other = SP_ITEM (i->data);
199 if (other == item)
200 continue;
202 double dist = unclump_dist (item, other);
203 if (dist < min && fabs (dist) < 1e6) {
204 min = dist;
205 closest = other;
206 }
207 }
209 return closest;
210 }
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;
220 for (GSList *i = others; i != NULL; i = i->next) {
221 SPItem *other = SP_ITEM (i->data);
223 if (other == item)
224 continue;
226 double dist = unclump_dist (item, other);
227 if (dist > max && fabs (dist) < 1e6) {
228 max = dist;
229 farest = other;
230 }
231 }
233 return farest;
234 }
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);
247 // perpendicular through closest to the direction to item:
248 Geom::Point perp = Geom::rot90(it - p1);
249 Geom::Point p2 = p1 + perp;
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];
256 // substitute the item into it:
257 double val_item = A * it[Geom::X] + B * it[Geom::Y] + C;
259 GSList *out = NULL;
261 for (GSList *i = rest; i != NULL; i = i->next) {
262 SPItem *other = SP_ITEM (i->data);
264 if (other == item)
265 continue;
267 Geom::Point o = unclump_center (other);
268 double val_other = A * o[Geom::X] + B * o[Geom::Y] + C;
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 }
277 return out;
278 }
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));
290 Geom::Matrix move = Geom::Translate (by);
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 }
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);
299 what->set_i2d_affine(what->i2d_affine() * move);
300 what->doWriteTransform(SP_OBJECT_REPR(what), what->transform, NULL);
301 }
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);
313 Geom::Matrix move = Geom::Translate (by);
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 }
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);
322 what->set_i2d_affine(what->i2d_affine() * move);
323 what->doWriteTransform(SP_OBJECT_REPR(what), what->transform, NULL);
324 }
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();
338 for (GSList *i = items; i != NULL; i = i->next) { // for each original/clone x:
339 SPItem *item = SP_ITEM (i->data);
341 GSList *nei = NULL;
343 GSList *rest = g_slist_copy (items);
344 rest = g_slist_remove (rest, item);
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 }
360 if (g_slist_length (nei) >= 2) {
361 double ave = unclump_average (item, nei);
363 SPItem *closest = unclump_closest (item, nei);
364 SPItem *farest = unclump_farest (item, nei);
366 double dist_closest = unclump_dist (closest, item);
367 double dist_farest = unclump_dist (farest, item);
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);
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 }
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 :