Алгоритм нахождения ячеек сетки, содержащихся в произвольно повернутом прямоугольнике (растеризация)

Question

Я ищу алгоритм, который может вычислить все ячейки сетки, занятые произвольным прямоугольником в 2-мерном пространстве в определенной области. Прямоугольник определяется его четырьмя угловыми координатами. На рисунке ниже я отметил два из них как красный, координаты ячеек сетки выделены черным цветом. Я ищу общий случай, который также охватывает невыровненные сетки (центр сетки!= Центр базовой системы coodinate), но преобразование между координатами ячейки <=> Система координат тривиально и уже реализовано. Все клетки являются квадратами.

Расчет выполняется тысячами в очень короткие сроки и должен быть максимально быстрым.

Что я сейчас делаю:

Прямо сейчас я вычисляю края прямоугольника (AB, BC, CD, DA) и пробую их в sampleRate = cellWidth / 4 интервалы. Чтобы найти средние клетки, я строю новые линии из AB + sampleRate * x в CD + sampleRate * x и снова попробовать эти строки в sampleRate, Я помещаю все ячейки, которые я нахожу в каждой точке выборки, в HashSet для удаления дубликатов. Но я чувствую, что это невероятно неэффективно.

Я также подумал о том, чтобы собрать все ячейки в соответствующей области в буфер и создать дерево диапазонов или дерево индексов. Тогда я мог бы поставить в очередь границы прямоугольника и получить все содержащиеся в нем ячейки в O(log n+m), но я не уверен, как это реализовать, и я даже не могу найти какие-либо реализации дерева диапазонов C#.

Мои знания в компьютерной графике очень ржавые, но разве не должен быть простой геометрический подход, который работает без выборки?

Answer 1

Точки, которые вас интересуют, отмечены точкой на изображении ниже. Каждая точка представляет собой либо минимальное значение X, либо максимальное значение X для данного значения Y. Для каждого значения Y значение X легко вычисляется из уравнения для строки:

x = x ₀ + (y - y ₀) (x ₁ - x ₀) / (y ₁ - y ₀)

Обратите внимание, что выровненный по оси прямоугольник (где (y ₁ - y ₀) равен 0) должен обрабатываться как особый (но тривиальный) случай.

Также обратите внимание, что как только вы вычислили первое значение X по краю прямоугольника, остальные значения X будут равнорасположены. Интервал является обратным к наклону линии. Итак, разделение
M = (x ₁ - x ₀) / (y ₁ - y ₀)
нужно сделать только один раз, а затем многократно добавить к значению X. Например, после вычисления координаты X для точки A на изображении координата X для точки B будет B _x = A _x + M. И координата X для точки C будет C _x = B _x + M.

Если у вас есть минимальное и максимальное значения X для каждого значения Y, это просто for цикл, чтобы получить все ячейки, которые имеют это значение Y.