С помощью данного алгоритма можно заполнить (зарисовать) любую окружность.
Теоретическое обоснование метода заключаются в использовании свойства квадрата и теоремы Пито: " в выпуклый четырёхугольник ABCD можно вписать окружность тогда и только тогда, когда суммы его противоположных сторон равны ".
Действительно, любой квадрат является выпуклым четырёхугольником:
- Cостоит из четырех точек и четырех последовательно соединяющих их отрезков;
- Никакие три из данных точек не лежат на одной прямой;
- Соединяющие эти три данных точки отрезки не пересекаются.
Из данного обоснования можно вывести идею,что если любую окружность можно вписать в квадрат, то перебирая все точки, принадлежащие этому квадрату, можно найти все точки,принадлежащие данной окружности или лежащие в ней, если известны координаты центра вписанной окружности и её радиус. Закрасив все такие точки, мы нарисуем и саму окружность, и круг,который этой окружностью ограничен.
Представление алгоритма на языке псевдокода :
- 1.Получить X и Y координаты окружности, радиус окружности R, цвет заполнения color;
- 2.Присвоить переменной cX значение левого края (X-R) описанного квадрата ABCD и начать цикл до правого края (X+R) (BD) с шагом в 1 единицу измерения (пиксель)
- 2.1Присвоить переменной cY значение верхнего края (Y+R) и начать цикл от до нижнего края (Y-R) (CD) с таким же шагом
- 2.1.1.Если значения cX и cY удовлетворяют неравенству (X-cX)2+(Y-cY)2≤Radius2 и в точке с координатами (cX,cY) не стоит точка цвета color, то поставить точку цвета color с координатами (cX, cY)
- 2.2.Закончить цикл по переменной cY
- 3.Закончить цикл по переменной cX
Данный алгоритм имеет сложность O(N2) и выгодно отличается от обобщенного рекурсивного алгоритма заполнения многоугольников потребляемой памятью, имея примерно такое же время работы применимо к окружности. Также, данный алгоритм гарантированно не переполняет стек вызовов, что позволяет закрашивать ему окружность любого радиуса. Недостатками являются сравнительно малая скорость заполнения и сложность O(N2).
Рис 1. Пример работы алгоритма. Синий квадрат показывает границы квадрата ABCD, внутри которого происходит просчёт принадлежности точек окружности
