Как найти все квадраты сетки на линии? - PullRequest
26 голосов
/ 22 июля 2010

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

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

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

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

Ответы [ 4 ]

34 голосов
/ 22 июля 2010

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

alt text

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

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

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

8 голосов
/ 22 июля 2010

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

7 голосов
/ 22 июля 2010
1 голос
/ 22 июля 2010
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...