在此代码中如何使用叉积来确定贝塞尔曲线段的“平坦度”？

Question

我有一个脚本，可以计算三次贝塞尔曲线中的点，然后在点之间绘制线段来绘制曲线。执行这些计算的函数是递归的，我希望函数停止在曲线段足够平坦的点，不需要任何进一步的处理，并且可以用直线按原样绘制。

从头开始，参考一些数学教程网站，我编写了一些代码来执行此操作，该代码找到从每个控制点到连接曲线起点和终点的线的垂直距离，如果距离很小足够了，假设曲线段足够平坦：

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;
    }
}

这段代码似乎按预期工作，我认为这是解决任务的合理方法，但我在 Stack Overflow 上找到了一个 示例，它以不同的方式进行计算，并且效率更高，无需使用任何平方根或除法:

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);
}

我可以看到这段代码正在使用叉积，但我不明白它是如何工作的或为什么它有效。我看过的大多数补习网站都以与我类似的方式进行垂直计算，但我更喜欢使用这个更简单的版本，因为它的计算强度较小，而且我必须进行数百次计算曲线，我想理解代码，而不是仅仅将其复制并粘贴到脚本中，而不知道它是如何工作的。

提前感谢您的任何帮助或建议。我不是数学高手，如果可能的话，我将不胜感激。我本想向代码作者询问一些意见，但该示例是在 13 年前发布的。

Answer 1

从第一个版本到第二个版本的转换是相对简单的代数，并且两种形式完全等价。从你的第一个代码开始：

// 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;
}

并与第二种方法进行比较

// 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);

我们可以用第二个方法的表示法重写第一个方法，这样相似性就更明显了：

$distance_1 = abs($a_cross_b)/sqrt($d_sq);
$distance_2 = abs($a_cross_c)/sqrt($d_sq);

将它们平方，我们有

$distance_1_sq = $a_cross_b*$a_cross_b/$d_sq;
$distance_2_sq = $a_cross_c*$a_cross_c/$d_sq;

为了避免进行昂贵的除法，请将测试乘以 $d_sq

顺便说一句，由于您将向下递归并预计会出现相当多的失败，因此在示例中不要使用任何退出代码并替换这个更懒的版本更有意义：

 $d_sq = 0.25 * $d_sq;
 if (($distance_1 >= $d_sq) || ($distance_2 >= $d_sq)){
    return false;
 }
 return true

假设您选择的语言将在满足第一个表达式时退出，而不做任何额外的工作。否则将其分成连续的测试（并将最有可能生成错误退出的测试放在第一个）。