Как найти все квадраты сетки на строке?

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

Основная идея довольно проста. В псевдокоде:

function LineOfSight(point1, point2): boolean
  squares = GetListOfSquaresOnLine(point1, point2)
  for each square in squares
    if square.IsOpaque then return false
  return true

GetListOfSquaresOnLine (концептуально) провел бы прямую линию от центра квадрата сетки в point1 к центру квадрата сетки в point2 и возвратил бы список всех квадратов, через которые проходит эта строка. Но это - первая часть, понятия не имеют, как реализовать. Кто-либо знает, как сделать это? Delphi или предпочтенные примеры C, но не требуемый.

26
задан Mason Wheeler 21 July 2010 в 21:16
поделиться

4 ответа

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

alt text

Поскольку вы упомянули «линию прямой видимости», похоже, вам нужен алгоритм, который перечисляет все квадраты сетки, через которые проходит линия. Этот набор иногда называют суперпокрытием (линии), и здесь описан один алгоритм .

Есть и другие подходы, приведенные в ответах на этот вопрос .

Обновление: Вот еще одна ссылка

36
ответ дан 28 November 2019 в 06:59
поделиться

Разве Алгоритм Брезенхема не то, что вы ищете?

8
ответ дан 28 November 2019 в 06:59
поделиться
8
ответ дан 28 November 2019 в 06:59
поделиться
Другие вопросы по тегам:

Похожие вопросы: