Как решалась переменная решения в алгоритме линии Брешенхама?

Question

Каждые статьи я изученные о Bresenham линии алгоритма, они говорят о решении переменной

Pi = dx * (d1 - d2) 

Где идея этого mathematical term родом?

Я имею в виду, какова была идея принятия dx * (d1 - d2) в качестве переменной решения?

Почему не было d1 - d2?

Here is one of the articles.

Answer 1

Поскольку единственная информация, мы заботимся о том, в d1-d2 знак, мы можем умножить его на любое положительное значение, и ничего не потерять. Фактически мы не знаем значения d1 и d2, которые сразу же вызывают алгоритм и должны рассчитать их значения из того, что мы знаем. Однако этот расчет включает деление на dX, а деление - медленное и, по возможности, следует избегать. Как это бывает, dX всегда положительный, поэтому мы можем просто умножать d1 и d2 на dX, чтобы удалить операцию деления, не теряя информацию, которую мы ищем.

Answer 2

Алгоритм Брешенема работает, сосредоточившись на одной части круга, разрезанной на секции 45 градусов, и решает только один из них. Круг формируется путем рассмотрения всех линий, которые можно было бы нарисовать из точки x1, y1 (т. Е. Первого переданного параметра). Однако, поскольку он сосредоточен только на одном разделе (т. Е. Скажем, что х растет быстрее, чем у в положительном направлении), чтобы обобщить решение на все строки, которые могут быть сформированы, он должен преобразовать все остальные части этого круга, преобразованные в один он знает, как рисовать круг. Обычно вы увидите некоторый код инициализации, который соответствует вершине алгоритма, который гарантирует, что x1, y1 < x2, y2 и заменяет их, если это не выполняется. Это эффективно сокращает круг пополам по количеству строк, которые он должен обрабатывать. Итак, теперь только 4 разных склона должны обрабатываться следующей частью кода. Переменная решения - это оптимизация для определения того, из какого из четырех разделов алгоритм попадает. Мы всегда находимся в положительном направлении X, но вопрос в том, что мы движемся вверх/вниз быстрее, чем X (разделы 1 & 4-начальное положение по часовой стрелке) или X движется быстрее, чем Y (разделы 2 & 3).

Переменная решения не позволяет нам делать оператор if на каждой итерации цикла.