Я отряхиваю свой старый проект. Одна из вещей, которую он должен был сделать, - с учетом декартовой системы координат и двух квадратов на сетке найти список всех квадратов, через которые пройдет линия, соединяющая центр этих двух квадратов.
Особый случай здесь заключается в том, что все начальные и конечные точки ограничены точным центром квадратов / клеток.
Вот несколько примеров - с парами начальных и конечных точек выборки. Затененные квадраты - это те, которые должны быть возвращены соответствующим вызовом функции
удалена мертвая ссылка 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]
Обратите внимание, что линии, проходящие непосредственно через углы, не должны содержать квадратов на "крыле" линии.
(Здесь могут работать добрые старины Брезенхэма, но это немного отстает от того, что я хочу. Насколько я знаю, для того, чтобы использовать его, мне в основном пришлось бы применить его к линии, а затем сканировать каждый квадрат на сетке на наличие истинного или ложного. Невозможно - или, по крайней мере, не элегантно - для больших сеток)
(я пересматриваю алгоритмы Брезенхэма и Брезенхема на основе моего неправильного понимания)
Для пояснения, одно из возможных применений этого было бы, если бы я хранил все свои объекты в игре внутри зон (сетка), и у меня есть луч, и я хочу увидеть, к каким объектам этот луч касается. Используя этот алгоритм, я мог проверить луч только для объектов, которые находятся в пределах указанных зон, а не для каждого объекта на карте.
Фактическое использование в моем приложении состоит в том, что каждая плитка имеет связанный с ней эффект, и объект проходит через данный отрезок линии каждый ход. На каждом шагу необходимо проверять, через какие квадраты прошел объект и, следовательно, какие эффекты применить к объекту.
Обратите внимание, что на данный момент текущая реализация, которую я имею, работает. Этот вопрос в основном для любопытства. Должен быть более простой способ ... как-то ... для такой простой проблемы.
Что я ищу именно? Что-то концептуально / аккуратно и чисто. Кроме того, я понял, что из-за того, что я точно указываю, все начальные и конечные точки всегда будут в центре квадратов / ячеек; так что, возможно, что-то, что использует в своих интересах, было бы также опрятно.