Получение ячеек в 2D сетке между двумя углами

Введите описание изображения здесь

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

Зная размер ячейки сетки, количество столбцов и строк, положение начального луча, угол a и угол b, как я могу получить все ячейки, которые попадают между двумя лучами?
1 2
angle vector-graphics

1 ответ:

Если оба луча лежат в одном и том же квадранте или в соседних квадрантах:

Вы можете использовать слегка модифицированный алгоритм Бресенхема, чтобы пройти оба луча вместе параллельно и получить целый столбец или ряд ячеек между ними. Пример псевдокода для случая вашего примера и для (в основном) горизонтального сектора: 

 initialisation for deltaerr1, deltaerr2
 for x from 0 to EndXCoord
         get all cells in column (x,y1)-(x,y2)

         error1 := error1 + deltaerr1
         if error1 ≥ 0.5 then
             y1 := y1 + 1
             error1 := error1 - 1.0

         error2 := error2 + deltaerr2
         if error2 ≥ 0.5 then
             y2 := y2 + 1
             error2 := error2 - 1.0

Если лучи находятся в противоположных квадрантах, то разведите их (и возьмите все промежуточные квадранты)

Некоторые случаи:

1-й и 2-й квадранты: сделать шаги в направлении y, получить строки

1-й и 4-й квадранты: сделайте шаги в направлении x, получите столбцы (как в псевдокоде)

Начало в 1-м и конец угла в 3-м квадрантах: сделайте шаги в направлении y в каждом квадранте, получите все необходимые ячейки во 2-м квадранте

Особые случаи:

Некоторый угол равен n * 90 - возможно, потребуется изменить направление

Лучи делают угол 180°: делают шаги Бресенхема вдоль линии в нужном диапазоне, получают строки или столбцы в выбранном диапазоне. полуплоскость

1