Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

У обчислювальної геометрії відома задача про визначення приналежності точки багатокутнику. На площині дано багатокутник і точка. Потрібно вирішити питання про належність точки багатокутнику.

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


1. Метод трасування променя

1.1. Облік числа перетинів

Методи працюють по-різному для багатокутників з самопересекающийся кордоном. Ліворуч: even-odd rule. Справа: nonzero winding rule.

Один із стандартних методів визначення приналежності точки безпідставного простому багатокутнику полягає в наступному. Випустимо промінь з даної точки в довільному напрямку (наприклад в позитивному напрямку горизонтальної осі), і порахуємо скільки разів промінь перетинає ребра багатокутника. Для цього достатньо пройтися в циклі по ребрах багатокутника і визначити, перетинає чи промінь кожне ребро. Якщо число перетинань непарній, то оголошується, що точка лежить усередині багатокутника, якщо парне - то зовні. Це засновано на тому простому спостереженні, що при русі по променю з кожним перетином кордону точка поперемінно виявляється то всередині, то зовні багатокутника. Алгоритм відомий під такими назвами, як crossing number (count) algorithm або even-odd rule .

В алгоритмі виникає утруднення в виродження випадку, коли промінь перетинає вершину багатокутника. Один із прийомів для її подолання полягає в тому, щоб вважати, що такі вершини багатокутника лежать на нескінченно малу величину вище (або нижче) прямий променя, і стало бути перетину насправді і немає. [1] Таким чином, перетин променя з ребром зараховується, якщо один з кінців ребра лежить строго нижче променя, а інший кінець - вище або лежить на промені.

Алгоритм працює за час O (N) для N-кутника.


1.2. Облік числа обертів

Крива робить два оберти навколо даної точки.

Розглянемо число оборотів, яке робить орієнтована кордон багатокутника навколо даної точки P. В алгебраїчній топології це число називається winding number . [2] Воно може бути обчислено наступним чином. Як і раніше, випустимо промінь з P в довільному напрямку і розглянемо ребра, які він перетинає. Кожному перетинанню привласнимо число +1 або -1, в залежності від того, як ребро перетинає промінь - за годинниковою (зліва направо) або проти годинникової стрілки (справа наліво). Ці два випадки можна розрізнити за знаком скалярного твори між направляючим вектором ребра і нормаллю до напрямного вектора променя. [3] Сума отриманих величин і є winding number . Сума буде позитивною або негативною, в залежності від орієнтації кордону. Якщо вона не дорівнює нулю, то будемо вважати, що точка лежить усередині багатокутника, інакше - зовні.

Такий алгоритм відомий під назвою nonzero winding rule . [3]

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


2. Метод підсумовування кутів

Можна визначити, що точка P знаходиться всередині многокутника c вершинами V 0, V 1,..., V n = V 0, обчисливши суму:

\ Sum_ {i = 1} ^ n \ phi_i ,

де φ i - Кут (в радіанах і зі знаком) між променями PV i - 1 і PV i, тобто:

\ Phi_i = \ arccos \ left (\ frac {PV_ {i-1} \ cdot PV_i} {| PV_ {i-1} | \ cdot | PV_i |} \ right).

Можна довести, що ця сума є не що інше, як winding number точки P щодо кордону багатокутника, з точністю до константного множника . Тому можна вважати, що точка лежить зовні багатокутника, якщо сума дорівнює нулю (або досить близька до нього, якщо використовується наближена арифметика). Однак даний метод дуже непрактичний, так як вимагає обчислення дорогих операцій для кожного ребра (зворотних тригонометричних функцій, квадратних коренів, поділу), і був навіть названий "найгіршим у світі алгоритмом" для даної задачі. [1]

К. Вейлер був запропонований практичний варіант цього методу, який уникає дорогих операцій і наближених обчислень. [4] Було показано, що суму кутів можна обчислити, використовуючи лише операцію класифікації точки багатокутника по квадрантам щодо точки P. Алгоритм Вейлера і деякі поліпшення до нього описуються в [5].


3. Алгоритми c передобробки

3.1. Опуклі і зоряні багатокутники

Належність точки опуклому чи зоряному N-кутнику може бути визначена за допомогою двійкового пошуку за час O (log N), при витраті O (N) пам'яті та O (N) часу на попередню обробку. [6]

3.2. Довільний багатокутник

Задачу про належність точки безпідставного простому багатокутнику можна розглядати як окремий випадок задачі про локалізації точки в планарному подразбіеніі. Для N-кутника ця задача може бути вирішена за час O (log 2 N) з використанням O (N) пам'яті та O (N log N) часу на предобработку. [7]

Примітки

  1. 1 2 Eric Haines. Point in Polygon Strategies - erich.realtimerendering.com / ptinpoly /
  2. Може перекладатися на російську мову як "індекс кривої відносно точки", "число кручення", "число намоток", "гвинтове число" і т.п.
  3. 1 2 Foley JD, et al. Computer Graphics: Principles and Practice. Addison-Wesley. 1990. P. 965.
  4. K. Weiler. An incremental angle point in polygon test, in: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16-23.
  5. Kai Hormann and Alexander Agathos. The point in polygon problem for arbitrary polygons - citeseerx.ist.psu.edu / viewdoc / download? doi = 10.1.1.88.5498 & rep = rep1 & type = pdf. Comput. Geom. Theory Appl. 20 (2001), 131-144.
  6. Препарату, Шеймос. Стор. 60-61.
  7. Препарату, Шеймос. Стор. 74. Теорема 2.6.

Література

  • Препарату Ф., Шеймос М. Обчислювальна геометрія. Введення. Розділ 2.2: Завдання локалізації точок. М.: Мир, 1989.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Завдання про 18 точках
Завдання про чотири кубах
Завдання про покриття безлічі
Завдання про переміщення дивана
Завдання про незалежний безлічі
Завдання про упакування в контейнери
Завдання про лицарів і брехун
Точки
I без точки
© Усі права захищені
написати до нас
Рейтинг@Mail.ru