ЯК визначити приналежність

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

Інструкція

Скористайтеся методом трасування променя з урахуванням числа перетинів. У цьому випадку із заданої точки в довільному напрямку випускається промінь, після чого підраховується, скільки разів він перетне ребра багатокутника. Для цього використовується циклічний алгоритм, який перевіряє кожне ребро фігури на перетин. Якщо кількість перетинів є парним, то точка лежить зовні багатокутника, якщо ж непарних - то всередині.

Вирішіть задачу про приналежність методом трасування променя з урахуванням числа обертів, які робить орієнтована межа багатокутника щодо заданої точки. У цьому випадку також випускається з точки промінь в довільному напрямку і розглядаються ребра, з якими він перетнувся. Якщо промінь перетинає ребро за годинниковою стрілкою (зліва направо), то йому присвоюється число «+1», якщо проти годинникової стрілки (справа наліво) - то число «-1». Після цього складається сума отриманих величин. Якщо вона дорівнює нулю, то точка знаходиться зовні багатокутника, а якщо більше або менше нуля - то всередині.

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

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