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

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

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

Облік кількості перетинів

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

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

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

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

Підрахунок кількості обертів

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

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

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

Література

• Препарата, Франко; Шеймос, Майкл (1985), Computational Geometry – An Introduction, Springer-Verlag, ISBN 0-387-96131-3, 1ша редакція: ISBN 0-387-96131-3; 2ге видання, виправлене і довнене (Розділ 2.2.1)