#математика #алгоритм #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;
}
