Алгоритм Брезенхема для... параболы

Алгоритм Брезенхэ́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Е. Брезенхэмом (Jack E. Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка.

из википедии

  Суть алгоритма Брезенхема для окружности: считаем один раз точку и отражаем её ещё 7 раз, для параболы же получаем то же самое, только рисуем не часть четверти, как у окружности, а одну ветвь параболы, отражая её потом зеркально от оси. Ну обовсём по порядку.
  Имеем каноническое уравнение параболы:

Определися с направлениями движения. Их как и в случае с коружностью три (гм.. странные совпадения:): вертикаль, горизонталь и диагональ, соответствено движение из начальной точки (x,y) будут следующими: (x,y+1), (x+1, y) или (x+1,y+1). Теперь, было бы не плохо понять, как мы двигаемся при отрисовке параболы, имея три направления. Для начала, находим расстояния от трёх возможных точек до параболы по следующим формулам:

—  для диагонали


      
          —   для горизонтали

     
          —   для вертикали

  Затем высчитываем направление нашего движения следующим образом, находим разности между расстояниями:

  Если дельта меньше нуля, то следующее направление движения горизонталь либо диагональ, в противном случае вертикаль либо диагональ. Предположим что меньше, тогда смотрим разницу расстояний  И снова сравнения, если разность меньше нуля, то двигаемся по диагонали, если не - по горизонтали.   Вернёмся к   дельта, мы рассмотрели случай с меньше, но что же будет если всё не так? А будет следующее - очередное сравнение и обьектом его будет разности растояний .  Если разность больше нуля, то движение по диагонали, если меньше - по вертикали.Вот собственно и весь принцип определения направлений движения.

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

  Вот собственно и всё, принцип почти тот же что и для окружности. Такой вариант достаточно медленный из-за пересчета расстояний до параболы на каждой итерации, поэтому его лучше оптимизировать, но... об этом позже.

З.Ы. Небольшой кусок кода на С#, иллюстрирующий вышесказанное:

//---------------------------------------------------------

            int p = 2;
            int x0 = 0; //  центр
            int y0 = 0; //
            int Sh, Sv, Sd;
            Sd = ((y + 1) * (y + 1) )- 2 * p * (x + 1);
            Sv = ((y + 1)*(y + 1)) - 2 * p * x;
            Sh = (y*y) - 2 * p * (x + 1);
            this.drawPix(x0, y0);    
            while (x + x0 < maxX) //пока полотно не кончится
            {
                if (Math.Abs(Sh) - Math.Abs(Sv)<=0)
                {
                    if (Math.Abs(Sd) - Math.Abs(Sh) < 0)
                           y++;
                    x++;

                }
                else
                {
                    if (Math.Abs(Sv) - Math.Abs(Sd) > 0)
                           x++;
                    y++;
                    
                }

                this.drawPix(x + x0, y + y0);

                Sd = ((y + 1) * (y + 1)) - 2 * p * (x + 1);
                Sv = ((y + 1) * (y + 1)) - 2 * p * x;
                Sh = (y * y) - 2 * p * (x + 1);
            }
//---------------------------------------------------------