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

Преобразуйте кривую Безье в полилинию/многоугольник и заполните ее. Если вы оцениваете полином Безье на достаточно близких интервалах (~ 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-цикле. Теперь он зацикливается до тех пор, пока расстояние не станет достаточно маленьким, а не достаточно большим.

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

Код в Математике:

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

.

.

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

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

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

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

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

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

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

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