У меня есть сетка из прямоугольных ячеек, покрывающая плоскость, находящуюся на некотором расстоянии от начала координат, и я хотел бы определить ячейку сетки, где прямая линия, начинающаяся в начале координат, пересекает ее.
Ячейки на сетке имеют одинаковые размеры (dx, dy), и между ячейками нет промежутков, но, поскольку каждая ячейка на плоскости имеет различное расстояние от начала координат, телесный угол, который они покрывают, не является постоянным - если я мог найти простую функцию, которая переводит направление (тэта, фи) в индекс клетки (ix, iy).
В настоящее время я использую что-то вроде поиска ближайшего соседа, чтобы найти ячейки, но это вообще не использует "привязку к сетке" моих ячеек. Есть ли какой-нибудь алгоритм, который помог бы мне улучшить это?
EDIT
Я знаю, что мог бы просто использовать простую тригонометрию, чтобы получить ячейку, но меня больше интересует, какие существуют алгоритмы, которые выполняют поиск ближайшего соседа на регулярно расположенных входах.