Модифікація алгоритму дискретної апроксимації плоских множин точок

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Модифікація алгоритму дискретної апроксимації плоских множин точок

Пугачов Є.В., д.т.н., професор, Черняк В.І., здобувач (Національний університет водного господарства та природокористування, м. Рівне)

Стаття присвячена модифікації алгоритму дискретної апроксимації плоских множин точок і висвітленню основних проблем, які виникли при його реалізації в середовищі MATLAB, а також - методів їх усунення.

The article is devoted to updating of the algorithm of discrete approximation of flat sets of points and illumination of the basic problems that have arisen at its realization in MATLAB environment, and also - methods of their elimination.

У літературі стосовно методів апроксимації плоских множин точок [1-4], як правило, вважається, що апроксимувальна лінія є простою дугою. Проте структура точкової множини може бути і більш складною, наприклад, мати всередині порожнини або розгалуження. В такому випадку апроксимувальна лінія повинна мати відповідну топологію.

В докторській дисертації Є. В. Пугачова [5] в теоретичному плані розроблено метод дискретної апроксимації плоских множин точок на основі класифікації підмножин точок і елементів, що складають апроксимувальну лінію. При реалізації наведеного в [5] алгоритму в середовищі MATLAB виникли деякі труднощі, що призвело до його модифікації.

Метою даної роботи є висвітлення цих труднощів і розроблення способів їх усунення.

Рис. 1. Початкова множина точок

дискретний апроксимація точковий множина

Нехай задано неупорядковану множину точок (рис.1).

Апроксимація плоскої множини точок здійснюється за таким алгоритмом.

1. Побудова опуклої оболонки і упорядкування точкової множини (рис.2). Для цього необхідно побудувати тріангуляцію Делоне для даної множини точок. В роботі [5] для цього спочатку будується діаграма Вороного, в результаті чого визначаються суміжні точки, сполучивши які отримаємо граф, геометрично двоїстий діаграмі Вороного, в загальному випадку - тріангуляцію Делоне. В даній роботі використовується оператор системи MATLAB delaunay, який виконує тріангуляцію Делоне. Упорядкована точкова множина розглядається з позицій теорії графів [6,7] як планарний геометричний граф, а з позицій комбінаторної топології - як двовимірний симпліціальний вимірно-неоднорідний комплекс [8]. Тому надалі при необхідності використовується термінологія обох розділів математики, наприклад, вершині (точці), ребру і трикутнику в графах відповідають в симпліціальному комплексі нульвимірний (Т0), одновимірний (Т1) і двовимірний (Т2) симплекси.

Рис. 2. Упорядкована на основі тріангуляції Делоне початкова множина точок

2. Визначення ваги р (в [6] - степінь, валентність) кожної точки множини. Вага вершини н графа - це число ребер графа, інцидентних н. Наприклад, вага точок 1, 39 і 41 буде відповідно дорівнювати р1=6, р39=5, р41=5.

3. Визначення такого числа найближчих за відстанню вершин для кожної точки множини, яке відповідає вазі точки. Наприклад, для точки 1 це буде шість вершин: 42, 43, 2, 41, 44, 73; а для точки 39 це буде п'ять вершин: 40, 38, 62, 67, 41.

4. Визначення зовнішніх і внутрішніх контурів (форми) плоскої множини точок. Для побудови зовнішніх і внутрішніх контурів точкової множини розглянемо спосіб відкидання неістотних в'язей [10] на конкретному прикладі: перевіряємо в'язь 1-39 (рис.2). В'язь 39-1 є неістотною для точки 39, оскільки точка 1 не входить до числа найближчих вершин точки 39. Аналогічно, в'язь 1-39 є неістотною для точки 1. Якщо ребро є неістотним для обох інцидентних йому вершин, то воно відкидається, і вага цих вершин зменшується на одиницю. Відповідно зменшується на одиницю і число найближчих за відстанню точок для цих вершин при наступних перевірках.

В роботі [10] розроблено алгоритм визначення порядку перевірки в'язей на неістотність, згідно якого спочатку визначається зовнішній контур точкової множини, а потім внутрішній. В зв'язку з складністю реалізації даного алгоритму в середовищі MATLAB автори використали інший: перевіряються в'язі, інцидентні даній вершині, до тих пір, поки за останній цикл перевірки не буде виявлено жодної неістотної в'язі. Така перевірка проводиться для всіх вершин множини, в результаті чого визначається зовнішній і внутрішній контури множини точок одночасно (рис.3).

Рис.3. Оконтурена точкова множина

Для оцінки однозначності результату роботи алгоритму контури множини визначались три рази при різній послідовності вершин. В першому тесті послідовність відповідала порядку зростання номерів вершин, в другому була обернена послідовність, в третьому - довільна. Результат отримали однаковий.

5. Аналіз плоскої множини точок.

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

1. Вершини степеня 1 (як і в [11] - В1) - точки 19, 27.

2. Вершини степеня 2 (як і в [11] - В2) - точки 18, 20, 24, 25, 26, 28, 29, 31, 32.

3. Вершини розгалуження (В3) - це вершини, оточення яких складається з двох і більше компонент (в [7] - шарнір , в роботі [11] - це точки типу В3 і В4) - точки 9, 10, 12, 13, 16, 17, 22, 30, 33, 47.

4. Ребра, інцидентні вершинам В1, В2, В3 і В4.

5. Підмножини першого типу (ПМ1), що складаються з внутрішньої вершини і вершин її оточення [11] (в [6] - з'єднання зіркового і циклічного графу або колеса). На рис. 4 таких підмножин п'ять: 1-2-3-4-5-11, 5-6-7-8-9-11, 41-33-34-43-42-39-40, 42-41-43-36-37-38-39, 43-34-35-36-42-41.

Рис.4. Класифікація елементів вимірно-неоднорідного двовимірного симпліціального комплексу

6. Підмножин другого типу (ПМ2), які складаються з пар трикутників, які не входять в ПМ1, суміжних по ребру; вершини трикутників, які не інцидентні суміжному ребру, не повинні мати вагу 2 і не повинні бути типу В3: 45-46-48-49, 46-47-48-49 та інші (рис.4).

7. Підмножин третього типу (ПМ3), що складаються з трикутників, які не ввійшли до складу ПМ1 і ПМ2: 9-10-11, 9-12-16, 13-14-15, 21-22-23, 44-45-49.

Вершини типу В3 і В4 фактично виконують однакові функції, тому автори їх об'єднали в один елемент класифікації. Аналогічно об'єднані ребра Р1 і Р2.

Введення підмножин другого типу ПМ2 авторської класифікації, відмінної від розробленої в роботі [11], дозволяє частково згладити апроксимувальні криві (рис.5). Обмеження (пункт 6) для вершин підмножин другого типу призначені для того, щоб не втрачалися крайні точки при стиснені точкових множин, які виглядають як смуга.

а) б)

Рис.5. Апроксимувальна крива: а - без застосування підмножин другого типу ПМ2, б - з застосуванням підмножин ПМ2

6. Після аналізу симпліціального комплексу проводиться етап його стиснення. Для цього елементи, зазначені в пунктах 1-4, фіксуються, а підмножини ПМ1-ПМ3 апроксимуються центроїдами їх вершин. Фіксовані вершини В3 і В4 сполучаються з центроїдами підмножин, яким вони належали, ребрами. Центроїди підмножин, суміжних як мінімум по ребру, теж сполучаються ребрами, за винятком випадку, показаного на рис.6, де підмножини першого типу, пов'язані з внутрішніми вершинами А і В, суміжні по ребру 3-4. Але поява ребра А-В (на рис.6 показано пунктиром) призводить до виникнення тривимірного симплексу (тетраедра) АВCD. В роботі [11] не було запропоновано конкретного алгоритму для позбавлення від таких ребер.

Рис.6. Випадок, коли центроїди суміжних підмножин першого типу не сполучаються ребром (показано пунктиром)

Для цього пропонується виконувати тріангуляцію Делоне для вершин В1-В4 і центроїдів підмножин ПМ1-ПМ3, і видаляти ребра, які не належать тріангуляції.

7. В результаті кожного етапу стиснення точкових множин втрачається крайня точка апроксимованої кривої, що зменшує область її існування. Щоб запобігти цьому в роботі [5] запропоновано такий алгоритм відновлення крайньої точки після кожного етапу стиснення.

1. Нехай кінцевою вершиною вітки кривої після стиснення є точка С (рис.7,а).

2. Через точку С проводимо пряму а, яка перпендикулярна до прямої ВС.

3. Відбираємо навколишні вершини, що лежать по інший бік від прямої а ніж точка В. Це будуть точки 1 і 2;

4. Відкладаємо одиничні вектори на променях С1 і С2;

5. Результуючий вектор задає напрям кінцевого ребра CD, а вершина D є найдальшою від вершини С з ортогональних проекцій вершин 1 і 2 на пряму кінцевого ребра. Як видно з рис.7, а, такий алгоритм призводить до появи осциляцій, тому пропонується в пункті 4 відкладати не одиничні вектори, а вектори С1 і С2. Результат цієї зміни показано на рис. 7, б.

а) б)

Рис.7. Відновлення крайніх вершин: а - згідно алгоритму, наведеному в роботі [5], б - модифіковане

8. Після кожного стиснення множини проводиться її аналіз і наступні етапи стиснення виконуються до повного зникнення підмножин ПМ1-ПМ3.

На рис. 8 показано оконтурену множину точок і її апроксимувальну дискретно представлену криву після першого етапу стиснення. На рис. 9 і 10 показано апроксимувальну дискретно представлену криву після другого і третього етапу стиснення.

Авторами було проведено тест на швидкодію виконання даного алгоритму на ПК для описаного вище прикладу. Параметри ПК: процесор Atlon 2000, RAM 512 Mb. Результати тестування: тріангуляція Делоне - 0.1094 с, визначення найближчих точок (сусідів) вершин графа - 2,5313 с, видалення неістотних в'язей - 0,0313 с, перший етап стиснення множини - 3,3783 с, другий - 0,4268 с, третій - 0,2613 с; загальний час - 6,73 с.

Рис.8. Оконтурена множина точок і її апроксимувальна дискретно представлена крива після першого етапу стиснення

Рис.9. Оконтурена множина точок і її апроксимувальна дискретно представлена крива після другого етапу стиснення

Рис.10. Оконтурена множина точок і її апроксимувальна дискретно представлена крива після третього етапу стиснення

Висновки

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

Література

1. Зенкевич О., Морган К. Конечные элементы и аппроксимация. - М.: Мир, 1986. - 318 с.

2. Корнійчук Н.П. Сплайны в теории приближения. -М.: Наука, 1984. - 351с.

3. Пугачов Є.В. Дискретне геометричне моделювання скалярних і векторних полів стосовно будівельної світлотехніки. Дис. … д-ра техн. наук: 05.01.01/КНУБА. - К., 2001. - 324 с.

4. Уилсон Р. Введение в теорию графов. - М.: Мир, 1977. - 207 с. 7. Зыков А.А. Основы теории графов. - М.: Наука, 1987. - 384 с.

5. Александров П.С. Комбинаторная топология. - Л.: Гостехиздат, 1947. - 660 с. 9. Препарата Ф., Шеймос М. Вычислительная геометрия. - М.: Мир, 1989. - 478 с.

6. Пугачов Є.В. Визначення контурів плоскої множини точок //Прикл. геометрія та інж. графіка. -1998. - Вип. 63. - С. 75 - 79.

7. Пугачов Є.В. Дискретна апроксимація плоскої множини точок лінією Прикл. геометрія та інж. графіка. - 2000. - Вип. 67. - С. 78 - 81.

Размещено на Allbest.ru