Поиск всех пикселей в пределах определенного диапазона в полярных координатах

В решении грубой силы вы можете сначала определить плотную ограничивающую рамку области, вычислив четыре вершины и включив четыре кардинальные крайние точки по мере необходимости. Затем для каждого пикселя вам нужно будет вычислить две окружности (квадратичные выражения) и две прямые линии (линейные выражения). Выполняя вычисления постепенно (X => X+1), количество операций уменьшается практически до нуля.

Внутри круга

f(X,Y) = X²+Y²-2XXc-2YYc+Xc²+Yc²-R² <= 0

Постепенно,

f(X+1,Y) = f(X,Y)+2X+1-2Xc <= 0

Если вы действительно хотите избежать этих накладных расходов, вы прибегнете к методам преобразования строки сканирования. Сначала подумайте о заполнении наклонного прямоугольника. Проведя две горизонтальные линии по промежуточным вершинам, вы разложите прямоугольник на два треугольника и параллелограмм. Тогда для любой линии сканирования, которая пересекает одну из этих фигур, вы заранее знаете, какую пару сторон вы пересечете. Оттуда вы знаете, какую часть строки сканирования вам нужно заполнить.

Вы можете обобщить любую форму, в частности, сегмент круга. Будьте готовы к относительно тонкому анализу случаев, но найти сами пересечения не так сложно. Это может помочь разделить домен вертикалью, проходящей через центр, чтобы любая горизонталь всегда встречалась с контуром дважды, а не четырежды.

Предположим, что центр сечения находится в точке 0,0 для простоты. Если нет, то это легко изменить, сместив все координаты.

Для каждой возможной координаты y от r_max до -r_max найдите координаты x окружности обоих радиусов: -sqrt(r*r-y*y) и sqrt(r*r-y*y). Каждая точка внутри круга r_max и за пределами круга r_min может быть частью сечения и потребует дальнейшего тестирования.

Теперь выполните те же вычисления координаты x, но на этот раз с отрезками, описываемыми углами. Вам понадобится некоторая условная логика, чтобы определить, какая сторона линии находится внутри, а какая снаружи, и влияет ли она на верхнюю или нижнюю часть раздела.