src/helper/geom.cpp

   1 #define INKSCAPE_HELPER_GEOM_CPP\r
   2 \r
   3 /**\r
   4  * Specific geometry functions for Inkscape, not provided my lib2geom.\r
   5  *\r
   6  * Author:\r
   7  *   Johan Engelen <goejendaagh@zonnet.nl>\r
   8  *\r
   9  * Copyright (C) 2008 Johan Engelen\r
  10  *\r
  11  * Released under GNU GPL\r
  12  */\r
  13 \r
  14 #include "helper/geom.h"\r
  15 \r
  16 #include <2geom/pathvector.h>\r
  17 #include <2geom/transforms.h>\r
  18 #include <2geom/rect.h>\r
  19 #include <2geom/coord.h>\r
  20 \r
  21 /* Fast bbox calculation */\r
  22 /* Thanks to Nathan Hurst for suggesting it */\r
  23 static void\r
  24 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)\r
  25 {\r
  26     Geom::Coord a, b, c, D;\r
  27 \r
  28     bbox[0].extendTo(x111);\r
  29     bbox[1].extendTo(y111);\r
  30 \r
  31     /*\r
  32      * xttt = s * (s * (s * x000 + t * x001) + t * (s * x001 + t * x011)) + t * (s * (s * x001 + t * x011) + t * (s * x011 + t * x111))\r
  33      * xttt = s * (s2 * x000 + s * t * x001 + t * s * x001 + t2 * x011) + t * (s2 * x001 + s * t * x011 + t * s * x011 + t2 * x111)\r
  34      * xttt = s * (s2 * x000 + 2 * st * x001 + t2 * x011) + t * (s2 * x001 + 2 * st * x011 + t2 * x111)\r
  35      * xttt = s3 * x000 + 2 * s2t * x001 + st2 * x011 + s2t * x001 + 2st2 * x011 + t3 * x111\r
  36      * xttt = s3 * x000 + 3s2t * x001 + 3st2 * x011 + t3 * x111\r
  37      * xttt = s3 * x000 + (1 - s) 3s2 * x001 + (1 - s) * (1 - s) * 3s * x011 + (1 - s) * (1 - s) * (1 - s) * x111\r
  38      * xttt = s3 * x000 + (3s2 - 3s3) * x001 + (3s - 6s2 + 3s3) * x011 + (1 - 2s + s2 - s + 2s2 - s3) * x111\r
  39      * xttt = (x000 - 3 * x001 + 3 * x011 -     x111) * s3 +\r
  40      *        (       3 * x001 - 6 * x011 + 3 * x111) * s2 +\r
  41      *        (                  3 * x011 - 3 * x111) * s  +\r
  42      *        (                                 x111)\r
  43      * xttt' = (3 * x000 - 9 * x001 +  9 * x011 - 3 * x111) * s2 +\r
  44      *         (           6 * x001 - 12 * x011 + 6 * x111) * s  +\r
  45      *         (                       3 * x011 - 3 * x111)\r
  46      */\r
  47 \r
  48     a = 3 * x000 - 9 * x001 + 9 * x011 - 3 * x111;\r
  49     b = 6 * x001 - 12 * x011 + 6 * x111;\r
  50     c = 3 * x011 - 3 * x111;\r
  51 \r
  52     /*\r
  53      * s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a;\r
  54      */\r
  55     if (fabs (a) < Geom::EPSILON) {\r
  56         /* s = -c / b */\r
  57         if (fabs (b) > Geom::EPSILON) {\r
  58             double s, t, xttt;\r
  59             s = -c / b;\r
  60             if ((s > 0.0) && (s < 1.0)) {\r
  61                 t = 1.0 - s;\r
  62                 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;\r
  63                 bbox[0].extendTo(xttt);\r
  64             }\r
  65         }\r
  66     } else {\r
  67         /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */\r
  68         D = b * b - 4 * a * c;\r
  69         if (D >= 0.0) {\r
  70             Geom::Coord d, s, t, xttt;\r
  71             /* Have solution */\r
  72             d = sqrt (D);\r
  73             s = (-b + d) / (2 * a);\r
  74             if ((s > 0.0) && (s < 1.0)) {\r
  75                 t = 1.0 - s;\r
  76                 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;\r
  77                 bbox[0].extendTo(xttt);\r
  78             }\r
  79             s = (-b - d) / (2 * a);\r
  80             if ((s > 0.0) && (s < 1.0)) {\r
  81                 t = 1.0 - s;\r
  82                 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;\r
  83                 bbox[0].extendTo(xttt);\r
  84             }\r
  85         }\r
  86     }\r
  87 \r
  88     a = 3 * y000 - 9 * y001 + 9 * y011 - 3 * y111;\r
  89     b = 6 * y001 - 12 * y011 + 6 * y111;\r
  90     c = 3 * y011 - 3 * y111;\r
  91 \r
  92     if (fabs (a) < Geom::EPSILON) {\r
  93         /* s = -c / b */\r
  94         if (fabs (b) > Geom::EPSILON) {\r
  95             double s, t, yttt;\r
  96             s = -c / b;\r
  97             if ((s > 0.0) && (s < 1.0)) {\r
  98                 t = 1.0 - s;\r
  99                 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;\r
 100                 bbox[1].extendTo(yttt);\r
 101             }\r
 102         }\r
 103     } else {\r
 104         /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */\r
 105         D = b * b - 4 * a * c;\r
 106         if (D >= 0.0) {\r
 107             Geom::Coord d, s, t, yttt;\r
 108             /* Have solution */\r
 109             d = sqrt (D);\r
 110             s = (-b + d) / (2 * a);\r
 111             if ((s > 0.0) && (s < 1.0)) {\r
 112                 t = 1.0 - s;\r
 113                 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;\r
 114                 bbox[1].extendTo(yttt);\r
 115             }\r
 116             s = (-b - d) / (2 * a);\r
 117             if ((s > 0.0) && (s < 1.0)) {\r
 118                 t = 1.0 - s;\r
 119                 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;\r
 120                 bbox[1].extendTo(yttt);\r
 121             }\r
 122         }\r
 123     }\r
 124 }\r
 125 \r
 126 Geom::Rect\r
 127 bounds_fast_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)\r
 128 {\r
 129     return bounds_exact_transformed(pv, t); //use this as it is faster for now! :)\r
 130 //    return Geom::bounds_fast(pv * t);\r
 131 }\r
 132 \r
 133 Geom::Rect\r
 134 bounds_exact_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)\r
 135 {\r
 136     Geom::Rect bbox;\r
 137     \r
 138     if (pv.empty())\r
 139         return bbox;\r
 140 \r
 141     Geom::Curve *temp = pv.front().front().transformed(t);\r
 142     bbox = temp->boundsExact();\r
 143     delete temp;\r
 144 \r
 145     for (Geom::PathVector::const_iterator it = pv.begin(); it != pv.end(); ++it) {\r
 146         bbox.expandTo(it->initialPoint() * t);\r
 147 \r
 148         // don't loop including closing segment, since that segment can never increase the bbox\r
 149         for (Geom::Path::const_iterator cit = it->begin(); cit != it->end_open(); ++cit) {\r
 150             Geom::Curve const *c = &*cit;\r
 151 \r
 152             if(Geom::LineSegment const *line_segment = dynamic_cast<Geom::LineSegment const *>(c))\r
 153             {\r
 154                 bbox.expandTo( (*line_segment)[1] * t );\r
 155             }\r
 156             else if(Geom::CubicBezier const *cubic_bezier = dynamic_cast<Geom::CubicBezier const  *>(c))\r
 157             {\r
 158                 Geom::Point c0 = (*cubic_bezier)[0] * t;\r
 159                 Geom::Point c1 = (*cubic_bezier)[1] * t;\r
 160                 Geom::Point c2 = (*cubic_bezier)[2] * t;\r
 161                 Geom::Point c3 = (*cubic_bezier)[3] * t;\r
 162                 cubic_bbox( c0[0], c0[1],\r
 163                             c1[0], c1[1],\r
 164                             c2[0], c2[1],\r
 165                             c3[0], c3[1],\r
 166                             bbox );\r
 167             }\r
 168             else\r
 169             {\r
 170                 // should handle all not-so-easy curves:\r
 171                 Geom::Curve *ctemp = cit->transformed(t);\r
 172                 bbox.unionWith( ctemp->boundsExact());\r
 173                 delete ctemp;\r
 174             }\r
 175         }\r
 176     }\r
 177     //return Geom::bounds_exact(pv * t);\r
 178     return bbox;\r
 179 }\r
 180 \r
 181 /*\r
 182   Local Variables:\r
 183   mode:c++\r
 184   c-file-style:"stroustrup"\r
 185   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))\r
 186   indent-tabs-mode:nil\r
 187   fill-column:99\r
 188   End:\r
 189 */\r
 190 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :\r