Я стираю пыль со своего старого проекта. Одна из вещей, которую он должен был сделать, это - учитывая декартову систему координат и два квадрата на сетке, найти список всех квадратов, через которые будет проходить линия, соединяющая центр этих двух квадратов.
Особым случаем здесь является то, что все начальная и конечная точки ограничены точным центром квадратов / ячеек.
Вот несколько примеров - с парами начальных и конечных точек выборки. Заштрихованные квадраты - это те, которые должны быть возвращены соответствующим вызовом функции.
удалена неработающая ссылка на ImageShack - пример
Начальная и конечная точки обозначаются квадратами, в которых они находятся. На приведенном выше рисунке, если предположить, что нижний левый угол - это [1,1], линия справа внизу будет идентифицирована как от [6,2] до [9,5].
То есть от (центра) квадрата в шестом столбце слева, во втором ряду снизу до (центра) квадрата на девятый столбец слева, в пятом ряду снизу
Что действительно не кажется таким сложным. Однако каким-то образом мне показалось, что я нашел в сети какой-то сложный алгоритм и реализовал его.
Я помню, что это было очень и очень быстро. Мол, оптимизировано для сотен или тысяч раз на кадр быстро.
По сути, он прыгал от границы к границе квадратов, вдоль линии (точек, где линия пересекает линии сетки). Он знал, где находится следующая точка пересечения, видя, какая точка пересечения находится ближе - горизонтальная или вертикальная - и перемещалась к следующей.
Это вроде нормально в концепции, но фактическая реализация оказалась довольно не очень красивой, и я боюсь, что уровень оптимизации может быть слишком высоким для того, что мне практически нужно (я называю этот обход алгоритм может быть пять или шесть раз в минуту).
Есть ли простой, понятный и прозрачный алгоритм обхода прямой сетки?
С точки зрения программирования:
def traverse(start_point,end_point)
# returns a list of all squares that this line would pass through
end
где заданные координаты определяют сами квадраты.
Некоторые примеры:
traverse([0,0],[0,4])
# => [0,0], [0,1], [0,2], [0,3], [0,4]
traverse([0,0],[3,2])
# => [0,0], [0,1], [1,1], [2,1], [2,2], [3,2]
traverse([0,0],[3,3])
# => [0,0], [1,1], [2,2], [3,3]
Обратите внимание, что линии, проходящие непосредственно через углы, не должны включать квадраты на «крыле» линии.
(Здесь может сработать старый добрый Брезенхэм, но он немного отстает от того, что я хочу. Насколько я знаю, для того, чтобы использовать его, мне пришлось бы применить его к строке, а затем сканировать каждую квадрат на сетке для истинности или ложности. Невозможно - или, по крайней мере, неэлегантно - для больших сеток)
(Я пересматриваю алгоритмы Брезенхэма и Брезенхэма из-за моего недопонимания)
Для пояснения, одно из возможных применений этого было бы, если бы я хранил все свои объекты в игре внутри зон (сетка), и у меня есть луч, и я хочу видеть, каких объектов он касается. Используя этот алгоритм, я мог тестировать луч только для объектов, находящихся в заданных зонах, а не для каждого объекта на карте.
Фактическое использование этого в моем приложении заключается в том, что каждая плитка имеет связанный с ней эффект, и объект перемещается по заданному сегменту линии каждый поворот. На каждом шагу необходимо проверять, через какие квадраты прошел объект и, следовательно, какие эффекты применить к объекту.
Обратите внимание, что на данный момент текущая реализация, которая у меня есть, действительно работает. Этот вопрос в основном из любопытства. Должен быть более простой способ ... как-нибудь ... для такой простой проблемы.
Что именно я ищу? Что-то концептуально / аккуратное и чистое. Кроме того, я понял, что из-за того, что я точно указываю, все начальные и конечные точки всегда будут в центре квадратов / ячеек; так что, возможно, что-то, что использует это в своих интересах, тоже было бы изящным.
