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

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

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

Визначення ред.

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

Додатки ред.

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

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

Алгоритми пошуку многокутників видимості точки ред.

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

Наївні алгоритми ред.

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

Уніфікований алгоритм «фізичного» перетворення променів ред.

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

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

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

Алгоритм перетворення для кожної вершини ред.

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

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

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

Оптимальні алгоритми для точки у простому многокутнику ред.

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

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

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

Оптимальні алгоритми для точки в многокутнику з дірками ред.

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

Оптимальні алгоритми для точки між відрізками ред.

Відрізки, які не перетинаються, за винятком їх кінцевих точок ред.

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

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

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

Розділяй і володарюй ред.

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

Кутова розгортка ред.

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

Узагальнення на випадок, коли відрізки перетинаються ред.

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

Примітки ред.

↑ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.
↑ ^а ^б El Gindy, Hossam; Avis, David (1981). A linear algorithm for computing the visibility polygon from a point. Journal of Algorithms. 2 (2): 186—197. doi:10.1016/0196-6774(81)90019-5.
↑ ^а ^б Lee, D. T. (May 1983). Visibility of a simple polygon. Computer Vision, Graphics, and Image Processing. 22 (2): 207—221. doi:10.1016/0734-189X(83)90065-8.
↑ ^а ^б Joe, Barry; Simpson, R. B. (1987). Corrections to Lee's visibility polygon algorithm. BIT Numerical Mathematics. 27 (4): 458—473. doi:10.1007/BF01937271.
↑ Guibas, Leonidas; Motwani, Rajeev; Raghavan, Prabhakar (1992). The robot localization problem in two dimensions. ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics.
↑ Liow, Nicklaus. SIGHT & LIGHT how to create 2D visibility/shadow effects for your game. Архів оригіналу за 12 травня 2014. Процитовано 9 May 2014.
↑ Patel, Amit (5 July 2012). 2d Visibility Algorithm. Архів оригіналу за 14 травня 2014. Процитовано 9 May 2014.
↑ ^а ^б Patel, Amit (5 July 2012). Blobs in Games: 2d Visibility. Архів оригіналу за 12 травня 2014. Процитовано 9 May 2014.
↑ ^а ^б Bungiu, Francisc; Hemmer, Michael; Hershberger, John; Huang, Kan; Kröller, Alexander (2014). «Efficient Computation of Visibility Polygons». arXiv:1403.3905 [cs.CG].
↑ Heffernan, Paul; Mitchell, Joseph (1995). An optimal algorithm for computing visibility in the plane. SIAM Journal on Computing. 24 (1): 184—201. doi:10.1137/S0097539791221505.
↑ ^а ^б Suri, Subhash; O'Rourke, Joseph (1986). Worst-case optimal algorithms for constructing visibility polygons with holes. Symposium on Computational geometry. ACM. с. 14—23. doi:10.1145/10515.10517.
↑ Arkin, E; Mitchell, Joseph (1987). An optimal visibility algorithm for a simple polygon with star-shaped holes (Технічний звіт). № 746.
↑ Asano, Tetsuo (1985). An efficient algorithm for finding the visibility polygon for a polygonal region with holes. Institute of Electronics, Information, and Communication Engineers. Т. 68, № 9. с. 557—559.
↑ Hershberger, John (1989). Finding the upper envelope of $n$ line segments in $O(n\log n)$ time. Information Processing Letters. 33 (4): 169—174. doi:10.1016/0020-0190(89)90136-1.

Посилання ред.

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

Програмне забезпечення ред.

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

[PS-1] Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.

[ea-2] а ^б El Gindy, Hossam; Avis, David (1981). A linear algorithm for computing the visibility polygon from a point. Journal of Algorithms. 2 (2): 186—197. doi:10.1016/0196-6774(81)90019-5.

[lee-3] а ^б Lee, D. T. (May 1983). Visibility of a simple polygon. Computer Vision, Graphics, and Image Processing. 22 (2): 207—221. doi:10.1016/0734-189X(83)90065-8.

[js-4] а ^б Joe, Barry; Simpson, R. B. (1987). Corrections to Lee's visibility polygon algorithm. BIT Numerical Mathematics. 27 (4): 458—473. doi:10.1007/BF01937271.

[guibas-5] Guibas, Leonidas; Motwani, Rajeev; Raghavan, Prabhakar (1992). The robot localization problem in two dimensions. ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics.

[ncase-6] Liow, Nicklaus. SIGHT & LIGHT how to create 2D visibility/shadow effects for your game. Архів оригіналу за 12 травня 2014. Процитовано 9 May 2014.

[redblob-7] Patel, Amit (5 July 2012). 2d Visibility Algorithm. Архів оригіналу за 14 травня 2014. Процитовано 9 May 2014.

[redblob2-8] а ^б Patel, Amit (5 July 2012). Blobs in Games: 2d Visibility. Архів оригіналу за 12 травня 2014. Процитовано 9 May 2014.

[bungiu-9] а ^б Bungiu, Francisc; Hemmer, Michael; Hershberger, John; Huang, Kan; Kröller, Alexander (2014). «Efficient Computation of Visibility Polygons». arXiv:1403.3905 [cs.CG].

[hlogh-10] Heffernan, Paul; Mitchell, Joseph (1995). An optimal algorithm for computing visibility in the plane. SIAM Journal on Computing. 24 (1): 184—201. doi:10.1137/S0097539791221505.

[so-11] а ^б Suri, Subhash; O'Rourke, Joseph (1986). Worst-case optimal algorithms for constructing visibility polygons with holes. Symposium on Computational geometry. ACM. с. 14—23. doi:10.1145/10515.10517.

[am-12] Arkin, E; Mitchell, Joseph (1987). An optimal visibility algorithm for a simple polygon with star-shaped holes (Технічний звіт). № 746.

[asano-13] Asano, Tetsuo (1985). An efficient algorithm for finding the visibility polygon for a polygonal region with holes. Institute of Electronics, Information, and Communication Engineers. Т. 68, № 9. с. 557—559.

[hershberger-14] Hershberger, John (1989). Finding the upper envelope of $n$ line segments in $O(n\log n)$ time. Information Processing Letters. 33 (4): 169—174. doi:10.1016/0020-0190(89)90136-1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]