Користувач:Masich 0/Многокутник видимості

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

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

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

Визначення

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

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

Додатки

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

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

Алгоритми полігонів точкової видимості

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

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

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

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

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

   Algorithm naive_bad_algorithm($p$, $S$)
       $V$ := $\emptyset$
       for $\theta =0,\cdots ,2\pi$:
           // shoot a ray with angle $\theta$
           $r$ := $\infty$
           for each obstacle in $S$:
               $r$ := min($r$, distance from $p$ to the obstacle in this direction)
           add vertex $(\theta ,r)$ to $V$
       return $V$

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

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

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

   Algorithm naive_better_algorithm($p$, $S$)
       $V$ := $\emptyset$
       for each obstacle $b$ in $S$:
           for each vertex $v$ of $b$:
               // shoot a ray from $p$ to $v$
               $r$ := distance from $p$ to $v$
               $\theta$ := angle of $v$ with respect to $p$
               for each obstacle $b'$ in $S$:
                   $r$ := min($r$, distance from $p$ to $b'$)
               add vertex $(\theta ,r)$ to $V$
       return $V$

Тимчасова складність цього алгоритму - ${\displaystyle }$. Це пов'язано з тим, що алгоритм відстрілює промінь для кожної з ${\displaystyle }$ вершин, і щоб перевірити, де закінчується промінь, він повинен перевірити перетин з кожною з ${\displaystyle }$ перешкод. Цього достатньо для багатьох простих додатків, таких як відеоігри, і тому багато навчальних онлайн-посібників вчать цьому методу. Однак, як ми побачимо пізніше, алгоритми${\displaystyle }$ швидкіші.

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

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

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

${\displaystyle }$${\displaystyle }$ де ${\displaystyle }$ ${\displaystyle }$${\displaystyle }$, то затемненні вершини з ${\displaystyle }$${\displaystyle }$ буде складатися з усіх видимих вершин, тобто, це бажаний многокутник видимості. Ефективна реалізація була опублікована в 2014 році.

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

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

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

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

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

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

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

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

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

Кутова розгортка

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

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

${\displaystyle }$кількість вершин, де ${\displaystyle }$${\displaystyle }$

Зовнішні посилання

• http://web.informatik.uni-bonn.de/I/GeomLab/VisPolygon/index.html.en

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

• VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types, calculates visibility polygons in polygonal environments with polygonal holes
• visibility-polygon-js: A public domain Javascript library for computing a visibility polygon for a point among segments using the angular sweep method

Посилання

[[Категорія:Геометричні алгоритми]] [[Категорія:Многокутники]]