0

Please see the image below. image below This path object is created using 4 Bezier curve on each side. Currently I am facing a problem when I try to get bounds of this path object created using cubic brazier curves. As you can see top and bottom sides have control point away from the curve which makes bounds totally inaccurate.

So my question is is it possible to create a jigsaw puzzle piece like in the image having all control points on or at the level of the curve. ( That is creating a curve and perfect mirror of it, all points within the bounds of the curve)

pats
  • 1,273
  • 2
  • 20
  • 43
  • You could try to `Flatten` a copy of the path and use its bounds. If you move the control points the curve will change a lot! – TaW Sep 28 '17 at 10:25
  • Issues is not calculating bounds. I have already done that by flattening. I am using java/android functionality to use this path as a mask and then overlay the puzzle picture on it to generate the puzzle. That functionality uses these bounds as a consequence I encounter this problem. Easiest way is to move the control points within the bounds if possible. Any workaround? – pats Sep 28 '17 at 10:29

3 Answers3

1

Don't calculate the bounds by using the control points, then. At least if you need tight bounds and don't want a quick check for potential visibility in a given clipping rectangle. This awesome site can help a lot with common Bézier curve calculations, including bounding box.

Alternatively, switch to splines where the control points are on the curve, but then you could end up with the opposite effect where the curve extends beyond the bounds imposed by its control points.

Joey
  • 344,408
  • 85
  • 689
  • 683
  • Thanks for your response. I already implemented algo to estimate real bounds. But I am using java/android funcitonality to use this path as a mask and then overlay the puzzle picture on it to generate the puzzle. That functionality uses these bounds as a consequence I encounter this problem. Easiest way is to move the control points within the bounds if possible. Any workaround? – pats Sep 28 '17 at 10:24
  • Approximate the curve with a polyline. Or split the curve on the outermost points in each direction so that the control points are no longer outside. If you can approximate the curve, then finding that point shouldn't be difficult. For everything else, the link should provide the answer. – Joey Sep 28 '17 at 10:33
0

You can easily convert your BEZIER cubic control points into Interpolation cubic. Just by reversing this:

so:

/*                              bezier = interpol
1  |                           (    x0)=X1;
t  |                  (3.0*x1)-(3.0*x0)=(0.5*(X2-X0));
tt |         (3.0*x2)-(6.0*x1)+(3.0*x0)=(3.0*(X2-X1))-(X2-X0)-(0.5*(X3-X1));
ttt|(    x3)-(3.0*x2)+(3.0*x1)-(    x0)=(0.5*(X2-X0))+(0.5*(X3-X1))+(2.0*(-X2+X1));
1  |                           (    y0)=Y1;
t  |                  (3.0*y1)-(3.0*y0)=(0.5*(Y2-Y0));
tt |         (3.0*y2)-(6.0*y1)+(3.0*y0)=(3.0*(Y2-Y1))-(Y2-Y0)-(0.5*(Y3-Y1));
ttt|(    y3)-(3.0*y2)+(3.0*y1)-(    y0)=(0.5*(Y2-Y0))+(0.5*(Y3-Y1))+(2.0*(-Y2+Y1));
*/

// input: x0,y0,..x3,y3 ... Bezier control points
// output: X0,Y0,..X3,Y3  ... interpolation control points
    double x0,y0,x1,y1,x2,y2,x3,y3,m=1.0/9.0;
    X0=x0-(x1-x0)/m; Y0=y0-(y1-y0)/m;
    X1=x0;           Y1=y0;
    X2=x3;           Y2=y3;
    X3=x3+(x3-x2)/m; Y3=y3+(y3-y2)/m;

Hope I did not make any algebraic mistake. This will move all control points into your curves directly while the shape will be unchanged. Beware that for BBOX computation you should only use (X1,Y1) and (X2,Y2) as the used parameter t=<0,1> is interpolating between them !!!.

But even this can provide inaccuracy as you can have some extremes without control point. In case even that is a problem (The BBOX is a bit smaller than should) you can re-sample your shape to set of points (for example 10 per cubic) on the curve with some step (0.1) and do the BBOX from those points. That will be much more precise but slower of coarse...

Spektre
  • 49,595
  • 11
  • 110
  • 380
0

One property of Bezier curves is that as you split them, the distance between the smooth curve and the CVs shrinks.

So, one way to fix those CVs on the top and bottom is to split the related Bezier into two Beziers using the De Casteljau algorithm.

You could even do this algorithmically:

  • Find tight bounding box and CV-based bounding box.
  • If the difference is greater than your tolerance, find the max/min CVs and their related Bezier curves
  • Split all of the related Bezier curves into two Bezier curves each
  • Repeat

Eventually you'll hit your tolerance. You might have a lot of Beziers by then though if you have a very tight tolerance or tricky data.

tfinniga
  • 6,693
  • 3
  • 32
  • 37