在贝塞尔曲线中添加颜色的算法

Question

我正在使用 GD 库一段时间，尤其是 Bezier 曲线 atm。

我使用了 一些现有的类，我对其进行了一些修改（认真地eval()...)。我发现这是一个用于 GD 并转换为 GD 的通用算法。

现在我想把它提升到另一个层次：我想要一些颜色。

对于线条颜色没有问题，但是对于填充颜色就更难了。

我的问题是：

有没有现有的算法？我的意思是数学算法或任何已经这样做的语言，以便我可以将其转移到 PHP + GD？

编辑2 因此，我尝试了具有更难曲线的@MizardX解决方案：

• 第一个位置：50 - 50
• 最终位置：50 - 200
• 第一个控制点：300 - 225
• 第二个控制点：300 - 25

应该显示以下内容：

并给出：

编辑 我已经阅读了有关 @MizardX 解决方案的内容。使用imagefilledpolygon使其工作。

但是它没有按预期工作。请参见下图以了解问题。。 顶部图表是我所期望的（目前没有黑线，只有红色部分）。

使用的坐标：

• 第一个点是 100 - 100
• 最终点是 300 - 100
• 第一个控制点是 100 - 0
• 最终控制点是 300 - 200

底部是我用这种算法得到的结果...

Answer 1

将贝塞尔曲线转换为折线/多边形，并填充它。如果您以足够近的间隔（~1 像素）评估贝塞尔多项式，它将与理想的贝塞尔曲线相同。

我不知道您对贝塞尔曲线有多熟悉，但这里有一个速成课程：

<?php

// Calculate the coordinate of the Bezier curve at $t = 0..1
function Bezier_eval($p1,$p2,$p3,$p4,$t) {
    // lines between successive pairs of points (degree 1)
    $q1  = array((1-$t) * $p1[0] + $t * $p2[0],(1-$t) * $p1[1] + $t * $p2[1]);
    $q2  = array((1-$t) * $p2[0] + $t * $p3[0],(1-$t) * $p2[1] + $t * $p3[1]);
    $q3  = array((1-$t) * $p3[0] + $t * $p4[0],(1-$t) * $p3[1] + $t * $p4[1]);
    // curves between successive pairs of lines. (degree 2)
    $r1  = array((1-$t) * $q1[0] + $t * $q2[0],(1-$t) * $q1[1] + $t * $q2[1]);
    $r2  = array((1-$t) * $q2[0] + $t * $q3[0],(1-$t) * $q2[1] + $t * $q3[1]);
    // final curve between the two 2-degree curves. (degree 3)
    return array((1-$t) * $r1[0] + $t * $r2[0],(1-$t) * $r1[1] + $t * $r2[1]);
}

// Calculate the squared distance between two points
function Point_distance2($p1,$p2) {
    $dx = $p2[0] - $p1[0];
    $dy = $p2[1] - $p1[1];
    return $dx * $dx + $dy * $dy;
}

// Convert the curve to a polyline
function Bezier_convert($p1,$p2,$p3,$p4,$tolerance) {
    $t1 = 0.0;
    $prev = $p1;
    $t2 = 0.1;
    $tol2 = $tolerance * $tolerance;
    $result []= $prev[0];
    $result []= $prev[1];
    while ($t1 < 1.0) {
        if ($t2 > 1.0) {
            $t2 = 1.0;
        }
        $next = Bezier_eval($p1,$p2,$p3,$p4,$t2);
        $dist = Point_distance2($prev,$next);
        while ($dist > $tol2) {
            // Halve the distance until small enough
            $t2 = $t1 + ($t2 - $t1) * 0.5;
            $next = Bezier_eval($p1,$p2,$p3,$p4,$t2);
            $dist = Point_distance2($prev,$next);
        }
        // the image*polygon functions expect a flattened array of coordiantes
        $result []= $next[0];
        $result []= $next[1];
        $t1 = $t2;
        $prev = $next;
        $t2 = $t1 + 0.1;
    }
    return $result;
}

// Draw a Bezier curve on an image
function Bezier_drawfilled($image,$p1,$p2,$p3,$p4,$color) {
    $polygon = Bezier_convert($p1,$p2,$p3,$p4,1.0);
    imagefilledpolygon($image,$polygon,count($polygon)/2,$color);
}

?>

编辑：

我忘了测试例程。确实如你所说；它没有给出正确的结果。现在我修复了两个错误：

1. 我无意中重复使用了变量名 $p1 和 $p2。我将它们重命名为 $prev 和 $next。
2. while 循环中的符号错误。现在它会循环直到距离足够小，而不是足够大。

Answer 2

我检查了生成多边形的算法，确保连续参数生成点之间的有界距离，并且似乎对于我测试的所有曲线都适用。

Mathematica 中的代码：

pts={{50,50},{300,225},{300,25},{50,200}};
f=BezierFunction[pts];
step=.1; (*initial step*)

While[ (*get the final step - Points no more than .01 appart*)
   Max[
     EuclideanDistance @@@ 
         Partition[Table[f[t],{t,0,1,step}],2,1]] > .01,
   step=step/2]

(*plot it*)
Graphics@Polygon@Table[f[t],{t,0,1,step}]  

.

。

如果您不需要点之间相同的参数增量，则可以优化算法（即生成更少的点），这意味着您可以在每个点处选择一个参数增量，以确保到下一个点的有界距离。

随机示例：

Answer 3

这个答案与@MizardX 的非常相似，但使用不同的方法来沿着贝塞尔曲线找到合适的点以进行多边形近似。

function split_cubic($p, $t)
{
    $a_x = $p[0] + ($t * ($p[2] - $p[0]));
    $a_y = $p[1] + ($t * ($p[3] - $p[1]));
    $b_x = $p[2] + ($t * ($p[4] - $p[2]));
    $b_y = $p[3] + ($t * ($p[5] - $p[3]));
    $c_x = $p[4] + ($t * ($p[6] - $p[4]));
    $c_y = $p[5] + ($t * ($p[7] - $p[5]));
    $d_x = $a_x + ($t * ($b_x - $a_x));
    $d_y = $a_y + ($t * ($b_y - $a_y));
    $e_x = $b_x + ($t * ($c_x - $b_x));
    $e_y = $b_y + ($t * ($c_y - $b_y));
    $f_x = $d_x + ($t * ($e_x - $d_x));
    $f_y = $d_y + ($t * ($e_y - $d_y));

    return array(
        array($p[0], $p[1], $a_x, $a_y, $d_x, $d_y, $f_x, $f_y),
        array($f_x, $f_y, $e_x, $e_y, $c_x, $c_y, $p[6], $p[7]));
}

$flatness_sq = 0.25; /* flatness = 0.5 */
function cubic_ok($p)
{
    global $flatness_sq;

    /* test is essentially:
     * perpendicular distance of control points from line < flatness */

    $a_x = $p[6] - $p[0];  $a_y = $p[7] - $p[1];
    $b_x = $p[2] - $p[0];  $b_y = $p[3] - $p[1];
    $c_x = $p[4] - $p[6];  $c_y = $p[5] - $p[7];
    $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);
    return max($a_cross_b * $a_cross_b, $a_cross_c * $a_cross_c) < ($flatness_sq * $d_sq);
}

$max_level = 8;
function subdivide_cubic($p, $level)
{
    global $max_level;

    if (($level == $max_level) || cubic_ok($p)) {
        return array();
    }

    list($q, $r) = split_cubic($p, 0.5);
    $v = subdivide_cubic($q, $level + 1);
    $v[] = $r[0]; /* add a point where we split the cubic */
    $v[] = $r[1];
    $v = array_merge($v, subdivide_cubic($r, $level + 1));
    return $v;
}

function get_cubic_points($p)
{
    $v[] = $p[0];
    $v[] = $p[1];
    $v = array_merge($v, subdivide_cubic($p, 0));
    $v[] = $p[6];
    $v[] = $p[7];
    return $v;
}

function imagefilledcubic($img, $p, $color)
{
    $v = get_cubic_points($p);
    imagefilledpolygon($img, $v, count($v) / 2, $color);
}

基本思想是递归地将立方体分成两半，直到剩下的位几乎平坦。在我们分割立方体的每个地方，我们都会粘贴一个多边形点。

split_cubic 在参数 $t 处将立方体分成两部分。 cubic_ok 是“我们足够平坦吗？”测试。 subdivide_cubic 是递归函数。请注意，我们对递归深度进行了限制，以避免令人讨厌的情况真正把我们搞砸了。

您的自相交测试用例：

$img = imagecreatetruecolor(256, 256);

imagefilledcubic($img, array(
    50.0, 50.0, /* first point */
    300.0, 225.0, /* first control point */
    300.0, 25.0, /* second control point */
    50.0, 200.0), /* last point */
    imagecolorallocate($img, 255, 255, 255));

imagepng($img, 'out.png');

imagedestroy($img);

给出以下输出：

我不知道如何使 PHP 很好地反- 别名； imageantialias($img, TRUE); 似乎不起作用。

Answer 4

生成沿曲线的连续点的列表 (p_list))。

您在曲线的两个端点之间创建一条线 (l1)。

然后你将找到直线的法线 (n1)。使用该法线查找沿该法线 (d1) 的两个最远点（p_max1 和 p_max2）之间的距离。将此距离分成 n 个离散单位 (delta)。

现在将 l1 沿 n1 移动 delta，并求解交点（从强力开始并检查 p_list 中所有线段之间的解）。对于 l1 的每次移位，您应该能够获得两个交点，但边界和自交点除外，在这些情况下您可能只有一个点。希望四边形例程可以使四边形的两个点位于同一位置（三角形）并毫无怨言地填充，否则在这种情况下您将需要三角形。

抱歉，我没有提供伪代码，但这个想法非常简单。这就像取两个端点并用一把尺子将它们连接起来，然后使尺子与从一端开始的原始线保持平行，并用连续的非常接近的铅笔标记填充整个图形。您会发现，当您创建小铅笔标记（一个精细的矩形）时，该矩形极不可能使用曲线上的点。即使你强迫它使用曲线一侧的点，它与另一侧的点完全匹配也是很巧合的，因此最好只计算新点。在计算新点时，根据这些点重新生成曲线 p_list 可能是一个好主意，这样您就可以更快地填充它（当然，如果曲线保持静态，否则它没有任何意义） 。