## Bounding box of cubic bezier curve

21 September 2016

### Background

It is very commonly used approach to itterate through the points of the bezier

curve and this way to determine the most left, right, top, bottom possitions.

This approach is slow and not so accurate.

### Basics

Calculations of the points can be performed by simple calculations

A1 = A + (B-A)t = A(1-t) + Bt

B1 = B + (C-B)t = B(1-t) + BC

C1 = C + (D-C)t = C(1-t) + Dt

K = A1 + (B1-A1)t = A1(1-t) + B1t

L = B1 + (C1-B1)t = B1(1-t) + C1t

M = K + (L-K)t = K(1-t) + Lt

M = (A1(1-t) + B1t)(1-t) + (B1(1-t) + C1t)t =

A1(1-t)^2 + B1(1-t)t + B1(1-t)t + C1t^2 =

A1(1-t)^2 + 2B1(1-t)t + C1t^2

### (1-t)^3 A vs t^3 B

How the first coordinate relates to the last one? As we know t
starts from 0 and ends with 1. As we look on this equation (1-t)^3 a -
t^3 b we will see that it is a line. So if A is lower than B then A
will be lower point of the curve and B will be the biggest value. When
B is lower then we have the opposite situation. This relates to Left
and Right, also to Top and Bottom values. If we use the X coordinates
of the points then we have the Left and Right values. If we use the Y
coordinates then we have the Top and Bottom values

**But what happens with 3.(1-t)^2.t.A and 3.(1-t).t^2.B**

to be continued

### Left-right and Top-Bottom

Left and right are determined by the X coordinates. Top and bottom are determined by the Y coordinates.

This can be done separately. Algorithm is the same for both.

### Possible slope combinations

Possible slope combinations of the edges between the points.

They are 2^3 = 8. 2 states in 3 positions

Equal values are also posible, however, equals will be part of the other cases.

1. -> -> -> all in same direction

2. <- <- <- all in same direction

3. -> <- -> ends in same direction

4. <- -> <- ends in same direction

5. -> -> <- ends in opposite directions

6. -> <- <- ends in opposite directions

7. <- -> -> ends in opposite directions

8. <- <- -> ends in opposite directions

### Start and end

Both ends are equal. It doesn't matter which point we will choose for start and which for end. At the end we have the same bounding box.

If we have all edges in same direction -> -> -> it will be the same as <- <- <- if we choose other end for start.

This way we have pairs that are the same but looked from different end.

1. -> -> -> all in same direction

2. <- <- <- all in same direction

3. -> <- -> ends in same direction

4. <- -> <- ends in same direction

5. -> -> <- ends in opposite directions

6. -> <- <- ends in opposite directions

7. <- -> -> ends in opposite directions

8. <- <- -> ends in opposite directions

### Control points between end points

When control points lay between the end points, end points will define the bounding box.

No other point can lay more left or right than them.

Covered combinations

1. -> -> ->

2. <- <- <-

Partial covered combinations

3. -> <- ->

4. <- -> <-

### Opposite ends

In 4 combinations we have end eges with opposite directions

5. -> -> <- ends in opposite directions

6. -> <- <- ends in opposite directions

7. <- -> -> ends in opposite directions

8. <- <- -> ends in opposite directions

In these cases we have:

- if first edge is right oriented then we have first or last point define left boundary of the bounding box. The right boundary needs more calculations.

- if first edge is left oriented then we have first or last point as right boundary of the bounding box. The left boundary needs more calculations.

### Opposite edges

In 6 of the slope combinations we have edges that have opposite direction slopes

a/b = b/c <=> b^2 = ac

a = AB - b

c = BC - b

replace a and c

b^2 = (AB - b)(BC - b)

b^2 = AB*BC -ABb - BCb + b^2

b(AB + BC) = AB*BC

b = AB*BC/(AB + BC)

D = B - (B-A)(B-C)/(B-A+B-C)

Back to main menu