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

Якщо видимість многокутника обмежена, то це зіркоподібний многокутник. Полігон видимості обмежений, якщо всі промені, які виходять з точки, в кінцевому підсумку закінчуються деякою перешкодою. Таке трапляється, наприклад, якщо перешкоди — це ребра простого многокутника, а p знаходиться всередині многокутника. В останньому випадку многокутник видимості може бути знайдений за лінійний час.^[1][2][3][4]

Формально ми можемо визначити задачу пошуку плаского многокутника видимості наступним чином. Нехай ${\displaystyle S}$ — множина перешкод (відрізків або многокутників) в ${\displaystyle \mathbb {R} ^{2}}$. Нехай ${\displaystyle p}$ — точка в ${\displaystyle \mathbb {R} ^{2}}$, яка не міститься всередині перешкоди. Для точки ${\displaystyle p}$ многокутником видимості ${\displaystyle V}$ буде множина точок в ${\displaystyle \mathbb {R} ^{2}}$, таких, що для будь-якої точки ${\displaystyle q}$ з ${\displaystyle V}$, відрізок ${\displaystyle pq}$ не перетинає жодну перешкоду в ${\displaystyle S}$.

Полігони видимості корисні в робототехніці. Наприклад, коли робот в процесі навігації^[en] використовує такі датчики, як лідар для виявлення відстані до перешкоди, то, по суті, він будує многокутник видимості.^[5]

Многокутники видимості також використовуються у відеоіграх, існує багато онлайн-підручників, які пояснюють прості алгоритми їх реалізації.^[6][7][8]

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

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

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

   алгоритм простий_поганий_алгоритм(${\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]

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

• Visibility in simple polygons. Архів оригіналу за 3 травня 2017. (англ.)

• VisiLibity [Архівовано 18 січня 2018 у Wayback Machine.]: Бібліотека C++ з відкритим вихідним кодом для обчислення многокутника видимості в пласких многокутних середовищах
• visibility-polygon-js [Архівовано 16 лютого 2017 у Wayback Machine.]: Загальнодоступна бібліотека Javascript для обчислення многокутника видимості для точки у випадку перешкод у вигляді відрізків з використанням методу кутового замітання