Алгоритм оценки пикселей на основе минимального количества отрезков линии, необходимого для достижения определенной точки, при этом только пересекая действительные области? - PullRequest
Новая
       37

Алгоритм оценки пикселей на основе минимального количества отрезков линии, необходимого для достижения определенной точки, при этом только пересекая действительные области?

0 голосов
/ 08 января 2019

Учитывая массив двумерных пикселей, где любой пиксель может иметь значение 0 или 1, какой алгоритм будет выводить новый массив двумерных пикселей, где каждый пиксель со значением 1 получит новое значение на основе минимального количества требуемых отрезков линии достичь определенного пикселя «источника света», пересекая только пиксели с входным значением 1? Входные значения 0 не изменятся.

Пример входного массива, пурпурный крест представляет пиксель «источника света»:

https://cdn3.imggmi.com/uploads/2019/1/8/2a5f6dd0ebdc9c72115f9ce93af3337a-full.png

Выходной массив с выходными значениями 1 и 2 (Photoshopped, не идеальное изображение):

https://cdn3.imggmi.com/uploads/2019/1/8/0025709aaa826c26ee0a8e17476419cb-full.png

  • Красная область = 1 отрезок линии от источника
  • Желтая область = 2 отрезка линии от источника
  • Белая область = 3 или более отрезка линии от источника

(алгоритм не остановится на 3, он будет продолжаться до тех пор, пока не будет оценен каждый пиксель.)

РЕДАКТИРОВАТЬ: я не уверен, является ли StackOverflow правильным сайтом Stack Exchange для публикации этого, если нет, пожалуйста, дайте мне знать!

1 Ответ

0 голосов
/ 08 января 2019

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

Теперь обработайте ваш точечный источник как прожектор, изменяющийся от 0 до 2 * PI. Луч продолжается до тех пор, пока не достигнет края кадра или черного ящика. Это определяет полигон, который вы заполняете пурпурным (1 отрезок, прямое освещение).

Это легкая часть. Теперь вы можете повторить это для каждого пикселя, лежащего на пурпурно-белой (1-0) границе многоугольника. Это определяет конечный набор вторичных многоугольников; заполните их желтым (код 2).

Повторите этот процесс с желто-белыми (2-0) границами, чтобы идентифицировать 3 пикселей; итерируйте, пока у вас не закончатся пиксели.

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

...