Належність точки многокутнику

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Облік кількості перетинів[ред.ред. код]

Стандартний метод визначення належності точки простому многокутнику полягає в наступному. Випускається промінь з цієї точки в довільному напрямку (при реалізації алгоритму зручно вибрати позитивний напрямок горизонтальної вісі Ox), і рахується скільки разів промінь перетинає ребра многокутника. Для цього достатньо пройтися в циклі по ребрах многокутника і визначити, чи перетинає промінь кожне ребро. Якщо кількість перетинів непарна, то оголошується, що точка лежить всередині многокутника, якщо парна — то зовні. Метод засновано на тому простому спостереженні, що при русі по променю з кожним перетином кордону точка поперемінно виявляється то всередині, то зовні многокутника.

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

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

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

Облік кількості обертів[ред.ред. код]

Внутрішні точки мають різні індекси

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

Обчислення індексу відбувається наступним чином. Випускається промінь з заданої точки в довільному напрямку і розглянемо ребра, які він перетинає. Кожному перетинанню приписужться число +1 або −1, залежно від того, як ребро перетинає промінь — за годинниковою або проти годинникової стрілки. Сума отриманих величин і є індексом точки.

Література[ред.ред. код]

  • Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. Раздел 2.2.1: М.: Мир, 1989.