{"id":205,"date":"2009-10-09T15:46:03","date_gmt":"2009-10-09T14:46:03","guid":{"rendered":"http:\/\/floris.briolas.nl\/floris\/?p=205"},"modified":"2009-11-05T20:05:08","modified_gmt":"2009-11-05T19:05:08","slug":"bounding-box-of-cubic-bezier","status":"publish","type":"post","link":"https:\/\/floris.briolas.nl\/floris\/2009\/10\/bounding-box-of-cubic-bezier\/","title":{"rendered":"Calculating \/ Computing the Bounding Box of Cubic Bezier"},"content":{"rendered":"<p>Goal: Showing an algo that computes the Bounding box of a cubic bezier.<br \/>\nAudience: Needs some basic Math, Derivative, solving parabola, knowledge of computer language.<br \/>\nSample in c# : coming soon, at bottom of article.<\/p>\n<p>This is also my first usage of a HTML5 element, so IE users sorry!<\/p>\n<p>If you are NOT familiar with what a cubic bezier is, please <a href=\"http:\/\/en.wikipedia.org\/wiki\/B%C3%A9zier_curve\">look at this wiki page<\/a>.<\/p>\n<p>If you use the start and end point of a cubic bezier and both of the controlpoints, you will end up with a box. This box will contain the bezier, but it&#8217;s not really tight. You want a tight bb (bounding box). The controlpoints of the bezier may lay outside the bb.<\/p>\n<p>This example is shows a working example  (if the HTML5 canvas element is supported you&#8217;ll see a interactive demonstration) :<\/p>\n<p><!-- example --><\/p>\n<style type=\"text\/css\"><!--\n#container { position: relative; }\n#imageView { border: 1px solid #000; }\n-->\n<\/style>\n<div id=\"container\">\n<canvas id=\"imageView\" width=\"400\" height=\"300\"><\/p>\n<p>Sorry the CANVAS tag is not supported by your browser (are you browsing with IE??) \ud83d\ude41<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" src=\"http:\/\/floris.briolas.nl\/floris\/wp-content\/uploads\/2009\/10\/exampleCubicBezier.png\" alt=\"exampleCubicBezier\" title=\"exampleCubicBezier\" width=\"400\" height=\"300\" class=\"alignleft size-full wp-image-217\" srcset=\"https:\/\/floris.briolas.nl\/floris\/wp-content\/uploads\/2009\/10\/exampleCubicBezier.png 400w, https:\/\/floris.briolas.nl\/floris\/wp-content\/uploads\/2009\/10\/exampleCubicBezier-300x225.png 300w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><br \/>\n<\/canvas>\n<\/div>\n<p><script src=\"\/floris\/my_js\/CubicBezier.js\"><\/script><br \/>\n<script>init();<\/script><br \/>\n<!-- example  done--><\/p>\n<p>So how to do this?<\/p>\n<p>You&#8217;ll need to know the function of the cubic bezier. Defined as:<br \/>\nf(t) = a*t^3 + b*t^2 + c*t +d<br \/>\nwhere<br \/>\nd = P0<br \/>\nc = 3*P1-3*P0<br \/>\nb = 3*P2-6*P1+3*P0<br \/>\na = P3-3*P2+3*P1-P0<\/p>\n<p>p0 and p3 are the begin and end point of the bezier, p1 &#038; p2 the control points. This function is defined for t=[0..1] so (0, 0.00001, 0.00002, &#8230; 0.99999)<\/p>\n<p>Code to draw bezier point by point<\/p>\n<pre name=\"code\" class=\"c#\">\r\n\r\nprotected override void OnPaint(PaintEventArgs pe)\r\n{\r\n  Func&lt;double, double, double, double, double, double&gt; bezierSpline = (p0, p1, p2, p3, t) =&gt;\r\n                (p3 - 3 * p2 + 3 * p1 - p0) * Math.Pow(t, 3)\r\n                + (3 * p2 - 6 * p1 + 3 * p0) * Math.Pow(t, 2)\r\n                + (3 * p1 - 3 * p0) * t\r\n                + (p0);\r\n\r\n\r\n  for (double t = 0; t <= 1; t += 0.001) \/\/adjust if you want\r\n  {\r\n    double x = bezierSpline(_points[0].X, _points[1].X, _points[2].X, _points[3].X, t);\r\n    double y = bezierSpline(_points[0].Y, _points[1].Y, _points[2].Y, _points[3].Y, t); ;\r\n\r\n    var p = new PointF((float)x, (float)y);\r\n    drawPoint(pe.Graphics, p, Color.Orange, 2);\r\n  }\r\n}\r\n\r\nprivate void drawPoint(Graphics g, PointF p, Color color, float size)\r\n{\r\n  Brush b = new SolidBrush(color);\r\n  float w = size;\r\n  RectangleF r = new RectangleF(p.X-(w\/2f),p.Y-(w\/2f),w,w);\r\n  g.FillEllipse(b,r);\r\n  b.Dispose();                \r\n}\/\/this code snippet has been cut-n-pasted from project, may contain some err..\r\n<\/pre>\n<p>A possible way to compute bb is to add each point to bb evaluation, and you need plenty to ensure the exactness of the bb! Don't do this! Unless you want to do TDD and test if the bb is nearly the same as the bb you are about to compute for testing purposes.<\/p>\n<h3>Derivative<\/h3>\n<p>The exact solution can be found by using math. if you derivative the bezier function you can find <a href=\"http:\/\/en.wikipedia.org\/wiki\/Maxima_and_minima\">local extremes<\/a>.<\/p>\n<p>so<br \/>\nf(t) = a*t3 + b*t2 + c*t +d<br \/>\nbecomes :<br \/>\nf(t)' = 3a*t^2 + 2b*t + c<\/p>\n<p>Do not forget the values of a,b and c! as defined above.<\/p>\n<p>If you find the where f(t)'=0 then you'll find local extremes. To do this you'll need to find where the parabola equals 0 for each of the axises. You'll need to solve the parabola (f(t)' is now a parabola!) for the x and y values of your points.<\/p>\n<p>To find out if there is a solution we'll use the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Discriminant\">discriminant (Quadratic formula)<\/a> b^2-4ac. This will tell you if there is a solution. <\/p>\n<p>Example:<br \/>\nsuppose points:<br \/>\np0 = (30,70)<br \/>\np1 = (0,270)<br \/>\np2 = (290,110)<br \/>\np3 = (200, 100)<\/p>\n<p>f(t)' = 3a*t^2 + 2b*t + c<\/p>\n<p>with:<\/p>\n<p>a = P3-3*P2+3*P1-P0<br \/>\nb = 3*P2-6*P1+3*P0<br \/>\nc = 3*P1-3*P0<\/p>\n<p>becomes:<\/p>\n<p>f(t)' = 3(P3-3*P2+3*P1-P0)*t^2 + 2(3*P2-6*P1+3*P0)*t + (3*P1-3*P0)<\/p>\n<p>\/\/solution for x values:<br \/>\na = 3(200-3*290+3*0-30)  = -2100<br \/>\nb = 2(3*P2-6*P1+3*P0) = 1920<br \/>\nc = (3*P1-3*P0) = -90<\/p>\n<p>with D = b^2-4ac<br \/>\nD=2930400<br \/>\nD>0 so there are 2 solutions<\/p>\n<p>you can calculate the solution with <strong>(-b + sqrt(b^2 - 4ac)) \/ 2a<\/strong> and <strong>(-b - sqrt(b^2 - 4ac)) \/ 2a<\/strong>.<\/p>\n<p>s1 = 0.04956 s2 = 0.86472<\/p>\n<p>do the same for the Y values<br \/>\nyou'll come to:<br \/>\na=1530<br \/>\nb=-2160<br \/>\nc=600<\/p>\n<p>D=993600 so 2 solutions<\/p>\n<p>s1=1.03163<br \/>\ns2=0.38013<\/p>\n<p>!!You'll need to throw away the first solution of 1.03163, since the bezier function is only defined between 0 and 1!<\/p>\n<p>us the solutions you came up as params for the original bezier function.<br \/>\nso :<br \/>\n\/\/s1 = 0.04956 s2 = 0.86472<br \/>\nx1 = f(0.04956) => 27.8<br \/>\ny1 = f(0.04956) => 97.1<\/p>\n<p>x2 = f(0.86472) => 217.3<br \/>\ny2 = f(0.86472) => 111.0<\/p>\n<p>\/\/s1=1.03163 s2=0.38013<br \/>\nx3 = f(0.38013) => 96.0<br \/>\ny3 = f(0.38013) => 170.0<\/p>\n<p>ok,.. now you have the local extremes! And evaluation of the bb is next.<\/p>\n<h3>The Bounding Box<\/h3>\n<p>Take the start and end point, include the local extremes.<\/p>\n<p>find the smallest x and y value<br \/>\nfind the largest x and y value.<\/p>\n<p>there you have your bb!<\/p>\n<p>Now there is a small trap,..<br \/>\nyour p0..p3 can be placed in such a way that for the f(t)'  a becomes 0. When this happens the function is no longer a parabola, but a line.<br \/>\nf(t)' = at^2 + bt + c<br \/>\nf(t)' = <del datetime=\"2009-10-09T14:40:00+00:00\">at^2<\/del> + bt + c<br \/>\nf(t)' = bt + c<br \/>\n-bt= c<br \/>\n-t = c\/b<br \/>\nt = -c\/b<\/p>\n<p>that is all you'll need to solve the bb of a bezier!<\/p>\n<p><!--more--><\/p>\n<p>Here is some c# code :<\/p>\n<pre name=\"code\" class=\"csharp\">\r\nusing System;\r\nusing System.Collections.Generic;\r\nusing System.Linq;\r\nusing System.Text;\r\nusing System.Drawing;\r\n\r\nnamespace BoundingBoxTestProject\r\n{\r\npublic static class BezierOp\r\n{\r\n    public delegate TResult Func&lt;T1, T2, T3, T4, T5, TResult&gt;(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5);\r\n\r\n    \/\/cubic polinomal\r\n    \/\/x = At^3 + Bt^2 + Ct + D\r\n    \/\/where A,B,C,D:\r\n    \/\/A = p3 -3 * p2 + 3 * p1 - p0\r\n    \/\/B = 3 * p2 - 6 * p1 +3 * p0\r\n    \/\/C = 3 * p1 - 3 * p0\r\n    \/\/D = p0            \r\n    public static Func&lt;double, double, double, double, double, double&gt; bezierSpline = (p0, p1, p2, p3, t) =&gt;\r\n                                                                        (p3 - 3 * p2 + 3 * p1 - p0) * Math.Pow(t, 3)\r\n                                                                        + (3 * p2 - 6 * p1 + 3 * p0) * Math.Pow(t, 2)\r\n                                                                        + (3 * p1 - 3 * p0) * t\r\n                                                                        + (p0);\r\n\r\n    \/\/X = At^3 + Bt^2 + Ct + D\r\n    \/\/where A,B,C,D:\r\n    \/\/A = (p3 -3 * p2 + 3 * p1 - p0)\r\n    \/\/B = (3 * p2 - 6 * p1 +3 * p0)\r\n    \/\/C = (3 * p1 - 3 * p0)\r\n    \/\/D = (p0)\r\n\r\n    \/\/We would like to know the values of t where X = 0\r\n    \/\/X  = (p3-3*p2+3*p1-p0)t^3 + (3*p2-6*p1+3*p0)t^2 + (3*p1-3*p0)t + (p0)\r\n    \/\/Derivetive :\r\n    \/\/X' = 3(p3-3*p2+3*p1-p0)t^(3-1) + 2(6*p2-12*p1+6*p0)t^(2-1) + 1(3*p1-3*p0)t^(1-1)              [f(x)=aX^n =&gt; f'(x)=a*n*X^(n-1)  remember?]\r\n    \/\/simplified:\r\n    \/\/X' = (3*p3-9*p2+9*p1-3*p0)t^2 + (6*p2-12*p1+6*p0)t + (3*p1-3*p0)\r\n    \/\/**!!reusing a,b,and c!!!***\r\n    \/\/taken as aX^2 + bX + c  a,b and c are:          \r\n    public static Func&lt;double, double, double, double, double&gt; A = (p0, p1, p2, p3) =&gt; 3 * p3 - 9 * p2 + 9 * p1 - 3 * p0;\r\n    \/\/ommitting power 2 for now            \r\n    public static Func&lt;double, double, double, double&gt; B = (p0, p1, p2) =&gt; 6 * p2 - 12 * p1 + 6 * p0;\r\n    public static Func&lt;double, double, double&gt; C = (p0, p1) =&gt; 3 * p1 - 3 * p0;\r\n\r\n    \/\/b^2 - 4ac = Determinant\r\n    public static Func&lt;double, double, double, double&gt; Determinant = (a, b, c) =&gt; Math.Pow(b, 2) - 4d * a * c;\r\n\r\n    public static Func&lt;double, double, double, double[]&gt; Solve = (a, b, c) =&gt;\r\n                                                       {\r\n                                                           Func&lt;double, double, double, bool, double&gt; _Solve =\r\n                                                               (a_, b_, c_, s) =&gt;\r\n                                                               (-b_ +\r\n                                                                (Math.Sqrt((b_ * b_) - (4d * a_ * c_)) *\r\n                                                                 ((s) ? 1d : -1d))) \/ (2d * a_);\r\n\r\n                                                           double d = Determinant(a, b, c);\r\n                                                           if (d &lt; 0)\r\n                                                               return new double[] { };\r\n\r\n                                                           if (a == 0)\r\n                                                               \/\/aX^2 + bX + c well then then this is a simple line\r\n                                                               \/\/x= -c \/ b\r\n                                                               return new double[] { -c \/ b };\r\n\r\n                                                           if (d == 0)\r\n                                                           {\r\n                                                               return new double[] { _Solve(a, b, c, true) };\r\n                                                           }\r\n                                                           else\r\n                                                               return new double[]\r\n                                                                  {\r\n                                                                      _Solve(a, b, c, true),\r\n                                                                      _Solve(a, b, c, false)\r\n                                                                  };\r\n                                                       };\r\n\r\n    public static RectangleF GetRect(PointF p1, PointF c1, PointF c2, PointF p2)\r\n    {\r\n        double aX = A(p1.X, c1.X, c2.X, p2.X);\r\n        double bX = B(p1.X, c1.X, c2.X);\r\n        double cX = C(p1.X, c1.X);\r\n\r\n        double aY = A(p1.Y, c1.Y, c2.Y, p2.Y);\r\n        double bY = B(p1.Y, c1.Y, c2.Y);\r\n        double cY = C(p1.Y, c1.Y);\r\n\r\n        var resX = Solve(aX, bX, cX).Where(t =&gt; (t &gt;= 0) && (t &lt;= 1)); \/\/solve for t ==0 & filter\r\n        var resY = Solve(aY, bY, cY).Where(t =&gt; (t &gt;= 0) && (t &lt;= 1)); \/\/solve for t ==0 & filter\r\n\r\n        \/\/Draw min and max;\r\n\r\n        List&lt;PointF&gt; _BBox = new List&lt;PointF&gt;();\r\n        _BBox.Add(p1); \/\/Add Begin and end point not the control points!\r\n        _BBox.Add(p2);\r\n\r\n        foreach (var e in resX.Union(resY))\r\n        {\r\n            double x = bezierSpline(p1.X, c1.X, c2.X, p2.X, e);\r\n            double y = bezierSpline(p1.Y, c1.Y, c2.Y, p2.Y, e);\r\n\r\n            PointF p = new PointF((float)x, (float)y);\r\n            _BBox.Add(p);\r\n        }\r\n\r\n        float minX = float.MaxValue;\r\n        float minY = float.MaxValue;\r\n        float maxX = float.MinValue;\r\n        float maxY = float.MinValue;\r\n\r\n        foreach (var e in _BBox) \/\/find the bounding box.\r\n        {\r\n            minX = Math.Min(e.X, minX);\r\n            minY = Math.Min(e.Y, minY);\r\n            maxX = Math.Max(e.X, maxX);\r\n            maxY = Math.Max(e.Y, maxY);\r\n        }\r\n\r\n        return new RectangleF(minX, minY, maxX - minX, maxY - minY);\r\n    }\r\n\r\n}\r\n\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Goal: Showing an algo that computes the Bounding box of a cubic bezier. Audience: Needs some basic Math, Derivative, solving parabola, knowledge of computer language. Sample in c# : coming soon, at bottom of article. This is also my first usage of a HTML5 element, so IE users sorry! If you are NOT familiar with [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_newsletter_tier_id":0,"jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[3],"tags":[7],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p61yPs-3j","_links":{"self":[{"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/posts\/205"}],"collection":[{"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/comments?post=205"}],"version-history":[{"count":33,"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/posts\/205\/revisions"}],"predecessor-version":[{"id":262,"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/posts\/205\/revisions\/262"}],"wp:attachment":[{"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/media?parent=205"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/categories?post=205"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/floris.briolas.nl\/floris\/wp-json\/wp\/v2\/tags?post=205"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}