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