eb5870d2eb77f51dea44c9dcc4e2c7451862f784
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 <algorithm>
15 #include <map>
16 #include "libnr/nr-matrix-ops.h"
17 #include "sp-item.h"
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
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;
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 }
38 NR::Maybe<NR::Rect> r = item->getBounds(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 }
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 NR::Maybe<NR::Rect> r = item->getBounds(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 }
66 return wh;
67 }
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);
80 NR::Point wh1 = unclump_wh (item1);
81 NR::Point wh2 = unclump_wh (item2);
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;
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;
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)));
96 // dist between centers minus angle-adjusted radii
97 double dist_r = (NR::L2 (c2 - c1) - r1 - r2);
99 double stretch1 = wh1[NR::Y]/wh1[NR::X];
100 double stretch2 = wh2[NR::Y]/wh2[NR::X];
102 if ((stretch1 > 1.5 || stretch1 < 0.66) && (stretch2 > 1.5 || stretch2 < 0.66)) {
104 std::vector<double> dists;
105 dists.push_back (dist_r);
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 }
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 }
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 }
159 // return the minimum of all dists
160 return *std::min_element(dists.begin(), dists.end());
161 } else {
162 return dist_r;
163 }
164 }
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;
174 for (GSList *i = others; i != NULL; i = i->next) {
175 SPItem *other = SP_ITEM (i->data);
177 if (other == item)
178 continue;
180 n++;
181 sum += unclump_dist (item, other);
182 }
184 if (n != 0)
185 return sum/n;
186 else
187 return 0;
188 }
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;
198 for (GSList *i = others; i != NULL; i = i->next) {
199 SPItem *other = SP_ITEM (i->data);
201 if (other == item)
202 continue;
204 double dist = unclump_dist (item, other);
205 if (dist < min && fabs (dist) < 1e6) {
206 min = dist;
207 closest = other;
208 }
209 }
211 return closest;
212 }
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;
222 for (GSList *i = others; i != NULL; i = i->next) {
223 SPItem *other = SP_ITEM (i->data);
225 if (other == item)
226 continue;
228 double dist = unclump_dist (item, other);
229 if (dist > max && fabs (dist) < 1e6) {
230 max = dist;
231 farest = other;
232 }
233 }
235 return farest;
236 }
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);
249 // perpendicular through closest to the direction to item:
250 NR::Point perp = NR::rot90(it - p1);
251 NR::Point p2 = p1 + perp;
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];
258 // substitute the item into it:
259 double val_item = A * it[NR::X] + B * it[NR::Y] + C;
261 GSList *out = NULL;
263 for (GSList *i = rest; i != NULL; i = i->next) {
264 SPItem *other = SP_ITEM (i->data);
266 if (other == item)
267 continue;
269 NR::Point o = unclump_center (other);
270 double val_other = A * o[NR::X] + B * o[NR::Y] + C;
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 }
279 return out;
280 }
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));
292 NR::Matrix move = NR::Matrix (NR::translate (by));
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 }
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);
301 sp_item_set_i2d_affine(what, sp_item_i2d_affine(what) * move);
302 sp_item_write_transform(what, SP_OBJECT_REPR(what), what->transform, NULL);
303 }
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);
315 NR::Matrix move = NR::Matrix (NR::translate (by));
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 }
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);
324 sp_item_set_i2d_affine(what, sp_item_i2d_affine(what) * move);
325 sp_item_write_transform(what, SP_OBJECT_REPR(what), what->transform, NULL);
326 }
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();
340 for (GSList *i = items; i != NULL; i = i->next) { // for each original/clone x:
341 SPItem *item = SP_ITEM (i->data);
343 GSList *nei = NULL;
345 GSList *rest = g_slist_copy (items);
346 rest = g_slist_remove (rest, item);
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 }
362 if (g_slist_length (nei) >= 2) {
363 double ave = unclump_average (item, nei);
365 SPItem *closest = unclump_closest (item, nei);
366 SPItem *farest = unclump_farest (item, nei);
368 double dist_closest = unclump_dist (closest, item);
369 double dist_farest = unclump_dist (farest, item);
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);
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 }