BoundingBox calculation fails in certain cases #224

Closed
timo22345 opened this Issue Feb 20, 2014 · 3 comments

Projects

None yet

2 participants

@timo22345

Bounding box calculation fails in this case:

var path = new Path("M185.3, 162.5 C 30.900000000000002,228.29999999999998,49.36666666666666,211.66666666666666,240.7,112.6");
path.attr({
    fillColor: "#FFAAAA",
    strokeColor: "black",
    strokeWidth: 1
  });
path.addTo(stage);
var bounds = path.getBoundingBox();
console.log(JSON.stringify(bounds));
new Rect(100, 100, 100, 100).attr({
    fillColor: "transparent",
    strokeColor: "red",
    strokeWidth: 1,
    x: bounds.left,
    y: bounds.top,
    width: bounds.width,
    height: bounds.height
}).addTo(stage);

The same in playground here.

Red rectangle shows calculated bbox position. It has wrong left value.

@timo22345

This should do the trick (Tests: http://jsbin.com/ivomiq/56/, http://jsbin.com/hotakayi/1/ ):

// Source: http://blog.hackers-cafe.net/2009/06/how-to-calculate-bezier-curves-bounding.html
// Original version: NISHIO Hirokazu
// Modifications: Timo
function getBoundsOfCurve (x0, y0, x1, y1, x2, y2, x3, y3)
{
  var tvalues = [], bounds = [new Array(6), new Array(6)],
      a,b,c,t,t1,t2,b2ac,sqrtb2ac;
  for (var i = 0; i < 2; ++i)
  {
    if (i==0)
    {
      b = 6 * x0 - 12 * x1 + 6 * x2;
      a = -3 * x0 + 9 * x1 - 9 * x2 + 3 * x3;
      c = 3 * x1 - 3 * x0;
    }
    else
    {
      b = 6 * y0 - 12 * y1 + 6 * y2;
      a = -3 * y0 + 9 * y1 - 9 * y2 + 3 * y3;
      c = 3 * y1 - 3 * y0;
    }
    if (abs(a) < 1e-12)
    {
      if (abs(b) < 1e-12) continue;
      t = -c / b;
      if (0 < t && t < 1) tvalues.push(t);
      continue;
    }
    b2ac = b*b - 4 * c * a;
    sqrtb2ac = sqrt(b2ac);
    if (b2ac < 0) continue;
    t1 = (-b + sqrtb2ac) / (2 * a);
    if (0 < t1 && t1 < 1) tvalues.push(t1);
    t2 = (-b - sqrtb2ac) / (2 * a);
    if (0 < t2 && t2 < 1) tvalues.push(t2);
  }

  var j = tvalues.length, jlen = j, mt;
  while(j--)
  {
    t = tvalues[j]; 
    mt = 1-t;
    bounds[0][j] = (mt*mt*mt*x0) + (3*mt*mt*t*x1) + (3*mt*t*t*x2) + (t*t*t*x3);
    bounds[1][j] = (mt*mt*mt*y0) + (3*mt*mt*t*y1) + (3*mt*t*t*y2) + (t*t*t*y3);
  }

  //tvalues[jlen] = 0;
  //tvalues[jlen+1] = 1;
  bounds[0][jlen] = x0;
  bounds[1][jlen] = y0;
  bounds[0][jlen+1] = x3;
  bounds[1][jlen+1] = y3;
  bounds[0].length = bounds[1].length = jlen+2;

  return {
    left: min.apply(null, bounds[0]),
    top: min.apply(null, bounds[1]),
    right: max.apply(null, bounds[0]),
    bottom: max.apply(null, bounds[1])
  };
};

EDIT: Removed unnecessary x,y and commented tvalues[jlen] = 0; and tvalues[jlen+1] = 1;. I used x, y to get the real bound coordinates, but when only bounding box is needed, they are unnecessary. I have used this function to get local extremes (to split cubic on them for use in cubic flattening to lines) in which case it was needed to return only tvalues array.

@basecode
Member

Thanks @timo22345! Will investigate soon.

@basecode
Member
basecode commented Jun 8, 2014

Hi @timo22345, thanks for taking the time to report this issue. I investigated a little bit further and found out that casting the intermediate results "a", "b" and "c" to int also fixes the issue. I added visual and unit tests. Do you see any problems with my fix?

I searched for the string "http://blog.hackers-cafe.net/2009/06/how-to-calculate-bezier-curves-bounding.html" on Github an found several other implementations. Other implementations store the intermediate result as doubles or int. That got me to deal with that approach, too.

@davidaurelio davidaurelio closed this in #227 Aug 28, 2014
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment