«Рисование» дуги в дискретных x-y шагах

Question

Каков наилучший способ рисования дуги, используя только движения позиции x-y? Например, скажем, я хочу нарисовать круг с радиусом 4 в точке (4,4). Давайте увидим, что мой «ящик» начинается с (4,0) и с разрешением в 1 шаг в каждом направлении. Как создать последовательность движений для завершения круга?

Если это непонятно, я могу попытаться объяснить лучше.

Answer 1

Если я правильно понимаю ваш вопрос, вы ищете алгоритм Брешенема. Вы можете прочитать об этом here, например.

Answer 2

Вам нужен алгоритм окружности окружности, также известный как алгоритм круга Брешенема (хотя Брешенем не развивал его). В Википедии есть a reasonably good article; также был a Python implementation на викторике LiteratePrograms (которой больше нет - ссылка на Wayback Machine) и several implementations на Rosetta Code. Идея заключается в том, чтобы ходить по кругу, последовательно вычисляя каждую координату из предыдущей (избегая более дорогих математических операций). Вы всегда двигаетесь в одном направлении (скажем «вверх») и используете вычисленную переменную, чтобы решить, следует ли ее поворачивать.