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

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

 

Алгоритм Брезенхема был предложен Джеком Е. Брезенхэмом (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|<|B|

с каждым шагом осуществляется движение по горизонтали или диагонали.
Если угол наклона больше 45º, с каждым шагом движение осуществляется вертикали или диагонали.
Таким образом, алгоритм рисования наклонного отрезка следующий:
Алгоритм Брезенхема
Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
using namespace std;
void Brezenhem(char **z, int x0, int y0, int x1, int y1)
{
  int A, B, sign;
  A = y1 - y0;
  B = x0 - x1;
  if (abs(A) > abs(B)) sign = 1;
  else sign = -1;
  int signa, signb;
  if (A < 0) signa = -1;
  else signa = 1;
  if (B < 0) signb = -1;
  else signb = 1;
  int f = 0;
  z[y0][x0] = '*';
  int x = x0, y = y0;
  if (sign == -1) 
  {
    do {
      f += A*signa;
      if (f > 0)
      {
        f -= B*signb;
        y += signa;
      }
      x -= signb;
      z[y][x] = '*';
    } while (x != x1 || y != y1);
  }
  else
  {
    do {
      f += B*signb;
      if (f > 0) {
        f -= A*signa;
        x -= signb;
      }
      y += signa;
      z[y][x] = '*';
    } while (x != x1 || y != y1);
  }
}
int main()
{
  const int SIZE = 25; // размер поля
  int x1, x2, y1, y2;
  char **z;
  z = new char*[SIZE];
  for (int i = 0; i < SIZE; i++) 
  {
    z[i] = new char[SIZE];
    for (int j = 0; j < SIZE; j++)
      z[i][j] = '-';
  }
  cout << "x1 = ";     cin >> x1;
  cout << "y1 = ";     cin >> y1;
  cout << "x2 = ";     cin >> x2;
  cout << "y2 = ";    cin >> y2;
  Brezenhem(z, x1, y1, x2, y2);
  for (int i = 0; i < SIZE; i++) 
  {
    for (int j = 0; j < SIZE; j++)
      cout << z[i][j];
    cout << endl;
  }
  cin.get(); cin.get();
  return 0;
}

Результат выполнения
Алгоритм Брезенхема: результат
Алгоритм Брезенхема: результат

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


Назад: Алгоритмизация

Комментариев к записи: 5

  • Описание алгоритма не соответствует блок-схеме. Вроде работает, но на блок-схеме координаты отрисовки постоянно пытаются быть выше линии, хотя в описании сказано, что переход на следующую координату происходит только после сравнения отрезка |P-Q|. Потратил кучу времени что бы понять, почему то, что алгоритм рисует не подходит под то, что ожидается в алгоритме Брейзенхейма здорового человека.

  • В сравнеии недочет. Нужно сравнить модули A и B. Из-за этого программа будет работать некоректно

  • Дмитрий
    Здравствуйте! Есть некоторая неточность в алгоритме, а именно - сравнение "A<B" в алгоритме выполняется над знаковыми разностями, а на самом деле сравнивать нужно модули. Также можно исключить умножение на знак (a*signa и b*signb), поскольку эти произведения всегда являются модулями значений A и B.

  • Арсений Слободюк
    Спасибо, Елена, за понятное объяснение и элегантный код, очень всё упаковано, а ведь есть 8 вариантов знаков и отношений модулей A и B. Теперь критика: На блок-схеме нет модуля в условии A<B. Для рисования качественных линий  условия f > 0 недостаточно, надо сравнивать модули ошибки для двух случаев. Т.е. первое 'f > 0' заменяется на abs(f) > abs(f-abs(B)), а второе - на abs(f-abs(A)). А так алгоритм "идет" сбоку от идеальной прямой. abs оператор недорогой, любая ардуина потянет. Можно даже (но не в учебной программе) удалить знаки у A & B вначале, после вычисления signa & signb.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *