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

Товарищи программисты-математики, отдаю на ваш справедливый суд данный класс. Некоторые очевидные методы, вроде lineTo я убрал, чтобы не было tl;dr, то есть, это выжимка интересующих меня моментов. /** * @param $x * @param $y */ function __construct($x=false,$y=false){ $this->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 точек не надо.

Ответ

По поводу 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; }