Методи визначення приналежності точки многоугольнику

Нещодавно на хабре була стаття, в якій описувалося як можна визначити, де знаходиться точка по відношенню до многоугольнику: всередині або зовні. Подібна проблема зустрічається в геометричному моделюванні і в комп'ютерній графіці досить часто. А так як метод, описаний у статті, був трохи не оптимальний, а в коментарях був невеликий хаос, виникла думка написати цю статтю. Отже, які існують алгоритми сучасної комп'ютерної графіки, щоб визначити, чи належить задана точка многоугольнику чи ні.

Перш, ніж почати, хочу відразу описати проблему. Хоча сама проблема проста: у нас заданий набір точок та встановлено порядок, в якому ці точки з'єднуються. Та задана точка, яку ми тестуємо на приналежність. Мається на увазі, що у нас замкнутий багатокутник, і в загальному випадку ребра багатокутника не перетинаються один з одним, тобто він позбавлений він самоперетинів. Обмежень на кількість вершин немає, тобто легко може бути заданий багатокутник з мільйоном вершин. Ми сподіваємося, що користувач задасть нам незрозуміло що, але і гарантувати це теж не можемо. І ще один нюанс: так як ми працюємо з комп'ютерною графікою, що означає, що ми використовуємо арифметику з плаваючою точкою, яка хоча і дозволяє оперувати з числами досить точно, все одно не позбавлена помилок.

Ну начебто визначилися з проблемою, давайте тепер подивимося, які методи рішення існують.

Метод 1. Трасування променів

Почну я з того, який вважається найбільш популярним в світі графіки та ігор: трасування променів. Коротенько, алгоритм можна описати наступним чином:

  1. З досліджуваної точки випускаємо промінь або в наперед заданому, або в довільному напрямку.
  2. Вважаємо кількість перетинів з гратки.
  3. Якщо кількість перетинів парне, ми знаходимося зовні. Якщо кількість перетинів непарне, ми – всередині.
Звучить просто, чи не правда? І правда, це найпростіший метод. Він у підсумку зводиться до деякого кількості перетинів відрізка (межі багатокутника) і променя, тобто по суті перетину двох прямих і тестування отриманої точки на приналежність променю і відрізку. У найпростішому випадку доведеться перетнути промінь зі всіма відрізками, при використанні дерев (квадратичних, бінарних або BVH), можна скоротити цю кількість. В цілому кажуть, що алгоритмічна складність цього алгоритму O(log n), де n – кількість ребер у многокутнику.

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

image

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

Рівняння кожного відрізка (межі багатокутника): a + t(ba), де а – координати одного кінця відрізка, b – координати іншого кінця відрізка. Очевидно, що якщо промінь перетинає відрізок, t повинно бути в інтервалі [0,1]. Якщо ми променем перетинаємо вершину, то t = 0 або t = 1. Це в ідеальному світі математики. В реальному світі комп'ютерної алгебри у вас може вийти щось на зразок t = 1e-10. Або t = -1e-10. Або 0.99999999999998. Або 1.000000000000001. Оскільки перетин двох прямих включає в себе процедуру поділу, таке може запросто вийти. І що ж у такому випадку робити? Довіритися комп'ютера і вважати, що якщо ми строго більше або дорівнюють нулю, або строго менше або дорівнюють одиниці, то вважаємо це за перетин, а інакше не вважаємо? Довірилися і отримали ситуацію, коли з одним ребром параметр t = -1e-20, з іншим ребром t = 1.000000000000000001. В результаті перетинами це не вважаємо, і у нас промінь проскочив повз і результат виявляється неправильним.

Подивимося в іншому напрямку. Відправили промінь в негативному напрямку. Там теж не дуже добре – промінь перетинає вершину всередині многокутника. Теж може виявитися що завгодно. Замість горизонтального напряму взяти вертикальне? Ніхто не гарантує, що ви знову не перетнете вершину. В конкретно вибраному мною прикладі нагорі точка підібрана таким чином, що його перетину з променем, паралельним осі y і йде зверху вниз теж перетинає багатокутник у вершині.

Причому якщо ви думаєте, що перетин з вершиною – це погано, дивіться що ще може статися:

image

Тут ми перетинаємо промінь з відрізком, який з цим променем збігається. Як бути в такому випадку? А якщо не збігається, а майже збігається? А уявіть собі, що в многокутнику безліч майже вироджених ребер, як з таким перетинати?

Найсумніше у цій ситуації те, що нам ось здається: «мені треба щось дуже просте для моїх простих цілей, мене така ситуація не торкнеться». За законом Мерфі, на жаль, саме така ситуація виникає всякий раз, коли її зовсім не чекаєш. І тому я плавно переходжу до другого методу.

Метод 2. Ближня точка та її нормаль

Взагалі у цього методу є страшну назву angle weighted pseudo normals і пов'язаний він поняттям так званих полів відстаней зі знаком (signed distance fields). Але лякати зайвий раз я нікого не хочу, так що нехай буде просто ближня точка та її нормаль (тобто вектор перпендикулярний).

Алгоритм у даному випадку такий:

  1. Для досліджуваної точки шукаємо найближчу точку на багатокутнику. При цьому пам'ятаємо, що найближча точка може бути не тільки на відрізку, але і у вершині.
  2. Шукаємо нормаль найближчої точки. Якщо ближня точка лежить на ребрі, то нормаль є вектор, перпендикулярний ребру і дивиться назовні багатокутника. Якщо ближня точка – одна з вершин, то нормаллю є усереднений вектор ребер, прилеглих до вершини.
  3. Обчислюємо кут між нормаллю найближчої точки і вектором від досліджуваної точки до найближчої. Якщо кут менше 90 градусів, то ми – всередині, інакше – зовні.
Причому кут як такої вважати не обов'язково, достатньо перевірити знак косинуса цього кута. Якщо позитивний – всередині, якщо негативний – зовні. А оскільки нас цікавить тільки знак косинуса, то по суті ми обчислюємо знак скалярного добутку між двома векторами.

image

Розглянемо приклад. Точка A1, найближча точка для неї знаходиться на ребрі. Якщо все робимо правильно, нормаль до ребра паралельна вектору від досліджуваної точки до найближчої. У випадку точки A1, кут між векторами = 0. Або майже нуль, так як з-за операцій з плаваючою точкою все можливо. Менше 90 градусів, досліджувана точка A1 – всередині. Протестуємо точку A2. У неї найближча точка – вершина, нормаль до якої – усереднена нормаль ребер прилеглих до цієї вершини. Вважаємо скалярний добуток двох векторів, має бути від'ємним. Ми – зовні.

Так, начебто з суттю методу розібралися. Що там з продуктивністю і проблемами, пов'язаної з плаваючою точкою?

Як і у випадку трасування точок, продуктивність – O(log n), якщо використовувати дерева для зберігання інформації про ребрах. З обчислювальної точки зору метод, хоча і має подібну складність, буде дещо повільніше, ніж трасування. Насамперед тому, що відстань між точкою і ребром трохи більше дорога операція, ніж перетин двох ліній. Неприємності, пов'язані з плаваючою точкою, що виникають у цьому методі, як правило недалеко від ребер багатокутника. Причому чим ми ближче до ребра, тим більше ймовірність неправильного визначення знака. До щастя, що ми ближче до ребра, тим менше відстань. Тобто якщо ми, наприклад, говоримо, що якщо отримане відстань менше наперед заданого мінімального (це може бути константа начебто DBL_EPSILON або FLT_EPSILON), то точка належить ребру. А якщо вона належить ребру, то ми вже самі вирішуємо, частина чи багатокутника його ребро чи ні (як правило – частина).

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

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

Метод 3. Індекс точки відносно багатокутника

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

image

На малюнку точки P1, P2 і так далі – вершини багатокутника, а точки P1', P2' і так далі – їх проекції на коло. Тепер коли ми розглядаємо ребро многокутника, за проекціями можна визначити, чи відбувається обертання проти годинникової стрілки або за годинниковою стрілкою при переході від однієї вершини до іншої. Обертання проти годинникової стрілки будемо вважати позитивним поворотом, а обертання за годинниковою стрілкою – негативним. Кут, який відповідає кожному ребру – це кут між сегментами кола через проекції вершин цього ребра. Так як поворот у нас може бути позитивний або негативний, то і кут може бути позитивний або негативний.

Якщо після цього скласти всі ці кути, то сума повинна бути +360 або -360 градусів для точки, що знаходиться всередині і 0 для точки зовні. Плюс-мінус тут неспроста. Якщо при завданні порядку обходу багатокутник обходиться проти годинникової стрілки, повинно вийти +360. Якщо ж порядок обходу ребер у багатокутнику проти годинникової стрілки, то виходить -360. Щоб уникнути числових помилок як правило роблять так: ділять отриману суму на 360 і призводять до найближчого цілого. Число, що вийшло, до речі і є тим самим індексом точки. Результат може бути один із трьох: -1 означає що ми всередині і багатокутник обходимо за годинниковою стрілкою, 0 означає що ми зовні, +1 означає що ми зовні. Все інше означає що ми десь помилилися, або що вхідні дані коректні.

Алгоритм у цьому випадку наступний:

  1. Встановлюємо суму кутів 0.
  2. Для всіх ребер багатокутника:

    1. За допомогою скалярного добутку обчислюємо кут, утворений векторами починається в досліджуваній точці і закінчуються в кінцями ребра.
    2. Обчислюємо векторний добуток цих векторів. Якщо його z-компонента позитивна – додаємо кут до суми кутів, а інакше – віднімаємо від тієї ж суми.

    Ділимо суму на 2 якщо вважаємо в радіанах або на 360 якщо вважаємо в градусах. Останнє малоймовірно, але раптом.
    Результат округляємо до найближчого цілого. +1 або -1 означає, що ми зовні. 0 значить ми всередині.
  3. Розглянемо приклад. Є багатокутник, порядок якої встановлено проти годинникової стрілки. Є точка А, яку ми тестуємо. Для тестування спочатку обчислюємо кут між векторами AP1 і AP2. Векторний добуток цих векторів дивиться на нас, значить додаємо до суми. Переходимо далі і вважаємо кут між AP2 і AP3. Векторний добуток дивиться на нас, отриманий кут віднімаємо. І так далі. Для конкретно цього малюнка " я все порахував і ось що вийшло:Точка А.(AP1, AP2)=74.13, (AP2, AP3)=51.58, (AP3, AP4)=89.99, (AP4, AP5)=126.47, (AP5, AP1)=120.99. sum=74.13-51.58+89.99+126.47+120.99=360. 360/360=1 Точка – всередині.Точка B.(BP1, BP2)=44.78, (BP2, BP3)=89.11, (BP3, BP4)=130.93, (BP4, BP5)=52.97, (BP5, BP1)=33.63. sum=-44.78+89.11-130.93+52.97+33.63=0. Точка – зовні.І традиційно опишемо плюси і мінуси даного підходу. Почнемо з мінусів. Метод простий математично, але не так-то ефективний з точки зору продуктивності. По-перше, його алгоритмічна складність O(n) і, як не крути, а всі ребра багатокутника доведеться перебрати. По-друге, для обчислення кута доведеться скористатися операцією арккосинуса і двома операціями взяття кореня (формула скалярного добутку і зв'язок його з кутом в допомогу тим, хто не розуміє, чому). Ці операції дуже недешеві з точки зору швидкості, і, до того ж, похибки пов'язані з ними можуть бути суттєвими. І в третіх, алгоритм безпосередньо не визначає точку, яка лежить на ребрі. Або – зовні або всередині. Третього не дано. Втім, останній недолік легко визначається: якщо хоча б один з кутів дорівнює або майже дорівнює) 180 градусам, це автоматично означає ребро.Недоліки методу в чомусь компенсуються його достоїнствами. По-перше, це найбільш стабільний метод. Якщо багатокутник на вхід подано коректний, то результат виходить коректний для всіх точок, за винятком хіба що точок на ребрах, але про них дивися вище. Більш того, метод дозволяє частково боротися з некоректними вхідними даними. Багатокутник самопересекается? Не біда, метод швидше за все визначить більшість точок правильно. Багатокутник не замкнутий або взагалі не багатокутник а малоосмысленный набір сегментів? Метод визначить точки вірно у великій кількості випадків. Загалом, всім метод хороший, але повільний і вимагає обчислень арккосинусов. Що б хотілося закінчити цей огляд? А тим, що методів для вирішення проблеми визначення приналежності точки многоугольнику існує не один і навіть не два. Вони служать для різних цілей і деякі більш підходять у випадках, коли важлива швидкість, інші – коли важлива якість. Ну і не забуваємо про те, що у нас непередбачувані вхідні дані і ми працюємо з комп'ютером, у якого арифметика із плаваючою точкою схильна погрішностей. Якщо потрібна швидкість і якість абсолютно неважливо – трасування променів в допомогу. У більшості реальних додатків швидше за все допоможе метод ближньої точки і нормалі. Якщо ж на першому місці – точність визначення при незрозумілих вхідних даних, метод індексу точки повинен допомогти.Якщо будуть якісь питання, задавайте. Як людина, що займається геометрією і подібними проблемами пов'язаними з графікою, буду радий допомогти чим зможу.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.