«Инвертирование» вогнутого многоугольника

Question

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

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

Как вы можете видеть, легче район застроен с кучей треугольников, каждый из которых имеет общую точку в позиции игрока. У каждых двух соседей есть две общие точки.

Однако я готов вычислить границы для внешней части полигона, чтобы заполнить его с черным цветом треугольники «скрываются», что игрок не может видеть.

Один из способов сделать это - «замаскировать» черный прямоугольник текущим многоугольником, но я боюсь, что он очень неэффективен.

Любые идеи об эффективном алгоритме для достижения этого?

Спасибо!

Answer 1

Неаналитическое, грубое решение.

• Cast лучи с постепенным увеличением полярного угла
• записи, когда луч первым попадет объект (и точки, где она попадет)
• Продолжайте идти, пока он больше не попадет в том же объекте (и запись, где он ранее хитов)
• Используя две записанные точки, построить трапецию, которая простирается до бесконечности (или где)

Предостережения:

• не работает слишком хорошо с углублениями - нужно включить все точки между ними, а также. Может понадобиться триангуляция Делоне и т. Д. ... беспорядочно!

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