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

Question

Я какое-то время играю с библиотекой GD, а точнее - с кривыми Безье.

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

Теперь я хочу поднять его на другой уровень: мне нужны цвета.

Нет проблемдля цвет линии , но с заливка сложнее.

Мой вопрос:

Существует ли какой-либо существующий алгоритм для этого?Я имею в виду математический алгоритм или любой другой язык, который делает это так, чтобы я мог перевести его в PHP + GD?

EDIT2 Итак, я попробовал решение @MizardX с сложнее кривая:

• 1-е положение: 50 - 50
• конечное положение: 50 - 200
• 1-я контрольная точка: 300 - 225
• 2-е управлениеТочка: 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);
}

?>

Edit:

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

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). Используя эту нормаль, найдите расстояние между двумя самыми дальними точками (p_max1 и p_max2) вдоль этой нормали (d1). Разделите это расстояние на n дискретных единиц (дельта).

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

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