Методи визначення належності точки багатокутнику
Ну начебто визначились із проблемою, давайте тепер подивимося, які методи рішення існують.
Метод 1. Трасування променів
Почну я з того, що вважається найбільш популярним у світі графіки та ігор: трасування променів. Коротко, алгоритм можна описати так:
- З точки, що тестується, випускаємо промінь або в заздалегідь заданому, або в довільному напрямку.
- Вважаємо кількість перетинів із багатокутником.
- Якщо кількість перетинів парна, ми знаходимося зовні. Якщо кількість перетинів непарна, ми – усередині.
Метод простий, але, на жаль, у загальному випадку його краще не застосовувати. Причиною цього є випадок, коли ми перетинаємо променем вершину багатокутника чи ребро, яке частково збігається з променем. Ілюструю це на прикладі.
Допустимо, у нас є багатокутник, і є точка. На самому початку ми домовилися, що напрямок буде вздовж осі х. Випускаємо з точки промінь у позитивному напрямку осі x і промінь благополучно перетнув багатокутник у вершині. Тут постає питання, як саме ми перевіряємо таку ситуацію? Не забуваємо, що ми працюємо з числами з точкою, що плаває, і невеликі похибки можливі. Перейдемо у світ аналітичної геометрії,щоб можна було оперувати непросто геометричними поняттями, а числами.
Рівняння кожного відрізка (грані багатокутника):a+ t(b-a), деа– координати одного кінця відрізка,b- координати іншого кінця відрізка. Очевидно, що якщо промінь перетинає відрізок, t має бути в інтервалі [0,1]. Якщо ми променем перетинаємо вершину, то t = 0 чи t = 1. Це ідеальному світі математики. У реальному світі комп'ютерної алгебри у вас може вийти щось на зразок t = 1e-10. Або t = -1e-10. Або 0.999999999999998. Або 1.000000000000001. Оскільки перетин двох прямих включає процедуру поділу, таке може запросто вийти. І що ж тоді робити? Довіритися комп'ютеру і вважати, що якщо ми строго більші або рівні нулю або строго менше або рівні одиниці, то вважаємо це за перетин, а інакше не рахуємо? Довірилися та отримали ситуацію, коли з одним ребром параметр t = -1e-20, з іншим ребром t = 1.000000000000000001. В результаті перетинами це не вважаємо, і у нас промінь благополучно проскочив повз і результат виявляється неправильним.
Подивимося в іншому напрямку. Відправили промінь у негативному напрямку. Там теж не дуже добре – промінь перетинає вершину всередині багатокутника. Теж може виявитися будь-що. Замість горизонтального напрямку взяти вертикальне? Ніхто не гарантує, що ви знову не перетнете вершину. У конкретно обраному прикладі мною нагорі точка підібрана таким чином, що перетин її з променем, паралельним осі y і йде зверху вниз теж перетинає багатокутник у вершині.
Причому якщо ви думаєте, що перетин з вершиною – це погано, дивіться, що ще може статися:
Тут ми перетинаємо промінь із відрізком, який із цим променем збігається. Як бути втакому разі? А якщо не збігається, а майже збігається? А уявіть собі, що у багатокутнику безліч майже вироджених ребер, як із таким перетинати?
Найсумніше в цій ситуації те, що нам ось здається: «Мені треба щось дуже просте для моїх простих цілей, мене така ситуація не торкнеться». За законом Мерфі, на жаль, саме така ситуація виникає щоразу, коли її зовсім не чекаєш. І тому я плавно переходжу до другого методу.
Метод 2. Ближня точка та її нормаль
Взагалі цього методу є страшна назва angle weighted pseudo normals і пов'язаний він у поняттям так званих полів відстаней зі знаком (signed distance fields). Але лякати зайвий раз я нікого не хочу, тож нехай буде просто ближня точка та її нормаль (тобто перпендикулярний вектор).
Алгоритм у цьому випадку такий:
- Для точки, що тестується, шукаємо найближчу точку на багатокутнику. При цьому пам'ятаємо, що найближча точка може бути не лише на відрізку, а й у вершині.
- Шукаємо нормаль найближчої точки. Якщо ближня точка лежить на ребрі, то нормаль є вектор, перпендикулярний до ребра і що дивиться назовні багатокутника. Якщо ближня точка – одна з вершин, то нормаллю є усереднений вектор ребер, що належать до вершини.
- Обчислюємо кут між нормаллю найближчої точки та вектором від точки до найближчої. Якщо кут менший за 90 градусів, то ми – всередині, інакше – зовні.
Розглянемо приклад. Точка A1, найближча точка дляїї знаходиться на ребрі. Якщо все робимо правильно, нормаль до ребра паралельна вектору від точки до найближчої. У випадку точки A1, кут між векторами = 0. Або майже нуль, оскільки через операції з плаваючою точкою все можливо. Менше 90 градусів, точка A1, що тестується, – всередині. Протестуємо точку A2. У неї найближча точка – вершина, нормаль якої – усереднена нормаль ребер прилеглих до цієї вершині. Вважаємо скалярне твір двох векторів, має бути негативним. Ми – зовні.
Так, начебто із суттю методу розібралися. Що там з продуктивністю та проблемами, пов'язаною з плаваючою точкою?
Як і у випадку трасування точок, продуктивність – O(log n), якщо використовувати дерева для зберігання інформації про ребрах. З обчислювальної точки зору метод, хоч і має подібну складність, буде дещо повільнішим, ніж трасування. Насамперед тому, що відстань між точкою і ребром трохи дорожча операція, ніж перетин двох ліній. Неприємності, пов'язані з плаваючою точкою, виникають у цьому методі, як правило, недалеко від ребер багатокутника. Причому що ми ближче до ребра, то більша ймовірність неправильного визначення знака. На щастя, що ми ближче до ребра, то менша відстань. Тобто якщо ми, наприклад, говоримо, що якщо отримана відстань менша за заздалегідь задану мінімальну (це може бути константа на кшталт DBL_EPSILON або FLT_EPSILON), то точка належить ребру. А якщо вона належить ребру, то ми вже самі вирішуємо, чи частина багатокутника його ребро чи ні (зазвичай – частина).
Описуючи попередній метод, досить багато сказано про недоліки. Настав час назвати кілька недоліків і цього способу. Насамперед, цей метод вимагає, щоб усі нормалі до ребрів були спрямовані у правильнубік. Тобто до того, як визначати, зовні ми чи всередині, треба провести якусь роботу з обчислення цих нормалей та правильне їхнє орієнтування. Дуже часто, особливо коли на вході велике звалище з вершин і ребер, цей процес не завжди простий. Якщо треба визначити тільки для однієї точки, процес орієнтації нормалей може зайняти більшу частину часу, яку можна було б витратити на щось ще. Також цей метод дуже не любить, коли на вхід подається багатокутник із самоперетинами. На початку я сказав, що в нашому завданні такий випадок не розглядається, але якби він розглядався, цей метод міг видати зовсім неочевидні результати.
Але в цілому метод непоганий, особливо якщо у нас на вході багатокутник з великою кількістю вершин і ребер, а точок на приналежність треба багато протестувати. Якщо точок мало, трасування променів нестабільна, а хочеться чогось більш-менш надійного, тобто і третій спосіб.
Метод 3. Індекс точки щодо багатокутника
Цей метод відомий досить давно, але в основному залишається теоретичним, переважно тому, що він не такий ефективний, як попередні два. Ось його суть «на пальцях». Візьмемо одиничне коло з центром у точці, що тестується. Потім кожну вершину багатокутника спроектуємо на це коло променями, які проходять через вершину і точку, що тестується. Якось приблизно так:
На малюнку точки P1, P2 і так далі – вершини багатокутника, а точки P1', P2' і так далі – їх проекції на коло. Тепер коли ми розглядаємо ребро багатокутника, за проекціями можна визначити, чи відбувається обертання проти годинникової стрілки або годинникової стрілки при переході від однієї вершини до іншої. Обертання проти годинникової стрілки вважатимемо позитивним поворотом, аобертання за годинниковою стрілкою – негативним. Кут, який відповідає кожному ребру – це кут між сегментами кола через проекції вершин цього ребра. Так як поворот у нас може бути позитивний або негативний, то кут може бути позитивний або негативний.
Якщо після цього скласти всі ці кути, то сума повинна бути +360 або -360 градусів для точки, що знаходиться всередині, і 0 для точки зовні. Плюс-мінус тут недарма. Якщо при заданні порядку обходу багатокутник обходиться проти годинникової стрілки, має бути +360. Якщо ж порядок обходу ребер у багатокутнику проти годинникової стрілки, виходить -360. Щоб уникнути числових помилок зазвичай роблять так: ділять суму, що вийшла, на 360 і призводять до найближчого цілого. Число до речі і є тим самим індексом точки. Результат може бути один з трьох: -1 означає, що ми всередині і багатокутник обходимо за годинниковою стрілкою, 0 означає, що ми зовні, +1 означає, що ми зовні. Решта означає, що ми десь помилилися, або що вхідні дані некоректні.
Алгоритм у разі наступний:
- Встановлюємо суму кутів 0.
- Для всіх ребер багатокутника:
- За допомогою скалярного твору обчислюємо кут, утворений векторами, що починається в точці, що тестується і закінчуються в кінцях ребра.
- Обчислюємо векторне твір цих векторів. Якщо його z-компонента позитивна – додаємо кут до суми кутів, інакше – віднімаємо з тієї ж суми.
Розглянемо приклад. Є багатокутник,порядок якого встановлено проти годинникової стрілки. Є точка А, яку ми тестуємо. Для тестування спочатку обчислюємо кут між векторами 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 Крапка – усередині.
(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 градусам, це автоматично означає ребро.
Недоліки методу чимось компенсуються його перевагами. По-перше, це найстабільніший метод. Якщо багатокутник на вхід подано коректний, то результатвиходить коректний для всіх точок, за винятком хіба що точок на ребрах, але про них дивись вище. Понад те, метод дозволяє частково боротися з некоректними вхідними даними. Чи багатокутник самоперетинається? Чи не біда, метод швидше за все визначить більшість точок правильно. Багатокутник не замкнутий чи взагалі не багатокутник, а малоосмислений набір сегментів? Метод визначить точки чітко у велику кількість випадків. Загалом усім метод хороший, але повільний і вимагає обчислень арккосинусов.
Чим хотілося б закінчити цей огляд? А тим, що методів для вирішення проблеми визначення належності крапки багатокутнику існує не один і навіть не два. Вони служать для різних цілей і деякі більш підходять у випадках, коли важлива швидкість, інші – коли важлива якість. Ну і не забуваємо про те, що у нас непередбачувані вхідні дані і ми працюємо з комп'ютером, у якого арифметика з плаваючою точкою схильна до похибок. Якщо потрібна швидкість і якість не має значення – трасування променів на допомогу. У більшості реальних додатків, швидше за все, допоможе метод ближньої точки і нормалі. Якщо ж першому місці – точність визначення при незрозумілих вхідних даних, метод індексу точки має допомогти.
Якщо будуть якісь питання, ставте. Як людина, яка займається геометрією та подібними проблемами пов'язаними з графікою, буду радий допомогти чим зможу.
Ви можете допомогти і перевести небагато коштів на розвиток сайту