Многокутник видимості

Наївні алгоритми легко зрозуміти і реалізувати, але вони не оптимальні, бо зазвичай є набагато повільнішіми за інші алгоритми.

У реальному житті точка, що світиться, освітлює видиму їй область, оскільки випромінює світло в усіх напрямках. Це можна змоделювати, стріляючи променями в багатьох напрямках. Припустимо, що є точка і множина перешкод. Тоді алгоритм буде виражений наступним псевдокодом:

   алгоритм простий_поганий_алгоритм(${\displaystyle p}$, ${\displaystyle S}$)
       ${\displaystyle V}$ := ${\displaystyle \emptyset }$
       для ${\displaystyle \theta =0,\cdots ,2\pi }$:
           //вистрілити промінь з кутом ${\displaystyle \theta }$
           ${\displaystyle r}$ := ${\displaystyle \infty }$
           для кожної перешкоди у ${\displaystyle S}$:
               ${\displaystyle r}$ := min(${\displaystyle r}$, відстань від ${\displaystyle p}$ до перешкоди в цьому напрямку)
           додати вершину ${\displaystyle (\theta ,r)}$ у ${\displaystyle V}$
       повернути ${\displaystyle V}$

Тепер, якби можна було спробувати всю неперервну множину кутів, результат був би правильним. На жаль, неможливо дійсно спробувати кожен напрямок через обмеження на обчислювальну потужність. Наближення можна створити, кинувши багато, скажімо, 50 променів, розташованих рівномірно один від одного. Однак це не точне рішення, бо малі перешкоди можуть бути пропущені між двома сусідніми променями. Крім того, він дуже повільний, тому що для отримання приблизно такого ж рішення може знадобитися багато променів, і многокутник вихідної видимості може мати в собі набагато більше вершин, ніж потрібно.

Описаний раніше алгоритм можна значно покращити як за швидкістю, так і за точністю, зробивши спостереження, що достатньо стріляти променями лише у вершини кожної перешкоди. Це пов'язано з тим, що будь-які вигини або кути уздовж межі многокутника видимості обумовлені деякою вершиною на перешкоді.

   алгоритм простий_покращенний_алгоритм(${\displaystyle p}$, ${\displaystyle S}$)
       ${\displaystyle V}$ := ${\displaystyle \emptyset }$
       для кожної перешкоди ${\displaystyle b}$ у ${\displaystyle S}$:
           для кожної вершини ${\displaystyle v}$ з ${\displaystyle b}$:
               //вистрілити промінь з ${\displaystyle p}$ у ${\displaystyle v}$
               ${\displaystyle r}$ := відстань від ${\displaystyle p}$ до ${\displaystyle v}$
               ${\displaystyle \theta }$ := кут ${\displaystyle v}$ відносно ${\displaystyle p}$
               для кожної перешкоди ${\displaystyle b'}$ у ${\displaystyle S}$:
                   ${\displaystyle r}$ := min(${\displaystyle r}$, відстань від ${\displaystyle p}$ до ${\displaystyle b'}$)
               додати вершину ${\displaystyle (\theta ,r)}$ у ${\displaystyle V}$
       повернути ${\displaystyle V}$

Часова складність цього алгоритму — ${\displaystyle O(n^{2})}$. Це пов'язано з тим, що алгоритм відстрілює промінь для кожної з ${\displaystyle n}$ вершин, і щоб перевірити, де закінчується промінь, він повинен перевірити перетин з кожною з ${\displaystyle O(n)}$ перешкод. Цього достатньо для багатьох простих додатків, таких як відеоігри, і тому багато навчальних онлайн-посібників вчать цьому методу[8]. Однак, як ми побачимо пізніше, існують швидші ${\displaystyle O(n\log n)}$ алгоритми (або навіть ще швидші, якщо перешкодою є простий многокутник або якщо є фіксована кількість полігональних отворів).

Полігон видимості для точки у центрі (показана білим), всередині простого многокутника, обведеного чорним кольором.

Для простого многокутника ${\displaystyle {\mathcal {P}}}$ і точки ${\displaystyle p}$, алгоритм лінійного часу є оптимальним для обчислення області в ${\displaystyle {\mathcal {P}}}$, яку видно з ${\displaystyle p}$. Такий алгоритм був вперше запропонований в 1981 році[2]. Однак він досить складний. У 1983 році був запропонований концептуально простіший алгоритм[3], який мав незначну помилку, виправлену в 1987 році.[4]

Тут буде коротко описаний останній алгоритм. Він просто обходить границю многокутника ${\displaystyle {\mathcal {P}}}$, обробляючи вершини в тому порядку, в якому вони з'являються, зберігаючи при цьому стек вершин ${\displaystyle {\mathcal {S}}=s_{0},s_{1},\cdots ,s_{t}}$, де ${\displaystyle s_{t}}$ — верхівка стека. У стеці зберігаються вершини, видимі з ${\displaystyle p}$, які зустрілися на поточний момент часу. Якщо згодом, під час виконання алгоритму, для деяких вершин з'ясується, що вони розташовані у затемненій частині ${\displaystyle {\mathcal {S}}}$, то такі затемненні вершини в ${\displaystyle {\mathcal {S}}}$ будуть видалені зі стека. На момент завершення алгоритму ${\displaystyle {\mathcal {S}}}$ буде складатися з усіх видимих вершин, тобто, це шуканий многокутник видимості. Ефективна реалізація була опублікована в 2014 році.[9]

Для точки в многокутнику з ${\displaystyle h}$ отворами й ${\displaystyle n}$ вершинами можна показати, що оптимальним алгоритмом у найгіршому випадку є ${\displaystyle \Theta (n+h\log h)}$. Такий алгоритм був запропонований в 1995 році разом з доведенням його оптимальності.[10] Проте, він спирається на лінійний алгоритм тріангуляції многокутника Чазеля, який є надзвичайно складним.

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

У випадку коли перешкоди задані множиною з ${\displaystyle n}$ відрізків, які не перетинаються, за винятком їх кінцевих точок, можна показати, що в найгіршому випадку алгоритм ${\displaystyle \Theta (n\log n)}$ є оптимальним. Це пов'язано з тим, що алгоритм многокутника видимості повинен виводити вершини многокутника видимості в відсортованому порядку, тому проблему сортування можна звести до обчислення многокутника видимості.[11]

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

Алгоритм «розділяй і володарюй» для обчислення многокутника видимості був запропонований в 1987 році.[12]

У 1985[13] і 1986 рр.[11] було запропоновано метод кутового замітання, тобто обертове замітання площини для обчислення видимого многокутника. Ідея полягає в тому, щоб спочатку впорядкувати всі кінці відрізів за полярним кутом, а потім виконати ітерацію за ними у порядку зміни кутів. Під час ітерації рядок подій підтримується у вигляді купи. Ефективна реалізація була опублікована в 2014 році.[9]

Задача пошуку многокутника видимості у випадку, коли відрізки перетинаються, зводиться за лінійний час до задачі пошуку нижньої обгортки. За аргументом Девенпорта-Шинцель нижня обгортка, в найгіршому випадку, має ${\displaystyle \Theta (n\alpha (n))}$ кількість вершин, де ${\displaystyle \alpha (n)}$ — обернена функція Акермана. Оптимальний алгоритм «розділяй і володарюй», працюючий у найгіршому випадку, який виконується за ${\displaystyle \Theta (n\log n)}$, був створений Джоном Хершбергером у 1989 році.[14]

• VisiLibity: Бібліотека C++ з відкритим вихідним кодом для обчислення многокутника видимості в пласких многокутних середовищах
• visibility-polygon-js: Загальнодоступна бібліотека Javascript для обчислення многокутника видимості для точки у випадку перешкод у вигляді відрізків з використанням методу кутового замітання