Алгоритм добавления цвета в кривых Безье

Ответ 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);
}

?>

Edit:

Я забыл протестировать рутину. Это так, как вы сказали; Это не дает правильного результата. Теперь я исправил две ошибки:

• Я непреднамеренно повторно использовал имена переменных $p1 и $p2. Я переименовал их $prev и $next.
• Неверный знак в while -loop. Теперь он петли, пока расстояние не станет достаточно маленьким, а не достаточно большим.

Ответ 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*)
[email protected]@Table[f[t],{t,0,1,step}]  

.

.

Алгоритм может быть оптимизирован (т.е. генерировать меньше точек), если вам не требуется одинаковое приращение параметров между точками, что означает, что вы можете выбрать приращение параметра в каждой точке, что обеспечивает ограниченное расстояние до следующего.

Случайные примеры:

Ответ 3

Создайте список последовательных точек, которые лежат вдоль кривой (p_list)).

Вы создаете линию между двумя конечными точками кривой (l1).

Затем вы найдете нормали линии (n1). Используя эту нормаль, найдите расстояние между двумя самыми дальними точками (p_max1 и p_max2) вдоль этой нормали (d1). Разделите это расстояние на n дискретных единиц (дельта).

Теперь сдвиньте l1 вдоль n1 на delta и решите для точек пересечения (начните с грубой силы и проверьте решение между всеми сегментами строки в p_list). Вы должны иметь возможность получить две точки пересечения для каждого сдвига l1, за исключением границ и самопересечений, где у вас может быть только одна точка. Надеемся, что подпрограмма quad может иметь две точки квада в одном и том же месте (треугольник) и заполнять без жалобы, иначе вам понадобятся треугольники в этом случае.

Извините, я не предоставлял псевдокод, но идея довольно проста. Это точно так же, как взятие двух конечных точек и объединение их с линейкой, а затем поддержание этой линейки параллельно первоначальному началу линии на одном конце и последовательные очень близкие метки карандаша заполняют всю фигуру. Вы увидите, что когда вы создаете свою маленькую метку карандаша (мелкий прямоугольник), чтобы прямоугольник вряд ли использовал точки на кривой. Даже если вы заставите его использовать точку на одной стороне кривой, было бы вполне совпадением, чтобы она точно соответствовала точке на другой стороне, по этой причине лучше просто вычислить новые точки. Во время вычисления новых точек было бы, вероятно, хорошей регенерацией кривых p_list в терминах этих точек, чтобы вы могли быстрее заполнить его (если кривая останется неподвижной, иначе это не имело бы смысла).

Ответ 4

Этот ответ очень похож на @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);, похоже, не работает.