Линейный алгоритм Брезенхема против сложного наивного вектора

Дано xlen дельта-х, ylen дельта-у, len это длина строки, почему этот код:

//Bresenham implementation
float x = x0, y = y0;

if (slope < 1) {
while (x < xlen) {
paintpt(x, y));
x += step;
if (left.y > right.y)
y += slope * step;
else
y -= slope * step;
}
}

более эффективный, чем этот код?

//Naive vector addition
int x = x0, y = y0;
float xinc = xlen / len, yinc = ylen / len;

for (float i = 0; i < len; i++) {
paintpt(x, y);
x += i * xinc;
y += i * yinc;
}

(Я имею в виду, кроме инициализации, очевидно. Предположим, что вам даны только длина линии и направление, и вы должны отступить от наклона и еще много чего.)

1

Решение

1) x += i * xinc; это умножение с плавающей точкой, округленное до целого числа. Это не гарантирует, что вы пройдете все целые числа с самого начала x в ваш финал x, Это означает, что в вашей линии могут быть дыры …

2) Ваша реализация в Брезенхэме неверна. Вы не добавляете шаги в x, Вы увеличиваете xна каждой итерации и добавить delta_y к счетчику ошибок. Когда счетчик ошибок больше delta_x Вы увеличиваете y и вычесть delta_x из счетчика ошибок.

Это объяснение линии, чья delta_y больше 0 и уступает delta_x, Делайте ротацию для всех остальных случаев.

3) Для эффективности: это немного сложно. Старые компьютеры не могли легко выполнять вычисления с плавающей запятой. Вплоть до Pentium не было никакого сопроцессора x87, и все вычисления с плавающей запятой выполнялись программно. Это было в 1000 раз медленнее, чем простая целочисленная арифметика. В настоящее время все компьютеры могут выполнять операции SIMD (т.е. они используют векторные расширения с плавающей точкой); это может быть не так больше.

3

Другие решения

Алгоритм Брезенхема основан на 60-х годах, когда компьютеры помещались в большие шкафы. Его отличительными чертами были / являются:

  • нет математики с плавающей точкой,
  • нет умножения / деления.

Поскольку в те дни даже целочисленные деления и умножения были «дорогими». «Настоящая» реализация Брезенхэма не будет делить / умножаться и не будет использовать математические вычисления с плавающей запятой. Ваша реализация «ложная». Проверьте Вот для «истинного».

5