Алгоритм визначення попадання крапки в контур на основі комплексного аналізу
.collapse">Зміст
Привіт всім хабра людям. Хочу надати шановним читачам приклад, коли суха і далека від життя у нашому розумінні вища математика дала хороший практичний результат.
Спочатку трохи спогадів
Було це під час перебування мою студентом одного з технічних ВНЗ у 90-ті, курсі напевно другому. Потрапив я якось на олімпіаду з програмування. І ось на цій самій олімпіаді було завдання: задати координати трикутника, тестової точки на площині, і визначити чи належить ця точка області трикутника. Загалом, плева задача, але тоді я її так і не вирішив. Але потім задумався – над загальнішим завданням – належність полігону. Повторюся - була середина 90-х, інтернету не було, книжок з комп'ютерної геометрії не було, а були лекції з вежі та лабораторія 286-х з турбо паскалем. І ось так збіглися зірки, що саме коли я розмірковував над проблемою, на вишці нам читали теорію комплексного змінного. І одна формула (про неї нижче) впала на благодатний ґрунт. Алгоритм був придуманий і реалізований на паскалі (на жаль, мій півтора гіговий гвинт загинув і забрав у небуття цей код і купу інших моїх юнацьких напрацювань). Після інституту я потрапив працювати до одного НДІ. Там мені довелося займатися розробкою ГІС для потреб працівників інституту та власним одним із завдань було визначення попадання об'єктів у контур. Алгоритм було переписано на С++ і добре зарекомендував себе у роботі.
Завдання для алгоритму
Визначити:
чи точка області D, обмеженої полігоном.
Висновок формул для подальшого написання алгоритму в жодному разі не претендує наматематичну повноту і точність, лише демонструє інженерний (споживчий підхід) до Цариці полів наук.
Інтегральна формула Коші
Пояснення з робітничо-селянської інженерної точки зору: — межа Г наш заданий контур, — z0 -тестована точка — f(z) — комплексна функція від комплексного аргументу ніде в контурі не звертається до нескінченність.
Тобто, щоб встановити належність точки контуру, нам необхідно обчислити інтеграл і порівняти його зі значенням функції цієї точки. Якщо вони збігаються, то крапка лежить у контурі. Зауваження: інтегральна теорема коші свідчить, що й точка лежить у контурі, ті підинтегральное вираз ніде не звертається у нескінченність, то інтеграл дорівнює нулю. Це спрощує справу - треба лише обчислити інтеграл і перевірити його на рівність нулю: дорівнює нулю точка не контуру, відмінний - лежить у контурі. Займемося обчисленням інтегралу. За f(z) приймемо просту функцію 1. Не порушуючи спільності, можна за z0 прийняти точку 0 (завжди можна зрушити координати).
Позбавляємося уявної одиниці в знаменнику підінтегральної частини і розщепимо інтеграл на дійсну і уявну частини:
Вийшло два криволінійні інтеграли ІІ роду. Обчислимо перший
Виконаються умова незалежності інтеграла від шляху, отже, перший інтеграл дорівнює нулю і його обчислювати не потрібно.
З уявною частиною такий фокус не минає. Згадуємо, що наша межа складається з відрізків прямих, отримуємо: Де Гi- це відрізок (xi,yi)-(xi+1,y i+1) Обчислимо i-ий інтеграл. Для цього запишемо рівняння i-го відрізка у параметричному вигляді
Підставимо в інтеграл
і після громіздких і нудних перетворень отримаємо наступну принадну формулу:
Остаточноотримуємо
Алгоритм на C++:
T - тип точки, наприклад:structPointD double x, y; >;
Приклад роботи алгоритму написаний із застосуванням на мій погляд великої бібліотеки 2D графіки: Anti-Grain Geometry (AGG).
Управління: клік лівою кнопкою - додавання нової точки контуру правою кнопкою - замикання контуру лівою із затисненим Shift-ом - перенесення тестової точки
Панове, кому цікаво, наводжу швидший алгоритм. Вже не мій. Особливе і величезне спасибі forgotten за статейку. template bool pt_in_polygon2(const T &test,const std::vector &polygon)
static const int q_patt[2][2]= < , >;