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

Question

Я хочу найти все пиксели изображения (в декартовых координатах), которые лежат в определенном полярном диапазоне, r_min r_max theta_min и theta_max. Итак, у меня есть некоторый кольцевой раздел, определенный с указанными выше параметрами, и я хочу найти целочисленные координаты x, y пикселей, которые лежат внутри него. Решение грубой силы приходит в середину (проходит через все пиксели изображения и проверяет, находится ли оно в нем), но мне интересно, есть ли у него более эффективное решение.

Благодаря

Answer 1

В решении грубой силы вы можете определить жесткий ограничивающий прямоугольник области, вычислив четыре вершины и включив в себя четыре крайних крайних точки по мере необходимости. Затем для каждого пикселя вам нужно будет оценить два круга (квадратичные выражения) и две прямые (линейные выражения). Выполняя вычисление инкрементально (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 

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

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

Answer 2

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

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

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