1 #define INKSCAPE_HELPER_GEOM_CPP
3 /**
4 * Specific geometry functions for Inkscape, not provided my lib2geom.
5 *
6 * Author:
7 * Johan Engelen <goejendaagh@zonnet.nl>
8 *
9 * Copyright (C) 2008 Johan Engelen
10 *
11 * Released under GNU GPL
12 */
14 #include "helper/geom.h"
15 #include "helper/geom-curves.h"
16 #include <typeinfo>
17 #include <2geom/pathvector.h>
18 #include <2geom/path.h>
19 #include <2geom/bezier-curve.h>
20 #include <2geom/hvlinesegment.h>
21 #include <2geom/transforms.h>
22 #include <2geom/rect.h>
23 #include <2geom/coord.h>
24 #include <2geom/sbasis-to-bezier.h>
25 #include <libnr/nr-convert2geom.h>
26 #include <glibmm.h>
28 using Geom::X;
29 using Geom::Y;
31 #define NR_HUGE 1e18
33 //#################################################################################
34 // BOUNDING BOX CALCULATIONS
36 /* Fast bbox calculation */
37 /* Thanks to Nathan Hurst for suggesting it */
38 static void
39 cubic_bbox (Geom::Coord x000, Geom::Coord y000, Geom::Coord x001, Geom::Coord y001, Geom::Coord x011, Geom::Coord y011, Geom::Coord x111, Geom::Coord y111, Geom::Rect &bbox)
40 {
41 Geom::Coord a, b, c, D;
43 bbox[0].extendTo(x111);
44 bbox[1].extendTo(y111);
46 // It already contains (x000,y000) and (x111,y111)
47 // All points of the Bezier lie in the convex hull of (x000,y000), (x001,y001), (x011,y011) and (x111,y111)
48 // So, if it also contains (x001,y001) and (x011,y011) we don't have to compute anything else!
49 // Note that we compute it for the X and Y range separately to make it easier to use them below
50 bool containsXrange = bbox[0].contains(x001) && bbox[0].contains(x011);
51 bool containsYrange = bbox[1].contains(y001) && bbox[1].contains(y011);
53 /*
54 * xttt = s * (s * (s * x000 + t * x001) + t * (s * x001 + t * x011)) + t * (s * (s * x001 + t * x011) + t * (s * x011 + t * x111))
55 * xttt = s * (s2 * x000 + s * t * x001 + t * s * x001 + t2 * x011) + t * (s2 * x001 + s * t * x011 + t * s * x011 + t2 * x111)
56 * xttt = s * (s2 * x000 + 2 * st * x001 + t2 * x011) + t * (s2 * x001 + 2 * st * x011 + t2 * x111)
57 * xttt = s3 * x000 + 2 * s2t * x001 + st2 * x011 + s2t * x001 + 2st2 * x011 + t3 * x111
58 * xttt = s3 * x000 + 3s2t * x001 + 3st2 * x011 + t3 * x111
59 * xttt = s3 * x000 + (1 - s) 3s2 * x001 + (1 - s) * (1 - s) * 3s * x011 + (1 - s) * (1 - s) * (1 - s) * x111
60 * xttt = s3 * x000 + (3s2 - 3s3) * x001 + (3s - 6s2 + 3s3) * x011 + (1 - 2s + s2 - s + 2s2 - s3) * x111
61 * xttt = (x000 - 3 * x001 + 3 * x011 - x111) * s3 +
62 * ( 3 * x001 - 6 * x011 + 3 * x111) * s2 +
63 * ( 3 * x011 - 3 * x111) * s +
64 * ( x111)
65 * xttt' = (3 * x000 - 9 * x001 + 9 * x011 - 3 * x111) * s2 +
66 * ( 6 * x001 - 12 * x011 + 6 * x111) * s +
67 * ( 3 * x011 - 3 * x111)
68 */
70 if (!containsXrange) {
71 a = 3 * x000 - 9 * x001 + 9 * x011 - 3 * x111;
72 b = 6 * x001 - 12 * x011 + 6 * x111;
73 c = 3 * x011 - 3 * x111;
75 /*
76 * s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a;
77 */
78 if (fabs (a) < Geom::EPSILON) {
79 /* s = -c / b */
80 if (fabs (b) > Geom::EPSILON) {
81 double s, t, xttt;
82 s = -c / b;
83 if ((s > 0.0) && (s < 1.0)) {
84 t = 1.0 - s;
85 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
86 bbox[0].extendTo(xttt);
87 }
88 }
89 } else {
90 /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
91 D = b * b - 4 * a * c;
92 if (D >= 0.0) {
93 Geom::Coord d, s, t, xttt;
94 /* Have solution */
95 d = sqrt (D);
96 s = (-b + d) / (2 * a);
97 if ((s > 0.0) && (s < 1.0)) {
98 t = 1.0 - s;
99 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
100 bbox[0].extendTo(xttt);
101 }
102 s = (-b - d) / (2 * a);
103 if ((s > 0.0) && (s < 1.0)) {
104 t = 1.0 - s;
105 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
106 bbox[0].extendTo(xttt);
107 }
108 }
109 }
110 }
112 if (!containsYrange) {
113 a = 3 * y000 - 9 * y001 + 9 * y011 - 3 * y111;
114 b = 6 * y001 - 12 * y011 + 6 * y111;
115 c = 3 * y011 - 3 * y111;
117 if (fabs (a) < Geom::EPSILON) {
118 /* s = -c / b */
119 if (fabs (b) > Geom::EPSILON) {
120 double s, t, yttt;
121 s = -c / b;
122 if ((s > 0.0) && (s < 1.0)) {
123 t = 1.0 - s;
124 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
125 bbox[1].extendTo(yttt);
126 }
127 }
128 } else {
129 /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
130 D = b * b - 4 * a * c;
131 if (D >= 0.0) {
132 Geom::Coord d, s, t, yttt;
133 /* Have solution */
134 d = sqrt (D);
135 s = (-b + d) / (2 * a);
136 if ((s > 0.0) && (s < 1.0)) {
137 t = 1.0 - s;
138 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
139 bbox[1].extendTo(yttt);
140 }
141 s = (-b - d) / (2 * a);
142 if ((s > 0.0) && (s < 1.0)) {
143 t = 1.0 - s;
144 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
145 bbox[1].extendTo(yttt);
146 }
147 }
148 }
149 }
150 }
152 Geom::OptRect
153 bounds_fast_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)
154 {
155 return bounds_exact_transformed(pv, t); //use this as it is faster for now! :)
156 // return Geom::bounds_fast(pv * t);
157 }
159 Geom::OptRect
160 bounds_exact_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)
161 {
162 if (pv.empty())
163 return Geom::OptRect();
165 Geom::Point initial = pv.front().initialPoint() * t;
166 Geom::Rect bbox(initial, initial); // obtain well defined bbox as starting point to unionWith
168 for (Geom::PathVector::const_iterator it = pv.begin(); it != pv.end(); ++it) {
169 bbox.expandTo(it->initialPoint() * t);
171 // don't loop including closing segment, since that segment can never increase the bbox
172 for (Geom::Path::const_iterator cit = it->begin(); cit != it->end_open(); ++cit) {
173 Geom::Curve const &c = *cit;
175 if( is_straight_curve(c) )
176 {
177 bbox.expandTo( c.finalPoint() * t );
178 }
179 else if(Geom::CubicBezier const *cubic_bezier = dynamic_cast<Geom::CubicBezier const *>(&c))
180 {
181 Geom::Point c0 = (*cubic_bezier)[0] * t;
182 Geom::Point c1 = (*cubic_bezier)[1] * t;
183 Geom::Point c2 = (*cubic_bezier)[2] * t;
184 Geom::Point c3 = (*cubic_bezier)[3] * t;
185 cubic_bbox( c0[0], c0[1],
186 c1[0], c1[1],
187 c2[0], c2[1],
188 c3[0], c3[1],
189 bbox );
190 }
191 else
192 {
193 // should handle all not-so-easy curves:
194 Geom::Curve *ctemp = cit->transformed(t);
195 bbox.unionWith( ctemp->boundsExact());
196 delete ctemp;
197 }
198 }
199 }
200 //return Geom::bounds_exact(pv * t);
201 return bbox;
202 }
206 static void
207 geom_line_wind_distance (Geom::Coord x0, Geom::Coord y0, Geom::Coord x1, Geom::Coord y1, Geom::Point const &pt, int *wind, Geom::Coord *best)
208 {
209 Geom::Coord Ax, Ay, Bx, By, Dx, Dy, s;
210 Geom::Coord dist2;
212 /* Find distance */
213 Ax = x0;
214 Ay = y0;
215 Bx = x1;
216 By = y1;
217 Dx = x1 - x0;
218 Dy = y1 - y0;
219 const Geom::Coord Px = pt[X];
220 const Geom::Coord Py = pt[Y];
222 if (best) {
223 s = ((Px - Ax) * Dx + (Py - Ay) * Dy) / (Dx * Dx + Dy * Dy);
224 if (s <= 0.0) {
225 dist2 = (Px - Ax) * (Px - Ax) + (Py - Ay) * (Py - Ay);
226 } else if (s >= 1.0) {
227 dist2 = (Px - Bx) * (Px - Bx) + (Py - By) * (Py - By);
228 } else {
229 Geom::Coord Qx, Qy;
230 Qx = Ax + s * Dx;
231 Qy = Ay + s * Dy;
232 dist2 = (Px - Qx) * (Px - Qx) + (Py - Qy) * (Py - Qy);
233 }
235 if (dist2 < (*best * *best)) *best = sqrt (dist2);
236 }
238 if (wind) {
239 /* Find wind */
240 if ((Ax >= Px) && (Bx >= Px)) return;
241 if ((Ay >= Py) && (By >= Py)) return;
242 if ((Ay < Py) && (By < Py)) return;
243 if (Ay == By) return;
244 /* Ctach upper y bound */
245 if (Ay == Py) {
246 if (Ax < Px) *wind -= 1;
247 return;
248 } else if (By == Py) {
249 if (Bx < Px) *wind += 1;
250 return;
251 } else {
252 Geom::Coord Qx;
253 /* Have to calculate intersection */
254 Qx = Ax + Dx * (Py - Ay) / Dy;
255 if (Qx < Px) {
256 *wind += (Dy > 0.0) ? 1 : -1;
257 }
258 }
259 }
260 }
262 static void
263 geom_cubic_bbox_wind_distance (Geom::Coord x000, Geom::Coord y000,
264 Geom::Coord x001, Geom::Coord y001,
265 Geom::Coord x011, Geom::Coord y011,
266 Geom::Coord x111, Geom::Coord y111,
267 Geom::Point const &pt,
268 Geom::Rect *bbox, int *wind, Geom::Coord *best,
269 Geom::Coord tolerance)
270 {
271 Geom::Coord x0, y0, x1, y1, len2;
272 int needdist, needwind, needline;
274 const Geom::Coord Px = pt[X];
275 const Geom::Coord Py = pt[Y];
277 needdist = 0;
278 needwind = 0;
279 needline = 0;
281 if (bbox) cubic_bbox (x000, y000, x001, y001, x011, y011, x111, y111, *bbox);
283 x0 = MIN (x000, x001);
284 x0 = MIN (x0, x011);
285 x0 = MIN (x0, x111);
286 y0 = MIN (y000, y001);
287 y0 = MIN (y0, y011);
288 y0 = MIN (y0, y111);
289 x1 = MAX (x000, x001);
290 x1 = MAX (x1, x011);
291 x1 = MAX (x1, x111);
292 y1 = MAX (y000, y001);
293 y1 = MAX (y1, y011);
294 y1 = MAX (y1, y111);
296 if (best) {
297 /* Quickly adjust to endpoints */
298 len2 = (x000 - Px) * (x000 - Px) + (y000 - Py) * (y000 - Py);
299 if (len2 < (*best * *best)) *best = (Geom::Coord) sqrt (len2);
300 len2 = (x111 - Px) * (x111 - Px) + (y111 - Py) * (y111 - Py);
301 if (len2 < (*best * *best)) *best = (Geom::Coord) sqrt (len2);
303 if (((x0 - Px) < *best) && ((y0 - Py) < *best) && ((Px - x1) < *best) && ((Py - y1) < *best)) {
304 /* Point is inside sloppy bbox */
305 /* Now we have to decide, whether subdivide */
306 /* fixme: (Lauris) */
307 if (((y1 - y0) > 5.0) || ((x1 - x0) > 5.0)) {
308 needdist = 1;
309 } else {
310 needline = 1;
311 }
312 }
313 }
314 if (!needdist && wind) {
315 if ((y1 >= Py) && (y0 < Py) && (x0 < Px)) {
316 /* Possible intersection at the left */
317 /* Now we have to decide, whether subdivide */
318 /* fixme: (Lauris) */
319 if (((y1 - y0) > 5.0) || ((x1 - x0) > 5.0)) {
320 needwind = 1;
321 } else {
322 needline = 1;
323 }
324 }
325 }
327 if (needdist || needwind) {
328 Geom::Coord x00t, x0tt, xttt, x1tt, x11t, x01t;
329 Geom::Coord y00t, y0tt, yttt, y1tt, y11t, y01t;
330 Geom::Coord s, t;
332 t = 0.5;
333 s = 1 - t;
335 x00t = s * x000 + t * x001;
336 x01t = s * x001 + t * x011;
337 x11t = s * x011 + t * x111;
338 x0tt = s * x00t + t * x01t;
339 x1tt = s * x01t + t * x11t;
340 xttt = s * x0tt + t * x1tt;
342 y00t = s * y000 + t * y001;
343 y01t = s * y001 + t * y011;
344 y11t = s * y011 + t * y111;
345 y0tt = s * y00t + t * y01t;
346 y1tt = s * y01t + t * y11t;
347 yttt = s * y0tt + t * y1tt;
349 geom_cubic_bbox_wind_distance (x000, y000, x00t, y00t, x0tt, y0tt, xttt, yttt, pt, NULL, wind, best, tolerance);
350 geom_cubic_bbox_wind_distance (xttt, yttt, x1tt, y1tt, x11t, y11t, x111, y111, pt, NULL, wind, best, tolerance);
351 } else if (1 || needline) {
352 geom_line_wind_distance (x000, y000, x111, y111, pt, wind, best);
353 }
354 }
356 static void
357 geom_curve_bbox_wind_distance(Geom::Curve const & c, Geom::Matrix const &m,
358 Geom::Point const &pt,
359 Geom::Rect *bbox, int *wind, Geom::Coord *dist,
360 Geom::Coord tolerance, Geom::Rect const *viewbox,
361 Geom::Point &p0) // pass p0 through as it represents the last endpoint added (the finalPoint of last curve)
362 {
363 if( is_straight_curve(c) )
364 {
365 Geom::Point pe = c.finalPoint() * m;
366 if (bbox) {
367 bbox->expandTo(pe);
368 }
369 if (dist || wind) {
370 if (wind) { // we need to pick fill, so do what we're told
371 geom_line_wind_distance (p0[X], p0[Y], pe[X], pe[Y], pt, wind, dist);
372 } else { // only stroke is being picked; skip this segment if it's totally outside the viewbox
373 Geom::Rect swept(p0, pe);
374 if (!viewbox || swept.intersects(*viewbox))
375 geom_line_wind_distance (p0[X], p0[Y], pe[X], pe[Y], pt, wind, dist);
376 }
377 }
378 p0 = pe;
379 }
380 else if(Geom::CubicBezier const *cubic_bezier = dynamic_cast<Geom::CubicBezier const *>(&c)) {
381 Geom::Point p1 = (*cubic_bezier)[1] * m;
382 Geom::Point p2 = (*cubic_bezier)[2] * m;
383 Geom::Point p3 = (*cubic_bezier)[3] * m;
385 // get approximate bbox from handles (convex hull property of beziers):
386 Geom::Rect swept(p0, p3);
387 swept.expandTo(p1);
388 swept.expandTo(p2);
390 if (!viewbox || swept.intersects(*viewbox)) { // we see this segment, so do full processing
391 geom_cubic_bbox_wind_distance ( p0[X], p0[Y],
392 p1[X], p1[Y],
393 p2[X], p2[Y],
394 p3[X], p3[Y],
395 pt,
396 bbox, wind, dist, tolerance);
397 } else {
398 if (wind) { // if we need fill, we can just pretend it's a straight line
399 geom_line_wind_distance (p0[X], p0[Y], p3[X], p3[Y], pt, wind, dist);
400 } else { // otherwise, skip it completely
401 }
402 }
403 p0 = p3;
404 } else {
405 //this case handles sbasis as well as all other curve types
406 Geom::Path sbasis_path = Geom::cubicbezierpath_from_sbasis(c.toSBasis(), 0.1);
408 //recurse to convert the new path resulting from the sbasis to svgd
409 for(Geom::Path::iterator iter = sbasis_path.begin(); iter != sbasis_path.end(); ++iter) {
410 geom_curve_bbox_wind_distance(*iter, m, pt, bbox, wind, dist, tolerance, viewbox, p0);
411 }
412 }
413 }
415 /* Calculates...
416 and returns ... in *wind and the distance to ... in *dist.
417 Returns bounding box in *bbox if bbox!=NULL.
418 */
419 void
420 pathv_matrix_point_bbox_wind_distance (Geom::PathVector const & pathv, Geom::Matrix const &m, Geom::Point const &pt,
421 Geom::Rect *bbox, int *wind, Geom::Coord *dist,
422 Geom::Coord tolerance, Geom::Rect const *viewbox)
423 {
424 if (pathv.empty()) {
425 if (wind) *wind = 0;
426 if (dist) *dist = NR_HUGE;
427 return;
428 }
430 // remember last point of last curve
431 Geom::Point p0(0,0);
433 // remembering the start of subpath
434 Geom::Point p_start(0,0);
435 bool start_set = false;
437 for (Geom::PathVector::const_iterator it = pathv.begin(); it != pathv.end(); ++it) {
439 if (start_set) { // this is a new subpath
440 if (wind && (p0 != p_start)) // for correct fill picking, each subpath must be closed
441 geom_line_wind_distance (p0[X], p0[Y], p_start[X], p_start[Y], pt, wind, dist);
442 }
443 p0 = it->initialPoint() * m;
444 p_start = p0;
445 start_set = true;
446 if (bbox) {
447 bbox->expandTo(p0);
448 }
450 // loop including closing segment if path is closed
451 for (Geom::Path::const_iterator cit = it->begin(); cit != it->end_default(); ++cit) {
452 geom_curve_bbox_wind_distance(*cit, m, pt, bbox, wind, dist, tolerance, viewbox, p0);
453 }
454 }
456 if (start_set) {
457 if (wind && (p0 != p_start)) // for correct picking, each subpath must be closed
458 geom_line_wind_distance (p0[X], p0[Y], p_start[X], p_start[Y], pt, wind, dist);
459 }
460 }
462 //#################################################################################
464 /*
465 * Converts all segments in all paths to Geom::LineSegment or Geom::HLineSegment or
466 * Geom::VLineSegment or Geom::CubicBezier.
467 */
468 Geom::PathVector
469 pathv_to_linear_and_cubic_beziers( Geom::PathVector const &pathv )
470 {
471 Geom::PathVector output;
473 for (Geom::PathVector::const_iterator pit = pathv.begin(); pit != pathv.end(); ++pit) {
474 output.push_back( Geom::Path() );
475 output.back().start( pit->initialPoint() );
476 output.back().close( pit->closed() );
478 for (Geom::Path::const_iterator cit = pit->begin(); cit != pit->end_open(); ++cit) {
479 if( dynamic_cast<Geom::CubicBezier const*>(&*cit) ||
480 is_straight_curve(*cit) )
481 {
482 output.back().append(*cit);
483 }
484 else {
485 // convert all other curve types to cubicbeziers
486 Geom::Path cubicbezier_path = Geom::cubicbezierpath_from_sbasis(cit->toSBasis(), 0.1);
487 output.back().append(cubicbezier_path);
488 }
489 }
490 }
492 return output;
493 }
496 /**
497 * rounds all corners of the rectangle 'outwards', i.e. x0 and y0 are floored, x1 and y1 are ceiled.
498 */
499 void round_rectangle_outwards(Geom::Rect & rect) {
500 Geom::Interval ints[2];
501 for (int i=0; i < 2; i++) {
502 ints[i] = Geom::Interval(std::floor(rect[i][0]), std::ceil(rect[i][1]));
503 }
504 rect = Geom::Rect(ints[0], ints[1]);
505 }
508 namespace Geom {
510 bool transform_equalp(Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon) {
511 return
512 NR_DF_TEST_CLOSE(m0[0], m1[0], epsilon) &&
513 NR_DF_TEST_CLOSE(m0[1], m1[1], epsilon) &&
514 NR_DF_TEST_CLOSE(m0[2], m1[2], epsilon) &&
515 NR_DF_TEST_CLOSE(m0[3], m1[3], epsilon);
516 }
519 bool translate_equalp(Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon) {
520 return NR_DF_TEST_CLOSE(m0[4], m1[4], epsilon) && NR_DF_TEST_CLOSE(m0[5], m1[5], epsilon);
521 }
524 bool matrix_equalp(Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon) {
525 return transform_equalp(m0, m1, epsilon) && translate_equalp(m0, m1, epsilon);
526 }
528 } //end namespace Geom
529 /*
530 The following predefined objects are for reference
531 and comparison.
532 */
533 Geom::Matrix GEOM_MATRIX_IDENTITY = Geom::identity();
535 /*
536 Local Variables:
537 mode:c++
538 c-file-style:"stroustrup"
539 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
540 indent-tabs-mode:nil
541 fill-column:99
542 End:
543 */
544 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :