Тріангуляційна сітка та автоматизація її побудови

1. Математична модель.

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

2. Тріангуляційна сітка.

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

Відсутність єдиного, довільно вибраного масштабу всім даних - розмір осередки сітки автоматично встановлює межа подробиці карти. Тріангуляція опорних точок природним чином підлаштовується під дані. Там де опорні точкирозріджені, трикутники більші, там, де є згущення, - дрібніші. Число трикутників визначається за формулою Ейлера і не перевищує подвоєного числа опорних точок. У правильності цього твердження можна переконатись, якщо спрямувати довжину внутрішнього ребра до нуля. У підсумку ми отримаємо на одне ребро та дві вершини менше.
У прямокутної сітки є два виділені напрями, не узгоджені з початковими даними. Маючи в якості реальної поверхні гірський хребет, який тягнеться навскіс або звивисте русло річки, ми будемо змушені сильно подрібнити сітку, що потребує значних обчислювальних потужностей і приведе до утворення нестійкостей. Використання тріангуляційної сітки дозволить побудувати апроксимуючу поверхню по кількох трикутниках - достатньо позначити гребінь і підніжжя (дно і береги).

Основним недоліком тріангуляційної сітки є складність програмування. Вже сам процес побудови тріангуляційної сітки є нетривіальним завданням.

Одне з варіантів її побудови пов'язані з розбиттям площини області Вороного, введені Г.Ф. Вороним 1908 року. Сенсом цього розбиття є розмежування площини області, що з точок, об'єднаних загальної найближчої опорної точкою.

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

Отримані грати маєнаступними властивостями:

її ребра - це відрізки серединних перпендикулярів. Тому, якщо деяка вершина Про Vb область отримана перетином серединних перпендикулярів до відрізків AB і BC, то вона рівновіддалена від A і від B, від B і C, тобто точка О - це центр описаного кола трикутника ABC і серединний перпендикуляр до AC теж проходить через О. Оскільки Оскільки належить Vb , то немає опорних точок, розташованих до Про ближче, ніж, але ОА=ОВ=ОС, тому O належить Va і O належить Vc

Крім того області Вороного утворюють грати, у кожній вершині якої, загалом, сходяться три ребра і три області.

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

Вона має й інші еквівалентні визначення. Один із них характеризує властивість тріангуляції Делоне давати локально найбільш правильні трикутники. Звучить воно так: тріангуляція буде тріангуляцією Делоне тоді і тільки тоді, коли в будь-якій парі трикутників із загальним ребром, в якій це ребро можна перекинути, не порушуючи планарність тріангуляції, від такої перекидання мінімальний з шести кутів у парі трикутників не збільшиться (таке перекидання, до речі, носить спеціальну назву – фліп). Іншими словами, від будь-якої локальної перебудови тріангуляції Делоне трикутники стають неправильнішими. Доказ цього факту випливає з іншого визначення тріангуляції Делон, так званого кругового критерію.

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

Доказ еквівалентності цих трьох визначень:

розглянемо тріангуляцію, що задовольняє круговому критерію, і візьмемо в ній довільну пару трикутників із загальним ребром, що допускає фліп. Нехай це будуть трикутники ABC та BCD. Якщо мінімальний кут BAC або BDC, то, очевидно, що він не збільшиться при фліпі. Якщо мінімальний кут належить до загальної сторони, то нехай це буде, наприклад, кут ABC. Опишемо біля трикутника ABC коло. За круговим критерієм точка D має бути поза нею. Нехай ребро AD перетинає коло в точці E. Тоді кути ABC і AEC рівні, оскільки спираються на ту саму дугу, а кут ADC, очевидно, менше AEC, тобто у разі при фліпі мінімальний кут не збільшиться. У зворотний бік доказ проводиться аналогічно. Доказ еквівалентності кругового критерію визначенню через області Вороного проводиться від зворотного: нехай тріангуляція Делоне, побудована вище не задовольняє критерію і всередину кола з центром О, описаної навколо трикутника АВС, потрапила вершина D. Як уже було показано, точка О - загальна вершина Vb, Va і Vc. Але раз точка D всередині кола, вона знаходиться ближче до точки О, ніж А, В і С. Поетом Про належить Vb, O належить Va, O належить Vc та їх перетину. Доказ у зворотний бік аналогічний.

3. Інкрементний алгоритм.

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

Ще однією перевагою цього алгоритму є простота видалення раніше внесених та оброблених точок. Простота ця обумовлена такою властивістю тріангуляції, як незалежність її всередині та поза багатокутником. Доводиться ця властивість на підставі симетрії кругового критерію: якщо D лежить поза колом, описаним навколо BCD, то A лежить поза колом, описаним навколо BCD. Це означає, що перебудова тріангуляції після видалення з неї точки зводиться до тріангуляції її сусідів. В алгоритмі це завдання вирішується створенням локального набору точок, сусідніх до віддаленої, побудовою тріангуляційної сітки на цих точках та додаванням створених трикутників у глобальну базу.

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

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

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

У разі потрапляння нової точки до трикутника, раніше побудованої тріангуляції, відбувається ліквідація цього трикутника та поява трьох нових (на базі чотирьох точок – нової та трьох вершин ліквідованого трикутника). Трикутники, що з'явилися, досліджуються на можливість побудови фліпів. Перетворені після фліпів трикутники додаються до розряду досліджуваних.

4. Перспективи розвитку.

Якщо говорити про перспективи розвитку даного алгоритму, то в мої подальші плани по роботі в даній галузі входить оптимізація структури уявлення використовуваних даних в ЕОМ з метою мінімізації часу роботи алгоритму, реалізація вищенаведеного алгоритму конкретною мовою програмування (робота в цьому напрямі вже ведеться. В якості базового обрано середовище програмування -DELPHI), а також безпосереднє рішення, що наводилася на самому початку завдання побудови гладкої функції, що проходить через опорні точки.