Перевірка приналежності точки багатокутнику

Припустимо, що нам необхідно, для деякої точки Метод трасування променя визначити, чи належить вона багатокутнику, чи лежить поза його межами (відмітимо, що точка належить багатокутнику, коли вона міститься на одній з його сторін або в його середині).

З'ясувати приалежність точки стороні багатокутника доволі просто, скориставшись алгоритмом приналежності точки відрізку: якщо точка Метод трасування променя належить відрізку з координатами metod_trasyvannja_promenja2 та metod_trasyvannja_promenja3, то повинна виконуватись наступна рівність:

metod_trasyvannja_promenja4

Для визначення приналежності точки середині багатокутника скористаємось одним із стандартних методів, а саме: проведемо з даної точки пряму, паралельну осі metod_trasyvannja_promenja6 і підраховуємо, скільки сторін даного багатокутника вона перетинає. Якщо в результаті підрахунку було отримано непарну кількість сторін, то точка metod_trasyvannja_promenja5 міститься в середині багатокутника, якщо парна кількість або нуль — то точка metod_trasyvannja_promenja5 міститься за його межами.

Читати повністю