How to calculate minimum and maximum of cubic Bezier curve

From About PCs Wiki
Jump to navigation Jump to search

Bezier curves are very important for computer graphics.

If you want to analyze a path in an SVG and construct the viewBox you need the extrema of the parts of the path. For linear components this is trivial, for curved parts of the path not so much.

A cubic Bezier curve is defined by four points: start , end and two control points and

Any point between start and end can be calculated as

where

The derivative is

We get a quadratic equation of the form

where

and the discriminant

When then we have trivial solution that start and end are the extrema.

Lua Code[edit | hide | hide all]

Now we have everything to construct our Lua subroutine. This routine does not contain any error protection

function boundbox(p0,p1,p2,p3)

-- p0, p1, p2, p3 are the coordinates of the controlpoints, either x or y
-- returns two numbers, min and max
-- no checks included if all parameters are numbers
-- no subroutine for calculation min or max included

  local bmin = p0;
  if p3 < bmin then bmin = p3 end
  local bmax = p0
  if p3 > bmax then bmax = p3 end
  
  local c = p1 - p0
  local b = p0 - 2 * p1 + p2
  local a = p3 - 3 * p2 + 3 * p1 - p0
  
  local h = b * b - a * c -- discriminant
  
  if h <= 0 then
    return bmin, bmax
  end
  
  local x = math.sqrt(h)
  
  local t = (-b + x)/a  -- one solution of the quadratic equation
  
  if t <= 0 or t >= 1 then t = ( -b - x )/a end -- it must be the other solution
  
  if t <= 0 or t >= 1 then return bmin, bmax end
  
  local s = 1 - t  -- simplifying notation
  
  local q = s^3 * p0 + 3 * s * s * t * p1 + 3 * s * t * t * p2 + t * t * t * p3
  
  if q < bmin then bmin = q end
  if q > bmax then bmax = q end
  
  return bmin, bmax

end

Links[edit | hide]