Bounding box of cubic bezier curve
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)