Алгоритм брезенхема java

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

Алгоритм Брезенхема был предложен Джеком Е. Брезенхэмом (Jack E. Bresenham) в 1962 году и предназначен для рисования фигур точками на плоскости. Этот алгоритм находит широкое распространение в машинной графике для рисования линий на экране. Алгоритм определяет, какие точки двумерного растра необходимо закрасить.

Графическая интерпретация алгоритма Брезенхема представлена на рисунке.

Для рисования прямых отрезков на плоскости с использованием алгоритма Брезенхема запишем уравнение прямой в общем виде

y=kx+b

f(x,y)=Ax+By+C=0

где коэффициенты A и B выражаются через коэффициенты k и b уравнения прямой. Если прямая проходит через две точки с координатами (x1;y1) и (x2;y2) , то коэффициенты уравнения прямой определяются по формулам

A=y2-y1
B=x1-x2
C=y1∙x2-y2∙x1

Для любой растровой точки с координатами (xi;yi) значение функция

f(xi,yi)=0 если точка лежит на прямой
f(xi,yi)>0 если точка лежит ниже прямой
f(xi,yi) где i – номер отображаемой точки.

Таким образом, одним из методов решения того, какая из точек P или Q (см. рисунок) будет отображена на следующем шаге, является сравнение середины отрезка |P-Q| со значением функции f(x,y) . Если значение f(x,y) лежит ниже средней точки отрезка |P-Q| , то следующей отображаемой точкой будет точка P , иначе — точка Q .
Запишем приращение функции

∆f=A∆x+B∆y

После отображения точки с координатами (xi,yi) принимается решение о следующей отображаемой точке. Для этого сравниваются приращения Δx и Δy , характеризующие наличие или отсутствие перемещения по соответствующей координате. Эти приращения могут принимать значения 0 или 1. Следовательно, когда мы перемещаемся от точки вправо,

∆f=A,

когда мы перемещаемся от точки вправо и вниз, то

∆f=A+B,

когда мы перемещаемся от точки вниз, то

∆f=B

Нам известны координаты начала отрезка, то есть точки, заведомо лежащей на искомой прямой. Ставим туда первую точку и принимаем f = 0 . От текущей точки можно сделать два шага — либо по вертикали (по горизонтали), либо по диагонали на один пиксель.
Направление движения по вертикали или горизонтали определяется коэффициентом угла наклона. В случае если угол наклона меньше 45º, и

|A| Реализация на C++

Алгоритм Брезенхема также может применяться в задачах управления, например, для регулирования мощности или скорости вращения. При этом горизонтальной осью является ось времени, а заданное значение устанавливает коэффициент угла наклона прямой.

Брезенхем и У на страже диагоналей

На что вы сейчас смотрите? Если вы не из параллельной вселенной, где все сидят за векторными мониторами, то перед вами растровое изображение. Поглядите на эту полоску: /. Если придвинуться поближе к монитору, то можно увидеть пиксельные ступеньки, которые пытаются притвориться векторной линией. Для этой цели существует целая куча всевозможных алгоритмов растеризации, но я бы хотел рассказать об алгоритме Брезенхема и алгоритме У, которые находят приближение векторного отрезка в растровых координатах.

С проблемой растеризации мне довелось столкнуться во время работы над процедурным генератором планов зданий. Мне нужно было представить стены помещения в виде ячеек двумерного массива. Похожие задачи могут встретиться в физических расчётах, алгоритмах поиска пути или расчёте освещения, если используется разбиение пространства. Кто бы мог подумать, что знакомство с алгоритмами растеризации однажды может пригодиться?

Принцип работы алгоритма Брезенхема очень простой. Берётся отрезок и его начальная координата x. К иксу в цикле прибавляем по единичке в сторону конца отрезка. На каждом шаге вычисляется ошибка — расстояние между реальной координатой y в этом месте и ближайшей ячейкой сетки. Если ошибка не превышает половину высоты ячейки, то она заполняется. Вот и весь алгоритм.

Это была суть алгоритма, на деле всё выглядит следующим образом. Сначала вычисляется угловой коэффициент (y1 — у0)/(x1 — x0). Значение ошибки в начальной точке отрезка (0,0) принимается равным нулю и первая ячейка заполняется. На следующем шаге к ошибке прибавляется угловой коэффициент и анализируется её значение, если ошибка меньше 0.5, то заполняется ячейка (x0+1, у0), если больше, то заполняется ячейка (x0+1, у0+1) и из значения ошибки вычитается единица. На картинке ниже жёлтым цветом показана линия до растеризации, зелёным и красным — расстояние до ближайших ячеек. Угловой коэффициент равняется одной шестой, на первом шаге ошибка становится равной угловому коэффициенту, что меньше 0.5, а значит ордината остаётся прежней. К середине линии ошибка пересекает рубеж, из неё вычитается единица, а новый пиксель поднимается выше. И так до конца отрезка.

Читать еще: Как восстановить то что удалил из корзины

Ещё один нюанс. Если проекция отрезка на ось x меньше проекции на ось y или начало и конец отрезка переставлены местами, то алгоритм не будет работать. Чтобы этого не случилось, нужно проверять направление вектора и его наклон, а потом по необходимости менять местами координаты отрезка, поворачивать оси, и, в конечном итоге, сводить всё к какому-то одному или хотя бы двум случаям. Главное не забывать во время рисования возвращать оси на место.

Для оптимизации расчётов, применяют трюк с умножением всех дробных переменных на dx = (x1 — x0). Тогда на каждом шаге ошибка будет изменяться на dy = (y1 — y0) вместо углового коэффициента и на dx вместо единицы. Также можно немного поменять логику, «передвинуть» ошибку так, чтобы граница была в нуле, и можно было проверять знак ошибки, это может быть быстрее.

У алгоритма Брезенхэма есть модификация для рисования окружностей. Там всё работает по схожему принципу, в чём-то даже проще. Расчёт идёт для одного октанта, а все остальные куски окружности дорисовываются по симметрии.

Теперь про алгоритм У Сяолиня для рисования сглаженных линий. Он отличается тем, что на каждом шаге ведётся расчёт для двух ближайших к прямой пикселей, и они закрашиваются с разной интенсивностью, в зависимости от удаленности. Точное пересечение середины пикселя даёт 100% интенсивности, если пиксель находится на расстоянии в 0.9 пикселя, то интенсивность будет 10%. Иными словами, сто процентов интенсивности делится между пикселями, которые ограничивают векторную линию с двух сторон.

На картинке выше красным и зелёным цветом показаны расстояния до двух соседних пикселей.

Для расчёта ошибки можно использовать переменную с плавающей запятой и брать значение ошибки из дробной части.

Если вам вдруг в будущем придётся работать с сетками, задумайтесь ненадолго, возможно вы изобретаете велосипед и на самом деле вы работаете с пикселями, хотя и не знаете этого. Модификации этих алгоритмов можно использовать в играх для поиска ячеек перед юнитом на карте, расчёта области поражения выстрела или красивой расстановки объектов. Или можно просто рисовать линии, как в программе по ссылкам ниже.

Unity Web Player | Windows | Linux | Mac | Исходники на GitHub
Левая кнопка мыши — Брезенхем, правая кнопка мыши — У, пробел — очистить, Esc — выход.
Для пользователей Linux: Сделайте файл BresenhamWu исполняемым с помощью «chmod +x BresenhamWu» и запускайте.

Алгоритм генерации линии Брезенхэма

Дана координата двух точек A (x1, y1) и B (x2, y2). Задача найти все промежуточные точки, необходимые для рисования линии АВ на экране компьютера в пикселях. Обратите внимание, что каждый пиксель имеет целочисленные координаты.

Ниже приведены некоторые предположения, чтобы сохранить алгоритм простым.

Мы рисуем линию слева направо.
х1

// C ++ программа для генерации строк Брезенхэма
// Допущения:
// 1) Линия рисуется слева направо.
// 2) x1
// 3) Наклон линии между 0 и 1.
// Рисуем линию от левого нижнего к верхнему
// право.
#include

using namespace std;

// функция для генерации строки

void bresenham( int x1, int y1, int x2, int y2)

int m_new = 2 * (y2 — y1);

int slope_error_new = m_new — (x2 — x1);

for ( int x = x1, y = y1; x

// Добавить наклон к сформированному углу приращения

// Ошибка наклона достигла предела, время до

// увеличиваем y и обновляем ошибку наклона.

if (slope_error_new >= 0)

slope_error_new -= 2 * (x2 — x1);

int x1 = 3, y1 = 2, x2 = 15, y2 = 5;

bresenham(x1, y1, x2, y2);

// Java-программа для генерации линии Bresenhams
// Допущения:
// 1) Линия рисуется слева направо.
// 2) x1
// 3) Наклон линии между 0 и 1.
// Рисуем линию от левого нижнего к верхнему
// право.

// функция для генерации строки

static void bresenham( int x1, int y1, int x2,

int m_new = 2 * (y2 — y1);

int slope_error_new = m_new — (x2 — x1);

for ( int x = x1, y = y1; x

System.out.print(«(» +x + «,» + y + «)n»);

// Добавить наклон к сформированному углу приращения

// Ошибка наклона достигла предела, время до

// увеличиваем y и обновляем ошибку наклона.

if (slope_error_new >= 0 )

slope_error_new -= 2 * (x2 — x1);

public static void main (String[] args)

int x1 = 3 , y1 = 2 , x2 = 15 , y2 = 5 ;

bresenham(x1, y1, x2, y2);

// Этот код предоставлен Anant Agarwal.

# Программа Python 3 для поколения Брезенхэма
# Допущения:
# 1) Линия проводится слева направо.
# 2) x1
# 3) Наклон линии между 0 и 1.
# Мы рисуем линию от левого нижнего к верхнему
# право.

# функция для генерации строки

def bresenham(x1,y1,x2, y2):

m_new = 2 * (y2 — y1)

slope_error_new = m_new — (x2 — x1)

for x in range (x1,x2 + 1 ):

print ( «(» ,x , «,» ,y , «)n» )

# Добавить наклон в угол приращения

slope_error_new = slope_error_new + m_new

# Ошибка наклона достигла предела, время до

# увеличить y и обновить ошибку наклона.

if (slope_error_new > = 0 ):

slope_error_new = slope_error_new — 2 * (x2 — x1)

if __name__ = = ‘__main__’ :

bresenham(x1, y1, x2, y2)

# Этот код предоставлен ash264

// C # программа для генерации линии Брезенхамса
// Допущения:
// 1) Линия рисуется слева направо.
// 2) x1
// 3) Наклон линии между 0 и 1.
// Рисуем линию от левого нижнего к верхнему
// право.

// функция для генерации строки

static void bresenham( int x1, int y1, int x2,

int m_new = 2 * (y2 — y1);

int slope_error_new = m_new — (x2 — x1);

for ( int x = x1, y = y1; x

Console.Write(«(» + x + «,» + y + «)n»);

// Добавить наклон к сформированному углу приращения

// Ошибка наклона достигла предела, время до

// увеличиваем y и обновляем ошибку наклона.

if (slope_error_new >= 0)

slope_error_new -= 2 * (x2 — x1);

public static void Main ()

int x1 = 3, y1 = 2, x2 = 15, y2 = 5;

bresenham(x1, y1, x2, y2);

// Этот код предоставлен нитин митталь.

// PHP программа для Брезенхема
// Предположение генерации строки:

// 1) Линия рисуется из
// слева направо.
// 2) x1
// 3) Наклон линии
// между 0 и 1.
// Рисуем линию снизу
// слева направо

// функция для генерации строки

function bresenham( $x1 , $y1 , $x2 , $y2 )

$m_new = 2 * ( $y2 — $y1 );

$slope_error_new = $m_new — ( $x2 — $x1 );

for ( $x = $x1 , $y = $y1 ; $x $x2 ; $x ++)

echo «(» , $x , «,» , $y , «)n» ;

// Добавить наклон в приращение

// Ошибка наклона достигла предела,

// время увеличивать y и

// обновить ошибку наклона.

if ( $slope_error_new >= 0)

$slope_error_new -= 2 * ( $x2 — $x1 );

$x1 = 3; $y1 = 2; $x2 = 15; $y2 = 5;

bresenham( $x1 , $y1 , $x2 , $y2 );

// Этот код предоставлен нитин митталь.
?>

Вышеприведенное объяснение должно дать приблизительное представление об алгоритме. Для подробного объяснения и доказательства читатели могут ссылаться на ссылки ниже.

Статьи по Теме:

Эта статья предоставлена Шивам Прадхан (anuj_charm) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Алгоритм брезенхема java

Друзья

Алгоритм Брезенхэма

Прим. В зависимости от перевода, иногда его называют алгоритм Брезенхема.

Рассмотрим произвольный отрезок p ₁ ( x ₁ , y ₁ ) – p ₂ ( x ₂ , y ₂ ) :

Чтобы растеризовать его можно поступить следующим образом (небольшая модификация алгоритма DDA-линии):

посчитаем длины отрезка по осям координат lengthX = | x ₂ – x ₁ | и lengthY = | y ₂ – y ₁ | ;
выберем большую из них length = max ( lengthX , lengthY ) ;
случай length == 0 особый: закрашиваем пиксел ( x ₁ , y ₁ ) = ( x ₂ , y ₂ ) и завершаем работу алгоритма;
допустим большая длина оказалась lengthX . Установим начальную точку x = x₁, y = y₁ ;
сделаем length + 1 итераций:
закрашиваем пиксел с координатами ( x , roundf ( y )) ;
координата x увеличивается на единицу, координата y увеличивается на lengthY / length X .

Прим. roundf – округление до ближайшего целого.

Прим. Обратите внимание, что | x ₂ – x ₁ | и | y ₂ – y ₁ | это расстояния между центрами первого и последнего пикселей.

#define roundf(x) floor(x + 0.5f )

void line(HDC hdc, int x1, int y1, int x2, int y2)
<
int lengthX = abs(x2 — x1);
int lengthY = abs(y2 — y1);

int length = max(lengthX, lengthY);

if (length == 0)
<
SetPixel(hdc, x1, y1, 0);
>

if (lengthY
<
// Начальные значения
int x = x1;
float y = y1;

// Основной цикл
length++;
while (length—)
<
SetPixel(hdc, x, roundf(y), 0);
x++;
y += float (lengthY) / lengthX;
>
>
else
<
// Начальные значения
float x = x 1;
int y = y 1;

// Основной цикл
length ++;
while (length—)
<
SetPixel(hdc, roundf(x), y, 0);
x += float (lengthX) / lengthY;
y++;
>
>
>

При таком подходе x является целочисленной переменной, в то время как y – вещественная. Также заметим, что координата x всегда увеличивается на единицу, хотя x₂ может быть меньше x₁ . То же замечание относится к координате y .

Итак, приведенный выше алгоритм обладает двумя существенными недостатками:

Он работает только в первой четверти.
Используются вычисления с плавающей точкой.

Распространение алгоритма на всю плоскость

Делений становится меньше

Теперь избавимся от вычислений с плавающей точкой. Можно поступить по аналогии с оптимизацией к алгоритму DDA, используя вычисления с фиксированной точкой. Но в данном случае можно даже не использовать операцию деления.

Рассмотрим основной цикл. Сначала оптимизируем цикл для случая lengthY lengthX , для другого случая все делается аналогично. Заметим, что изначально y является целой величиной. В цикле y изменяется на дробь со знаменателем lengthX . Т.о. х также является дробью со знаменателем lengthX . Избавимся от знаменателя, домножив на него: // Начальные значения int x = x 1; int y = y 1 * lengthX ; // Основной цикл length++; while (length—) < SetPixel(hdc, x, roundf( float (y) / lengthX), 0); x += dx; y += dy * lengthY; >Увы, но при отрисовке пикселя мы снова должны прибегать к делению. Идея состоит в том, что величина y / lengthX за шаг меняется не более чем на единицу. Разобьем y на целую часть и приращение следующим образом:

y = z + c , где z это y , округленная до ближайшего целого, а с принадлежит отрезку [-0.5; 0.5] . То, что с принадлежит отрезку [-0.5; 0.5] гарантирует нам, что z — это действительно y, округленное до ближайшего целого. Нашей задачей будет поддержание величины c в этих границах. Рассмотрим исходный вариант реализации основного цикла: // Начальные значения int x = x 1; float y = y 1; // Основной цикл length ++; while (length—) < SetPixel(hdc, x, roundf(y), 0); x += dx; y += dy * float (lengthY) / lengthX; >Внесем необходимые изменения: // Начальные значения int x = x 1; int y = y1; float c = 0; // Основной цикл length++; while (length—) < SetPixel(hdc, x, y, 0); x += dx; c += dy * float (lengthY) / lengthX; if (c >0.5) < c--; y++; >if (c c++; y—; > > Чтобы не делать несколько сравнений можно величину с всегда увеличивать в положительную сторону. Тем самым сравнивать придется только с 0.5, но при этом у будет менятся на dy : // Начальные значения int x = x 1; int y = y1; float c = 0; // Основной цикл length++; while (length—) < SetPixel(hdc, x, y, 0); x += dx; c += float (lengthY) / lengthX; if (c >0.5) < c --; y += dy ; >> Начнем избавляться от дробей. Сперва заметим, что можно сделать замену d = 2 * c — 1 , при этом d сравнивается с нулем: // Начальные значения int x = x 1; int y = y1; float d = -1; // Основной цикл length++; while (length—) < SetPixel(hdc, x, y, 0); x += dx; d += 2 * float (lengthY) / lengthX; if (d >0) < d -= 2; y += dy; >>Прим. При линейных заменах ( u = a * v + b ) правила следующие:

Считаем, что замена имеет смысл, т.е. не рассматривются варианты a = 0. Тогда замена обратима:

v = (1 / a) – b / a

Присвоение переменной преобразуется по линейному закону:

v = 2 > u = a * 2 + b

При сравнении переменной, величина, с которой производится сравнение, преобразуется по линейному закону:

v >0.5 > u > a * 0.5 + b

Если v увеличивается на некоторую величину, то u увеличивается на ту же величину, помноженную на a :

v -= 4 > u -= 4 * a;

В остальных ситуациях нужно внимательно следить, чтобы преобразования обоих величин сохраняли линейный закон их соответствия.

Вернемся к алгоритму. Последним штрихом будет применение оптимизации, рассмотренной в начале: // Начальные значения int x = x 1; int y = y1; int d = -lengthX; // Основной цикл length++; while (length—) < SetPixel(hdc, x, y, 0); x += dx; d += 2 * lengthY; if (d >0) < d -= 2 * lengthX; y += dy ; >>

0 0 голоса

Рейтинг статьи