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

Многокутник видимості показано жовтим кольором. Чотири перешкоди показано синім кольором.

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

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

ВизначенняРедагувати

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

Аналогічно, многокутник видимості сегмента або крайової видимий многокутник — це частина, видима будь-якій точці вздовж

ДодаткиРедагувати

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

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

Алгоритми многокутників точкової видимостіРедагувати

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

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

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

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

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

   Algorithm naive_bad_algorithm( ,  )
         :=  
       for  :
           // shoot a ray with angle  
             :=  
           for each obstacle in  :
                 := min( , distance from   to the obstacle in this direction)
           add vertex   to  
       return  

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

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

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

   Algorithm naive_better_algorithm( ,  )
         :=  
       for each obstacle   in  :
           for each vertex   of  :
               // shoot a ray from   to  
                 := distance from   to  
                 := angle of   with respect to  
               for each obstacle   in  :
                     := min( , distance from   to  )
               add vertex   to  
       return  

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

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

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

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

Тут буде коротко описаний останній алгоритм. Він просто обходить кордон многокутника  , обробляючи вершини в тому порядку, в якому вони з'являються, зберігаючи при цьому стек вершин  , де   — вершина стека. Стек являє собою вершини, видні  , які трапляються досі. Якщо пізніше, під час виконання алгоритму, деякі нові вершини будуть зустрічатися з неясною частиною  , то затемненні вершини з   будуть видалені зі стека. До моменту завершення алгоритму   буде складатися з усіх видимих вершин, тобто, це бажаний многокутник видимості. Ефективна реалізація була опублікована в 2014 році.[9]

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

Для точки в многокутнику з   дірами і   вершинами можна показати, що в гіршому випадку оптимальним алгоритмом є  . Такий алгоритм був запропонований в 1995 році разом з доказом його оптимальності.[10] Проте, він спирається на лінійний алгоритм тріангуляції багатокутника по Chazelle, який є надзвичайно складним.

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

Сегменти, які не перетинаються, за винятком їх кінцевих точокРедагувати

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

Для точки з набору   сегментів, які не перетинаються, за винятком їх кінцевих точок, можна показати, що в гіршому випадку алгоритм   є оптимальним. Це пов'язано з тим, що алгоритм многокутника видимості повинен виводити вершини многокутника видимості в відсортованому порядку, тому проблему сортування можна звести до обчислення многокутника видимості.[11]

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

Розділяй і володарюйРедагувати

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

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

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

Зазвичай пересічні сегментиРедагувати

Для точки, що складається в основному з пересічних сегментів, проблема многокутника видимості зводиться у лінійному часі до проблеми нижньої оболонки. За аргументом Девенпорта-Шинцель[en] нижня оболонка в найгіршому випадку має   кількість вершин, де   — зворотна функція Акермана. Найгірший варіант оптимального алгоритму розділяй і володарюй, який виконується за  , був створений Джоном Хершбергером[en] в 1989 році.[14]

ПосиланняРедагувати

Програмне забезпеченняРедагувати

ПосиланняРедагувати

  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. 
  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. 
  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. 
  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. 
  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. 
  6. Liow, Nicklaus. SIGHT & LIGHT how to create 2D visibility/shadow effects for your game. Процитовано 9 May 2014. 
  7. Patel, Amit (5 July 2012). 2d Visibility Algorithm. Процитовано 9 May 2014. 
  8. а б Patel, Amit (5 July 2012). Blobs in Games: 2d Visibility. Процитовано 9 May 2014. 
  9. а б Bungiu, Francisc; Hemmer, Michael; Hershberger, John; Huang, Kan; Kröller, Alexander (2014). «Efficient Computation of Visibility Polygons». arXiv:1403.3905 [cs.CG]. 
  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. 
  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. 
  12. Arkin, E; Mitchell, Joseph (1987). An optimal visibility algorithm for a simple polygon with star-shaped holes (746). 
  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. 
  14. Hershberger, John (1989). Finding the upper envelope of   line segments in   time. Information Processing Letters 33 (4): 169–174. doi:10.1016/0020-0190(89)90136-1.