Кривая Безье произвольного порядка.

#математика #алгоритм #php

Товарищи программисты-математики, отдаю на ваш справедливый суд данный класс.
Некоторые очевидные методы, вроде lineTo я убрал, чтобы не было tl;dr, то есть, это
выжимка интересующих меня моментов.
x = $x?$x:rand(1,IMG_SIZE_X);
        $this->y = $y?$y:rand(1,IMG_SIZE_Y);
    }

    /**
     * @param point $p
     * @param float $dist
     *
     * @return point
     */
    function midPoint(point $p,$dist=0.5){
        $new_x = $this->x+($p->x-$this->x)*$dist;
        $new_y = $this->y+($p->y-$this->y)*$dist;
        $new_point = new point($new_x,$new_y);
        return $new_point;
    }
}

/**
 * Class bezierimage
 */
class bezierimage{
    private $img;
    public $color;
    public $bgcolor;
    public $brush_position;
    function __construct(){
        $this->img = imagecreatetruecolor(IMG_SIZE_X,IMG_SIZE_Y);
        $this->color = imagecolorallocate($this->img,255,255,255);
    }

    /**
     * @param point[]   $points
     * @param float     $dist
     *
     * @return point[]
     */
    function getBezierPoints($points,$dist=0.5){
        if(count($points)==1){
            return $points[0];
        }
        $new_points = array();
        for($i=1;$imidPoint($points[$i],$dist);
        }
        return $this->getBezierPoints($new_points,$dist);
    }
    /**
     * @param point[]   $points
     * @param int       $precision
     */
    function bezierCurve($points,$precision=700){
        foreach($points as $point){
            $this->putPixel($point);
        }
        for($i=0;$i<$precision;$i++){
            $dist = $i/$precision;
            $this->lineTo($this->getBezierPoints($points,$dist),2);
        }
    }
}

Можно ли, не прибегая к другим языкам, оптимизировать данный код? Он заметно начинает
тормозить уже на порядке 70, а на 100 просто утыкается в ограничение по вложенности
рекурсии. Особенно интересуют два момента:
метод getBezierPoints - оптимизация
метод bezierCurve - динамический подбор количества полигонов, в зависимости от кривизны
линии на данном отрезке.

По поводу сторонних библиотек: к сожалению, чаще всего находятся максимум 3-4 порядка,
так что не вариант, разве что собрать свою.
P.S. таки да, я опять пытаюсь использовать PHP в целях, для которых он не предназначен.
Но интерес больше академический, для практики и правда более 6-10 точек не надо.    

Ответы

Ответ 1

По поводу getBezierPoints — можно сделать в один проход без рекурсии.

Смотрите. Пусть в начале у нас есть точки p[0], ..., p[n-1]. После первого шага у
нас получается q[0] = (p[0] + p[1]) / 2, q[1] = (p[1] + p[2]) / 2, ..., q[n-2] = (p[n-2]
+ p[n-1]) / 2, то есть

q[i] = (p[i] + p[i+1]) / 2.


На следующем шаге

r[i] = (q[i] + q[i+1]) / 2 = (p[i] + 2p[i+1] + p[i+2]) / 4.


Видно, что возникают биномиальные коэффициенты:

r[i] = (C_2^0 p[i + 0] + C_2^1 p[i + 1] + C_2^2 p[i + 2]) / 2^2.


(Немного математики: По индукции легко доказать, что биномиальные коэффициенты будут
и дальше: если на j-м уровне

s[i] = (\sum_k=0^{j-1} C_j^k p[i + k]) / 2^j,


то на (j+1)-м

t[i] = (s[i] + s[i+1]) / 2 =
     = (\sum_k=0^j (C_j^k + C_j^{k + 1}) p[i + k]) / 2^{j + 1}
     = (\sum_k=0^j C_{j + 1}^k p[i + k]) / 2^{j + 1}.


База индукции очевидна.)

Итак, нам нужны биномиальные коэффициенты. Их можно тоже легко вычислить на лету.
Конечный алгоритм должен быть таким:

int l = count($points);
int coeff = 1;
point result = $points[0];
for (int idx = 1; idx < l; idx++)
{
    coeff *= (l - idx);
    coeff /= idx;
    result += $points[idx] * coeff;
}
result /= (1 << (l - 1)); // степень двойки




Если делить надо не обязательно на 2, аналогично получается вот что:

int l = count($points);
double alpha = 0.333333; // или любое другое значение между 0 и 1
double beta = 1 - alpha;
double beta2alpha = beta / alpha;
int coeff = alpha ** (l - 1); // степень
point result = $points[0] * coeff;
for (int idx = 1; idx < l; idx++)
{
    coeff *= (l - idx);
    coeff /= idx;
    coeff *= beta2alpha;
    result += $points[idx] * coeff;
}