РОЗДІЛ 2
АЛГОРИТМІЗАЦІЯ ВІЗУАЛІЗАЦІЇ БАГАТОВИМІРНИХ ДАНИХ
Поставлене в підрозділі 1.4 завдання розробки автоматизованої системи містило в
собі розробку алгоритмів, інформаційного та програмного забезпечення вирішення
задач візуалізації багатовимірних даних в ГІС із застосуванням
сплайн-операторів. При цьому в другому розділі ставиться завдання:
Алгоритмізації процедур обчислення коефіцієнтів поліноміальних сплайнів на
основі В-сплайнів, близьких до інтерполяційних у середньому (підрозд. 2.1);
Проведення аналізу ефективності створеного алгоритмічного забезпечення
обчислення коефіцієнтів поліноміальних сплайнів (підрозд. 2.2).
Розробки, із застосуванням об’єктно-орієнтованого програмування та технології
OpenGL, компоненти автоматизації відтворення та візуалізації поверхонь та
гіперповерхонь за статистичними масивами (підрозд. 2.3).
Алгоритмізація обчислення коефіцієнтів багатовимірних поліноміальних сплайнів
[91]
Розвиток обчислювальної техніки постійно вимагає оновлення та вдосконалення
математичного апарату опрацювання даних в автоматизованих інформаційних
системах. Відносно складні, з точки зору алгоритмізації, класичні методи
апроксимації гладких функцій [60] за подібними даними не завжди можуть
задовольнити розробників програмних та апаратних засобів розв’язку задач
побудови візуальних моделей, поповнення даних, тощо. Так, наприклад метод
найменших квадратів потребує вирішення системи рівнянь вищого порядку, що
вимагає значних обчислювальних затрат, метод рівномірного наближення потребує
використання методів нелінійного програмування, тощо.
На заміну класичним приходять методи, що базуються на обчислювальному аспекті,
зокрема процедури, основані на використанні багатовимірних поліноміальних
сплайнів на основі В-сплайнів, близьких до інтерполяційних у середньому [83].
Задачею підрозділу є розробка алгоритму приведення процедури обчислення
значення багатовимірного поліноміального сплайну на основі В-сплайнів
Рисунок 2.1. Алгоритм обчислення коефіцієнтів сплайну на базі В-сплайнів,
близького до інтерполяційного у середньому, від двох змінних (початок)
(1.1), до лінійного вигляду з використанням, по можливості, елементарних
операцій "+", "–" і якомога меншої кількості операцій множення та ділення.
Отримання аналітичної формули для обчислення значень сплайну від двох або
більшої кількості змінних у розгорнутому вигляді є досить трудомісткою задачею.
Вирішенням даної задачі є автоматизація цього процесу, тобто
Рисунок 2.2. Алгоритм обчислення коефіцієнтів сплайну на базі В-сплайнів,
близького до інтерполяційного у середньому, від двох змінних (продовження)
Рисунок 2.3. Алгоритм [? STR – функція переведення цифрового значення у
строкове] обчислення коефіцієнтів сплайну на базі В-сплайнів,
близького до інтерполяційного у середньому, від двох змінних (продовження)
створення алгоритму, результатом роботи якого є отримання лінійного оператору
для обчислення значення сплайну будь-якої розмірності та ступеня уточнення.
Наведений алгоритм (рис. 2.1-2.4) призначений для обчислення коефіцієнтів
сплайну від двох змінних, однак його неважко модифікувати для обчислення
сплайну від будь-якої кількості змінних. Умовно, отриманий алгоритм можна
розбити на три складові: 1) підготовка загальних даних для подальших обчислень
(рис. 2.1, блоки 2-17); 2) обчислення матриці коефіцієнтів сплайну
(рис. 2.1-2.3, блоки 18-66); 3) генерування на базі отриманих коефіцієнтів
формули обчислення значення сплайну (рис. 2.3-2.4, блоки 67-90).
Рисунок 2.4. Алгоритм [? LEN – функція підрахунку кількості знаків у рядку]
обчислення коефіцієнтів сплайну на базі В-сплайнів,
близького до інтерполяційного у середньому, від двох змінних (закінчення)
Перша складова алгоритму фактично відповідає за формування коефіцієнту К, який
в подальшому буде використовуватись при генеруванні формули обчислення значень
сплайну. Коефіцієнт К являє собою коефіцієнт Кr,u в ступені n, де – Кr,u
коефіцієнт при відповідній матриці , n – кількість змінних, від яких буде
обчислюватися сплайн, Gr,u – це відповідні матриці .
Друга та третя частини алгоритму разом являють собою реалізацію формули (2.1).
Коефіцієнти сплайну, що обчислюються, заносяться до матриць MCoef та sMCoef
відповідної розмірності. Матриця MCoef після закінчення роботи алгоритму буде
містити значення коефіцієнтів сплайну у чисельному вигляді, а матриця sMCoef –
у строковому, для подальшого використання у третій частині алгоритму.
Остання частина алгоритму відповідає за формування формули обчислення значення
сплайну у формі, що відповідає постановці задачі, тобто з використанням якомого
меншої кількості операцій: "+", "–", "*", "/". Генерування формули здійснюється
у тимчасову строкову змінну tmpS, при цьому, враховуючи постановку задачі,
проводиться групування відносно змінних x та y. У зв’язку з тим, що результуюча
формула може бути досить великого обсягу було прийняте рішення зберігати її у
масиві рядків, при цьому кількість знаків у рядку не повинна перевищувати 100.
Це розбиття реалізовано за допомогою умови (рис. 2.4, блок 83).
Результатом програмної реалізації створеного алгоритму є розроблена автором
система автоматизованого обчислення коефіцієнтів багатовимірних поліноміальних
сплайнів SplineMaker [91]. Використання цього програмного продукту дає змогу
значно збільшити швидкість обчислення коефіцієнтів поліноміальних сплайнів
(S2,0, S2,1, S2,2, S3,0, S3,1, S3,2, S4,0, S4,1, S4,2) від однієї, двох або
трьох змінних. Наприклад обчислення коефіцієнтів сплайну S4,0 від трьох змінних
(додаток Д) на сучасній ЕОМ (Intel Pentium 4 HT 2.8GHz) займає приблизно 0.516
сек. При цьому кількість коефіцієн
- Київ+380960830922