У обчислювальної геометрії відома задача про визначення приналежності точки багатокутника. На площині дано багатокутник і крапка. Потрібно вирішити питання про приналежність точки багатокутника.
Багатокутник може бути як опуклим. так і неопуклого. Зазвичай передбачається, що багатокутник простий, тобто без самоперетинів, але завдання розглядають і для не-простих багатокутників. В останньому випадку різні способи визначення приналежності точки багатокутника можуть привести до різних результатів. Розрізняють алгоритми без попередньої обробки і алгоритми з попередньою обробкою, в ході якої створюються деякі структури даних, що дозволяють в подальшому швидше відповідати на безліч запитів про приналежність точок одній і тій же многоугольнику.
Метод трасування променя [ред | правити вікі-текст]
Облік кількості перетинів [ред | правити вікі-текст]
Методи працюють по-різному для багатокутників з самопересекающиеся кордоном. Зліва: even-odd rule. Справа: nonzero winding rule.
Один зі стандартних методів визначення приналежності точки безпідставного простому многоугольнику полягає в наступному. Випустимо промінь з даної точки в довільному напрямку (наприклад в позитивному напрямку горизонтальній осі), і порахуємо скільки разів промінь перетинає ребра багатокутника. Для цього достатньо пройтися в циклі по ребрах багатокутника і визначити, перетинає промінь кожне ребро. Якщо кількість перетинів непарній, то оголошується, що точка лежить всередині багатокутника, якщо парне - то зовні. Це засновано на тому простому спостереженні, що при русі по променю з кожним перетином кордону точка поперемінно виявляється то всередині, то зовні багатокутника. Алгоритм відомий під такими назвами, як crossing number (count) algorithm або even-odd rule.
В алгоритмі виникає утруднення в виродженим випадку, коли промінь перетинає вершину багатокутника. Один із прийомів для його подолання полягає в тому, щоб вважати, що такі вершини багатокутника лежать на нескінченно малу величину вище (або нижче) прямий променя, і стало бути перетину насправді і немає. [1] Таким чином, перетин променя з ребром зараховується, якщо один з кінців ребра лежить строго нижче променя, а інший кінець - вище або лежить на промені.
Алгоритм працює за час O (N) для N -угольніка.
Облік кількості обертів [ред | правити вікі-текст]
Крива робить два оберти навколо даної точки.
Розглянемо число оборотів, яке робить орієнтована межа багатокутника навколо даної точки P. В алгебраїчній топології це число називається індексом точки відносно кривої. [2] Воно може бути обчислено наступним чином. Як і раніше, випустимо промінь з P в довільному напрямку і розглянемо ребра, які він перетинає. Кожному перетину дамо число +1 або -1, в залежності від того, як ребро перетинає промінь - за годинниковою (зліва направо) або проти годинникової стрілки (справа наліво). Ці два випадки можна розрізнити за знаком скалярного твори між напрямних вектором ребра і нормаллю до направляючої вектору променя. [3] Сума отриманих величин і є індекс точки відносно кривої. Сума буде позитивною або негативною, в залежності від орієнтації кордону. Якщо вона не дорівнює нулю, то будемо вважати, що точка лежить всередині багатокутника, інакше - зовні.
Такий алгоритм відомий під назвою nonzero winding rule. [3]
Для простих багатокутників цей метод працює так само, як і метод, заснований на підрахунку числа перетинів. Різниця між ними проявляється при розгляді багатокутників з самопересекающиеся кордоном.
Метод підсумовування кутів [ред | правити вікі-текст]
Можна визначити, що точка P знаходиться всередині багатокутника c вершинами V0. V1. Vn = V0. обчисливши суму:
# X03D5; i = arccos # X2061; (P V i # X2212; 1 # X22C5; P V i | P V i # X2212; 1 | # X22C5; | P V i | ) S i g n (d e t (P V i # X2212; 1 P V i)). = \ Arccos \ left (\ cdot PV_> | \ cdot | PV_ | >> \ right) sign \ left (detPV _ \\ PV_ \ end> \ right).>Можна довести, що ця сума є не що інше, як winding number точки P щодо кордону багатокутника, з точністю до константного множника 2 # X03C0; . Тому можна вважати, що точка лежить зовні багатокутника, якщо сума дорівнює нулю (або досить близька до нього, якщо використовується наближена арифметика). Однак даний метод досить непрактичний, так як вимагає обчислення дорогих операцій для кожного ребра (зворотних тригонометричних функцій, квадратних коренів), і був навіть названий «найгіршим у світі алгоритмом» для даного завдання. [1]
К. Вейлер був запропонований практичний варіант цього методу, уникає дорогих операцій і наближених обчислень. [4] Було показано, що суму кутів можна обчислити, використовуючи лише операцію класифікації точки багатокутника по квадрантам щодо точки P. Алгоритм Вейлера і деякі поліпшення до нього описуються в [5].
Алгоритми c передобробці [ред | правити вікі-текст]
Опуклі і зоряні багатокутники [ред | правити вікі-текст]
Належність точки опуклого або зоряного N -угольніку може бути визначена за допомогою двійкового пошуку за час O (log N), при витраті O (N) пам'яті та O (N) часу на попередню обробку. [6]
Довільний багатокутник [ред | правити вікі-текст]
Завдання про належність точки безпідставного простому q можна розглядати як окремий випадок задачі про локалізацію точки в планарном подразбіеніі. Для N -угольніка ця задача може бути вирішена за час O (log 2 N) з використанням O (N) пам'яті та O (N log N) часу на попередню обробку. [7]
Примітки [ред | правити вікі-текст]
Література [ред | правити вікі-текст]
- Препарату Ф. Шеймос М. Розділ 2.2: Завдання локалізації точок. // Обчислювальна геометрія: введення. - Москва: Мир, 1989.