Рисование закрашенных кругов и треугольников на Raspberry Pi Pico с помощью MicroPython

[DimPal]

А как же алгоритм Брезенхема для окружности? Там в цикле можно без умножений, корней и тригонометрии обойтись (могу все на пальцах объяснить).

[N-Cube]

Интересно, как обойтись без умножений в цикле? Если квадрат числа можно через приращения с умножением на 2 расписать, то дальше упрощать некуда. Если вы про битовый сдвиг, то это все равно будет умножение на двойку, только иначе записанное (причем компиляторы такие операции давно как умеют оптимизировать сами).

[masai]

Алгоритм Брезенхема тем и хорош, что там только сложение, вычитание и умножение на два (то есть, сдвиг) и всё. А в алгоритме из статьи аж два возведения в квадрат и квадратный корень. То есть, тут ещё и вычисления с плавающей точкой.

[N-Cube]

Да, статья уровня «два ядра 100+ МГц и несколько аппаратных стейтмашин могут лампочкой помигать». А алгоритм Брезенхема это просто инкрементальное использование тождества (X + 1)^2 = X^2 + 2X + 1 в целых числах :)

[DimPal]

Предположим в цикле требуется получить квадрат числа: 0, 1, 4, 9, 16, 25, 36.

Приращение на каждом шаге: +1, +3, +5, +7, +9, +11.

Получаем:

int x=0;

int dx=1;

for(...)

{

print(x);

x += dx;

dx += 2;

}

[N-Cube]

Это вы из тождества (X + 1)^2 = X^2 + 2X + 1 расписали 2*x как сумму x двоек, а инкрементальный счетчик позволяет при каждой итерации только одну двойку прибавлять - математически эквивалентно получается. Будет ли выигрыш вычислительный - вряд ли. А вообще пример хороший для ручного счета, продемонстрировать, как же без компьютеров вычисления делали.

[DimPal]

вычислительный выигрыш зависит от множества факторов: аппаратное умножение на CPU, скорость чтения/записи двух переменных вместо одной, в кэш какого уровня попадют пернеменные цикла (и какова его скорость), ну и от фазы луны может зависеть немного :) Кстати, с небольшим понижением точности можно и от умножения на два избавиться в цикле, но это уже будет не Брезенхем, а велосипед по его мотивам. Идея примерно такая: на каждом следущм сканлайне нам ведь нужно решить - двигаться прямо или по диагонали. Для этого нужно оценить какой из шагов даёт меньшую погрешность (отклонение). Так вот если считать эту погрешность не по радиусу, а по его квадрату, задача сильно упрощается (правда немного теряем в точности).