I have a script that calculates the points in a cubic bezier curve and then draws line segments between the points to draw the curve. The function to do these calculations is recursive and I would like the function to stop at the point at which a curve segment is sufficiently flat enough to not require any further processing and can be drawn as-is with a straight line.
Starting from scratch but with reference to some mathematics tutorial sites, I wrote some code to do this which finds the perpendicular distance from each of the control points to the line connecting the start and end points of the curve, and if the distance is small enough it is assumed that the curve segment is flat enough:
function check_flatness($p)
{
// Distance between end point and start point of new polygon
$a_x = $p[6] - $p[0];
$a_y = $p[7] - $p[1];
// Distance between control point 1 and start point of new polygon
$b_x = $p[2] - $p[0];
$b_y = $p[3] - $p[1];
// Distance between control point 2 and end point of new polygon
$c_x = $p[4] - $p[6];
$c_y = $p[5] - $p[7];
// Perpendicular distance of control point 1 to start/end point line
$distance_1 = abs(($a_x * $b_y - $b_x * $a_y) / sqrt(($a_x * $a_x) + ($a_y * $a_y)));
// Perpendicular distance of control point 2 to start/end point line
$distance_2 = abs(($a_x * $c_y - $c_x * $a_y) / sqrt(($a_x * $a_x) + ($a_y * $a_y)));
if ($distance_1 < $some_value && $distance_2 < $some_value) {
return true; // stop recursion
} else {
return false;
}
}
This code seems to work as expected, and I assume that this is a reasonable way to solve the task, but I found an example on Stack Overflow that does the calculations differently and much more efficiently, without using any square roots or division:
function check_flatness($p)
{
// Distance between end point and start point of new polygon
$a_x = $p[6] - $p[0];
$a_y = $p[7] - $p[1];
// Distance between control point 1 and start point of new polygon
$b_x = $p[2] - $p[0];
$b_y = $p[3] - $p[1];
// Distance between control point 2 and end point of new polygon
$c_x = $p[4] - $p[6];
$c_y = $p[5] - $p[7];
// Different calculation method starts here...
$a_cross_b = ($a_x * $b_y) - ($a_y * $b_x);
$a_cross_c = ($a_x * $c_y) - ($a_y * $c_x);
$d_sq = ($a_x * $a_x) + ($a_y * $a_y);
$flatness_sq = 0.25;
return max($a_cross_b * $a_cross_b, $a_cross_c * $a_cross_c) < ($flatness_sq * $d_sq);
}
I can see that this code is using cross products, but I do not understand how it's meant to work or why it works. Most of the tuition sites I've looked at do the perpendicular calculation in a similar way to how I've done it, but I would prefer to use this simpler version because it is less computationally intensive and I have to do the calculations for hundreds of curves and I want to understand the code rather than just copying-and-pasting it into a script with no clue as to how it works.
Thank you in advance for any help or suggestions. I am no math whiz and an entry-level explanation if possible would be appreciated. I would have asked the author of the code for some input but the example was posted well over 13 years ago.
The conversion from the first version to the second is relatively simple algebra and the two forms are exactly equivalent. Starting from your first code:
// Perpendicular distance of control point 1 to start/end point line
$distance_1 = abs(($a_x * $b_y - $b_x * $a_y) / sqrt(($a_x * $a_x) + ($a_y * $a_y)));
// Perpendicular distance of control point 2 to start/end point line
$distance_2 = abs(($a_x * $c_y - $c_x * $a_y) / sqrt(($a_x * $a_x) + ($a_y * $a_y)));
if ($distance_1 < $some_value && $distance_2 < $some_value) {
return true; // stop recursion
} else {
return false;
}
and comparing it with the second method
// Different calculation method starts here...
$a_cross_b = ($a_x * $b_y) - ($a_y * $b_x);
$a_cross_c = ($a_x * $c_y) - ($a_y * $c_x);
$d_sq = ($a_x * $a_x) + ($a_y * $a_y);
$flatness_sq = 0.25;
return max($a_cross_b * $a_cross_b, $a_cross_c * $a_cross_c) < ($flatness_sq * $d_sq);
We can rewrite the first method in the notation of the second so that the similarities are more obvious:
$distance_1 = abs($a_cross_b)/sqrt($d_sq);
$distance_2 = abs($a_cross_c)/sqrt($d_sq);
and squaring them we have
$distance_1_sq = $a_cross_b*$a_cross_b/$d_sq;
$distance_2_sq = $a_cross_c*$a_cross_c/$d_sq;
and to avoid doing the expensive division multiply the tests through by $d_sq
Incidentally since you will be recursing down and expect a fair number of failures on the way it makes more sense not to use either of the exit codes in your examples and substitute this lazier version instead:
$d_sq = 0.25 * $d_sq;
if (($distance_1 >= $d_sq) || ($distance_2 >= $d_sq)){
return false;
}
return true
Assuming that your choice of language will exit when the first expression is met without doing any extra work. Otherwise split it into consecutive tests (and put the one most likely to generate an exit with false first).