Есть ошибка в алгоритме Брешенема из Википедии?

Question

Bresenham's algorithm используется для рисования линии на квадратной сетке, например, в виде пикселей.

Алгоритм частично основан на разбиении плоскости на 8 частей, называемых октантами.

Хитрость заключается в том, чтобы использовать симметрии обобщить алгоритм, независимо от того, где расположен второй момент: во-первых, мы «двигаться» его на первом октанте, то расчеты, и, наконец, очки генерироваться преобразуются обратно в исходный октант.

В Википедии есть basic function, чтобы выполнить трюк.

function switchToOctantZeroFrom(octant, x, y) 
    switch(octant) 
    case 1: return (x, y) 
    case 2: return (y, x) 
    case 3: return (y, -x) 
    case 4: return (-x, y) 
    case 5: return (-x, -y) 
    case 6: return (-y, -x) 
    case 7: return (-y, x) 
    case 8: return (x, -y) 

Кроме того, написано, что мы должны просто:

флипом система координируют на входе и выходе

Это основано на том факте, что эти транспозиции фактически являются involutions: f(f(x)) = x

Не обращая на это особого внимания, я сначала подумал, что это сработает.

Но для случаев 3 и 7 это не работает, потому что это не инволюция.

Например:

Case 4: (-5, 1) => (5, 1) => (-5, 1) // Good 
Case 3: (-1, 5) => (5, 1) => (1, -5) // Not good 

Мы должны сделать трюк еще раз:

Case 3: (-1, 5) => (5, 1) => (1, -5) => (-5, -1) => (-1, 5) // Good 

Так, я что-то неправильно?

Или это на самом деле недостаток точности при составлении статьи в Википедии, и кто-то должен ее улучшить?

Нет ли лучшего способа сделать эти переходы без этого, мне нужно использовать две функции switchToOctant_onInput и switchToOctant_onOutput (очевидное решение этой проблемы, которое я вижу сейчас)?

Answer 1

Октанты 2, 4, 6, 8 отображаются в октант 1 отражениями, которые являются инволютивными (самообратными).Октант 5 отображается на октант 1 с помощью поворота на 180 градусов, что также является инволютивным. Однако октанты 7 и 3 сопоставляются с октаном 1 с вращением +90 градусов, которые не являются инволютивными. Отображения просто не являются инволютивными, поэтому вы ничего не можете с этим поделать. Если вам нужна обратная функция, вы должны ее написать.

Страница Википедии вводит в заблуждение, поскольку говорит, что функция представляет собой «флип», который предлагает инволюцию.

Существует три подхода, которые я могу придумать для решения проблемы: 1) создать обратную функцию, которая очень похожа, за исключением случаев, когда случаи для 3 и 7 меняются местами (не переименовывайте существующую функцию); 2) добавьте случаи для отрицательных октантов, которые представляют собой обратную функцию, так что обратная величина switchOctant(3,x,y) равна switchOctant(-3,x,y), что совпадает с switchOctant(7,x,y) (однако вы должны тщательно подумать об октанте 0, если вы это сделаете); или 3) уменьшить или устранить необходимость в функции геометрического преобразования, улучшив функцию рисования линии. В частности, если вы улучшите функцию рисования линии для обработки любой строки в первом квадранте (а не только в первом октане!), Вы можете использовать геометрическое преобразование, отображающее любой квадрант в первый квадрант, который равен инволютивным.

Update

Я просто подумал, что еще один «угол» по этому вопросу (так сказать): можно сопоставить 3-й октант к 1-й октанту по отражению. Отражение от линии, проходящей через начало координат с наклоном тета задается

x' = x * cos(2*theta) + y * sin(2*theta) 
y' = x * sin(2*theta) - y * cos(2*theta) 

Линия отражения между 1-й и 3-й октантов имеет угол наклона theta = 45 + 45/2.0 градусов, так 2*theta = 135 градусов, и мы имеем

x' = -sqrt(2)/2 * x + sqrt(2)/2 * y 
y' = sqrt(2)/2 * x + sqrt(2)/2 * y 

Подобные формулы можно использовать для отображения 7-го октанта в 1-й. Таким образом, можно найти инволюцию, которая отображает каждый октант в первый октант. Тем не менее, есть две проблемы с этим отображением: 1) он не является непрерывным, тогда как отображение, данное в статье в Википедии, является непрерывным (что означает, что в изображении (x,y) нет резких скачков, поскольку точка перемещается вокруг плоскости); и 2) неясно, как использовать целочисленную арифметику для осуществления сопоставления.

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

Так что эта идея не очень хорошая, но я просто подумал, что упомянул об этом ради полноты.

Answer 2

Обсуждение октанта в алгоритме Брешенема основано на очевидных осевых симметриях относительно медиан и диагоналей. Не требуется свойство инволюции. (Если вам нужен обратный f, ну, используйте ... обратный f, но это явно не требуется).

Простой вариант является цифровой версией параметрического уравнения линии:

X = X0 + (k.(X1 - X0))/D 
Y = Y0 + (k.(Y1 - Y0))/D 

где

D = Max(|X1 - X0|, |Y1 - Y0|) 

и k в диапазоне [0..D].