увеличивая ячейки на строке в массиве

Question

Допустим, у меня есть массив 100x100, и я хочу увеличить все ячейки, попадающие на линию, соединяющую две точки в массиве, на 1.

Кто-нибудь имеет алгоритм или знает библиотекучто может сделать это?

Я работаю в PHP, но псевдокод тоже будет в порядке.

Answer 1

Лучший ответ, который у меня сейчас есть, - найти ограничивающий прямоугольник начальной и конечной точек, а затем проверить каждую из ячеек в ограничивающем прямоугольнике и проверить верхний правый и нижний левый углы, чтобы увидеть, находятся ли они над или подline.

Если они оба выше или ниже, то линия не проходит через ячейку.

Если одна сверху, а другая ниже, линия проходит через ячейку.

Я также должен был бы сделать ту же проверку в верхнем левом и нижнем правом углу.

Кажется ли этот алгоритм правильным?

Answer 2

Я думаю, что хороший (возможно, лучший) подход - это использовать алгоритм линии Брезенхэма

Взгляните на: Алгоритм Брезенхема

Answer 3

У меня есть решение, которое больше похоже на математический подход.

Допущения:

• Массив 100X100 имеет размерность 100 x 100 единиц, гдекаждая клетка занимает 1 х 1 единицу.
• Кроме того, каждая точка может быть построена с максимумом одной значащей цифры после десятичной точки, например, для 2,9 единиц.
• Система координат рассматривается с началом координат в верхнем левом углу и с максимумом внизу.правый угол, который будет соответствовать индексам массива.
• Рассмотрим начальную точку как (x1, y1) и конечную точку как (x2, y2).

Математический подход:

• Найдите наклон линии, используя формулу m = (y2 - y1) / (x2 - x1)
• Теперь найдите уравнение линиипоскольку y = m * x + b
• b можно узнать, заменив y на y1, а x на x1.

Алгоритм:

• Давайте проведем итерацию по различным значениям x с начальным значением x1 и unitl x2.Табулируйте y, используя уравнение строки и каждый шаг итерации x как 0,1
• Увеличивайте значение ячейки в начальной точке, а также для каждого массива [floor (x), floor (y)].
• После каждого приращения ячейки увеличивайте значение x на 1, а не на 0,1

Единственное условие, при котором это может быть проблемой, - это случай, когда линия имеет наклон бесконечности, т.е.линия и особый случай могут присутствовать для одного и того же.Я думаю, это должно работать: -)

Answer 4

Если ваша «линия» - это действительная линия (кратчайшее расстояние между двумя точками), а не набор случайных отрезков, возможно, вы можете использовать поиск в ширину, как я делал здесь . Это помогает объяснить немного больше. Это действительно применимо, только когда вся область открыта. Возможно, вам придется изменить это, если диагонали в порядке, и вы хотите использовать PHP вместо ActionScript. Понятия могут помочь вам, хотя.

Однако, если ваша линия - это не линия, а волнистый рисунок, который начинается и заканчивается в точке, то вам, вероятно, нужно выполнить тест пересечения на ваших квадратах, как вы предлагали.

Я не уверен, что у вас будет несколько кратчайших путей с диагоналями на самом деле ... Я все еще думаю, что ваше ограничивающее решение с оптимизацией, вероятно, будет работать лучше, но я не уверен, что это будет на самом деле неправильно любые отсчеты (с диагоналями в порядке и без препятствий.)

Удачи!

Answer 5

Что ж, если у вас есть граница, как в контексте лабиринта, в сочетании с начальной и конечной точкой, есть несколько способов кодирования алгоритма. Некоторые хорошие включают в себя:

1) Flood Fill, затем найдите кратчайший путь к узлу назначения от начального узла. 2) Поиск в глубину от начала до пункта назначения.

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

Надеюсь, это поможет:)