Структурная оптимизация модели триангуляции на основе многокритериальных оценок тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Шалиткин, Андрей Владимирович

• Шалиткин, Андрей Владимирович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Шалиткин, Андрей Владимирович

Введение.

Глава 1. Обзор.

1.1. Модели представления пространственных данных.

1.2. Построение поверхностей.

1.3. Алгоритмы анализа данных.

1.4. Постановка задачи.

Глава 2. Критерии оптимальности.

2.1. Оптимальность Е11-модели.

2.2. Постановка обобщенной задачи поиска оптимальной модели.

2.3. Автоматизация процесса поиска оптимальной модели.

2.4. Интегральный критерий оптимальности сетки триангуляции

2.5. Выводы.

Глава 3. Анализ и построение алгоритмов.

3.1. Методика поиска оптимальной модели данных.

3.2. Исследование мощности алгоритмов синтеза.

3.3. Исследование мощности алгоритмов анализа.

3.4. Общий критерий оптимальности модели данных.

3.5. Оптимизация сетки на основе интегрального критерия.

3.6. Выводы.

Глава 4. Реализация и практическое исследование.

4.1. Шаблон графической системы.

4.2. Комплекс для тестирования алгоритмов оптимизации сетки.

4.3. Исследование интегрального критерия оптимальности сетки.

4.4. Детализация алгоритма оптимизации сетки триангуляции.

Введение диссертации (часть автореферата) на тему «Структурная оптимизация модели триангуляции на основе многокритериальных оценок»

Триангуляционная?модель широко используется- в. различных системах работы с пространственными данными. Объекты описываются с помощью; поверхностей, которые, в свою очередь, являются'сетками триангуляции.

Детальное описание данной модели приводится в работах Abdul-Rahman А. [36], [37], Jones С. [52]. В работе Frank А. [50] показано представление структуры данных сетки триангуляции в виде ER-модели, в работе Worboys М. [74] освещаются аспекты применения ООП для хранения модели. В работе Скворцова A.B. [17] описано несколько наиболее часто используемых ER-моделей сетки триангуляции. В ряде работ Тюкачева H.A. [19], [20], [21], [23] описано применение триангуляционной модели в различных системах работы с трехмерными данными; В работе Тюкачева H.A. [22] впервые описаны критерии оптимальности модели данных двумерной триангуляционной сетки. В данной диссертации проведено более глубокое исследование критериев оптимальности модели данных, обобщение на произвольную ER-модель и разработана методика поиска оптимальной структуры ER-модели. Общая задача поиска оптимальной структуры ER-модели рассматривается в данной работе впервые.

Алгоритмы построения триангуляционной сетки с точки зрения геометрии рассмотрены в работах Роджерса Д. [14], Скворцова A.B. [17], [18], Ильмана В.М. [7], [8], Dwyer R. [50], Lewis В.[56]. Рассматриваемые в этих работах алгоритмы, как правило, позволяют строить сетку, удовлетворяющую критерию Делоне. В работах Baker В. [38], Bern М. [39], Mitchell S. [62], Chew L. [43], Ruppert J. [68] были предложены алгоритмы, позволяющие получать треугольники с дополнительными ограничениями, основанными на локальных критериях: отношение сторон треугольников, границы значений углов треугольников. В данной работе приводится описание интегрального критерия оптимизации сеткщ учитывающего несколько параметров оптимизации, а также алгоритмов постоптимизации сетки на его основе.

В ряде систем предъявляются жесткие требования к объему памяти, необходимой для хранения модели, быстроте выполнения-, алгоритмов, затратам на поддержку кода, то есть простоте программной реализации алгоритмов анализа данных и их точности. Хотя, модель сильно-влияет на, почти все вышеперечисленные характеристики, чаще всего она определяется интуитивно.

Триангуляционную модель данных можно представить в виде частного случая entity-relationship model (ER-модели), структура которой определяется набором сущностей и связями между этими сущностями, что позволяет рассматривать задачу определения модели данных, удовлетворяющей указанным требованиям, в контексте любой системы, использующей ER-представление, например СУБД.

С геометрической точки зрения структура триангуляции имеет множество характеристик, таких как размер, форма, равномерность сетки. Эти характеристики непосредственно влияют на точность результатов выполнения алгоритмов анализа данных. Существует множество алгоритмов триангуляции, которые позволяют получить сетку с треугольниками, удовлетворяющими некоторым требованиям: критерий Делоне, размеры углов, отношения сторон, сумма длин ребер и т. д., однако используемые критерии при этом чаще всего являются локальными и не учитывают всех необходимых характеристик.

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

Целью работы является разработка математического и программного обеспечения, позволяющего проводить структурную оптимизацию модели триангуляции на основе многокритериальных оценок для обеспечения экономии памяти, скорости и точности выполнения алгоритмов анализа в системах хранения и обработки пространственных данных.

Задачи исследования

Для достижения поставленной цели необходимо выполнение следующих задач:

1. Построение критерия оптимальности структуры данных триангуляционной модели, учитывающего объем памяти, необходимый для хранения модели, и скорость выполнения заданного набора алгоритмов.

2. Разработка методики, позволяющей проводить автоматизированный поиск оптимальной структуры данных по описанному в предыдущем пункте критерию.

3. Получение оптимальных структур данных триангуляционной модели для использования совместно с основными алгоритмами синтеза и анализа, применяемыми в системах хранения и обработки пространственных данных.

4. Построение критерия, позволяющего оптимизировать геометрическую структуру сетки триангуляции на основе ее интегральных свойств.

5. Разработка алгоритмов оптимизации геометрической структуры сетки триангуляции на основе описанного выше критерия.

Объектом исследования являются модели сеток триангуляции. Предметом исследования являются структура данных и геометрическая структура модели триангуляции.

Методы исследования. При выполнении работы использовались элементы теории графов, оптимизации, вычислительной геометрии, теории вероятностей и математической статистики, теории баз данных, комбинаторики.

Научная новизна работы состоит в следующем:

1. Впервые сформулирована постановка задачи поиска оптимальной ЕИ-модели для произвольного количества сущностей по критериям требуемого для ее хранения объема памяти и скорости выполнения заданного набора алгоритмов. К данной задаче сводится задача поиска оптимальной структуры данных модели триангуляции.

2. Разработана методика решения задачи поиска оптимальной ЕЯ-модели, включающая автоматизированный поиск на основе генетического алгоритма, позволяющего найти приближенное решение за приемлемое время.

3. Предложен критерий, позволяющей проводить оптимизацию интегральных свойств геометрической структуры триангуляционной сетки.

На защиту выносятся:

• постановка задачи поиска оптимальной ЕЛ-модели, к которой сводится задача оптимизации структуры данных модели триангуляции, по критериям требуемого для ее хранения объема памяти и скорости работы заданного набора алгоритмов, а также методика ее решения;

• полученные структуры данных триангуляционной модели, оптимальные для использования с основными алгоритмами синтеза и анализа, используемыми в системах хранения и обработки пространственных данных;

• критерий, позволяющий проводить оптимизацию интегральных свойств геометрической структуры сетки триангуляции и аспекты его применения.

Проведенные исследования соответствуют специальности 05.13.17 -«Теоретические основы информатики».

Практическая значимость состоит в возможности получения структуры данных модели триангуляции, оптимальной с точки зрения быстродействия алгоритмов анализа данных и потребляемого объема памяти. Кроме того, описанная методика позволяет проводить оптимизацию при рефакторинге баз данных.

Использование разработанного критерия оптимальности сетки триангуляции позволяет улучшить результаты работы алгоритмов анализа данных в системах, использующих триангуляционыую модель.

Результаты диссертационной работы внедрены в ООО «Центр менеджмента, оценки и консалтинга», а также воронежском филиале ОАО «Туполев» - конструкторское бюро.

Апробация работы. Основные положения диссертационной работы были доложены на конференциях: «Информатика: проблемы, методология, технологии» (Воронеж, 2008), «Информатика: проблемы, методология, технологии» (Воронеж, 2010), «Современные проблемы науки» (Тамбов, 2010), научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов Воронежского государственного университета (Воронеж, 2008-2011).

Публикации. Основное содержание диссертационной работы изложено в 10 работах, из них 4 статьи в журналах, реферируемых ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Материал изложен на 110 страницах, содержит 40 рисунков и 8 таблиц. Список литературы из 76 источников. —

Заключение диссертации по теме «Теоретические основы информатики», Шалиткин, Андрей Владимирович

4.8. Выводы

В главе 4 описывается архитектура ПО, разработанного для проведения практических исследований, а также приводятся результаты этих исследований.

Так, для проверки алгоритмов оптимизации сетки был разработан комплекс приложений, позволяющий тестировать различные алгоритмы триангуляции, оптимизации и анализа для двумерного и трехмерного случаев. Кроме того, в силу частоты применения графических решений в ряде приложений, общая архитектура описана как шаблон проектирования. За основу взят МУС-шаблон, который обеспечивает «слабую связность» между элементами системы, что позволяет улучшить расширяемость системы, упростить поддержку кода.

Так как с точки зрения топологии разница между трехмерной и двумерной триангуляцией не велика, основная часть исследований проводилась для двумерного случая и затем обобщалась на трехмерный.

Для автоматизации поиска оптимальной ЕК.-модели было реализовано

Заключение

В диссертации проведены исследования в соответствии с целью и поставленными задачами. Достигнуты следующие результаты, имеющие научное и практическое значение:

1. Задача оптимизации структуры данных модели триангуляции сведена к задаче поиска оптимальной ER-модели по критериям требуемого для ее хранения объема памяти и скорости выполнения заданного набора алгоритмов.

2. Разработана методика решения описанной в предыдущем пункте задачи, включающая автоматизированный поиск оптимальной ER-модели на основе генетического алгоритма, применения которого позволяет решить поставленную задачу за приемлемое время. В силу общности самой задачи, методика может применяться не только для поиска оптимальной структуры данных модели триангуляции, но и для ряда других задач, в частности для оптимизации схем баз данных.

3. Получены оптимальные структуры данных триангуляционной модели для использования с набором основных алгоритмов синтеза и анализа, применяемых в системах хранения и обработки пространственных данных.

4. Разработан критерий, позволяющий, в отличие от существующих локальных критериев, проводить оптимизацию интегральных свойств сетки триангуляции: формы и размера треугольников, равномерности сетки.

5. Описаны аспекты применения методов оптимизации, в частности алгоритма имитации отжига, методов нулевого и первого порядка, для оптимизации сетки триангуляции с помощью техники флипа и техники переноса точек на' основе разработанного интегрального критерия.

6. Разработан комплекс программ, включающий в себя визуальный редактор для проверки алгоритмов оптимизации сетки триангуляции и приложения для автоматизированного поиска оптимальной ЕЯ-модели. Проведено практическое исследование применения генетического алгоритма для поставленной задачи и получены оптимальные значения следующих параметров: размер пула, элиты, вероятность мутации элемента, вероятность мутации гена, селективная стратегия.

Список литературы диссертационного исследования кандидат технических наук Шалиткин, Андрей Владимирович, 2011 год

1. Азарнова T.B. Методы оптимизации: Элементы теории, алгоритмы и примеры / Т.В. Азарнова, И.Л. Кашира, Г.Д.' Чернышова. - Воронеж: Изд-во ВГУ, 2000. - 101 с.

2. Алейников С.М. Алгоритмы построения пространственных гранично-элементных сеток. / Алейников С.М., Бахтин A.A., Ткжачев H.A. // Мат. per. науч.-мет. конф. Информатика: проблемы, методология, технологии. Воронеж: ВГУ, 2004. - Вып. 4. - С. 48-52.

3. Грэй П. Логика, алгебра и базы данных / Пер. с англ. М.: Машиностроение. - 1989. - 359 с.

4. Делоне Б.Н. О пустоте сферы Текст. / Изв. АН СССР. ОМЕН, 1934.-№4.-С. 793-800.

5. Дубровин Б.А. Современная геометрия: методы и приложения Текст.: учеб. пособие для студ. физ.-мат. спец. ун-тов / Б.А. Дубровин, С.П. Новиков, А.Т. Фоменко. М.: Наука, 1979. - 759 с.

6. Ильман В.М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек / Алгоритмы и программы, ВИЭМС. Вып. 10(88). -М.: 1985.-С. 3-35.

7. Ильман В.М. Экстремальные свойства триангуляции Делоне / Алгоритмы и программы, ВИЭМС. Вып. 10(88). М.: 1985. - С. 57-66.

8. Касьянов В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев. СПб.: БХВ-Петербург, 2003. - 1104 с.

9. Коннолли Т. Базы данных проектироване реализация и сопровождение / Т. Коннолли, К. Бегг, А. Страчан. М.: Вильяме, 2001. -1120 с.

10. Ласло М. Вычислительная геометрия и компьютерная графика наS

11. С++ Текст. / Ласло М. М.: Изд-во «БИНОМ», 1997. - 304 с.

12. Лотов A.B., Поспелова И.И. многокритериальные задачи принятия решений: Учебное пособие. М:: Макс Пресс, 2008. - 197с.

13. Препарата Ф. Вычислительная геометрия: введение / Ф. Препарата, М. Шеймос. М.: Мир, 1989. - 478 с.

14. Численное моделирование. Фронтальные алгоритмы построения треугольной сетки. Электронный ресурс. // URL: http://ps300.narod.ru/fr3d/mesh.htm.(Дата обращения: 01.07.10.)

15. Роджерс, Д. Алгоритмические основы машинной графики Текст. / Пер. с англ. М.: Мир, 1989. - 512 с.

16. Скворцов A.B. Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции / A.B. Скворцов. Томск: Изд-во Том. ун-та, 2002. - С. 116-123.

17. Скворцов A.B. Линейно-узловой алгоритм построения оверлеев двух полигонов // Вестник Томского гос. ун-та. 2002. - № 273. - С.99-103.

18. Скворцов A.B. Триангуляция Делоне и её применение / A.B. Скворцов. Томск: Изд-во Том. ун-та, 2002. - 128 с.

19. Скворцов A.B. Алгоритмы построения и анализа триангуляции. / Скворцов A.B., Мирза Н.С. Томск: Изд-во Томск, ун-та, 2006. - 168 с.

20. Тюкачев H.A. Автоматическое построение слоев геологического разреза. / Вестник ВГУ. Серия: Системный анализ и информационные технологии. 2006. - №1. - С. 141-144.

21. Тюкачев H.A. Определение принадлежности точки многоугольнику общего вида методом трассировки луча / Вестник ВГТУ. 2009. - № 4. - С. 94-98.

22. Тюкачев H.A. Оверлей многогранников / Вестник ВГТУ. 2009. - № 6.-С. 131-137.

23. Тюкачев H.A. Выбор ER-модели для описания поверхности трехмерных тел / Вестник ВГТУ. 2009. - № 4. - С. 14-24.

24. Тюкачев H.A. Разработка алгоритмов вычислительной геометрии и их реализация в трехмерной геоинформационной системе / Тюкачев H.A. -Воронеж: Изд. ВГТУ, 2009. 244 с.

25. Тюкачев H.A. Компьютерная графика и мультимедиа. / H.A. Тюкачев, И.В. Илларионов, В.Г. Хлебостроев// Воронеж: Изд. ВГТУ, 2008. -794 с.

26. Ченцов О.В. Обзор алгоритмов построения оверлеев многоугольников. / О.В. Ченцов, A.B. Скворцов // Вестник ТГУ. 2003. - № 280. - С. 338-345.

27. Шалиткин A.B. Интегральный критерий оптимальности конечно-элементной сетки. / Вестник ВГТУ. Серия: Системный анализ и информационные технологии. 2009. - С.28-30.

28. Шалиткин A.B. Оптимальный выбор луча в задаче определения принадлежности точки многограннику // Тамбов: Перспективы науки, 2010. - С.64-67.

29. Шалиткин A.B. Поиск оптимальной' ER-модели для некоторых алгоритмов триангуляции. / Информатика: проблемы, методология, технологии: материалы X международной науч.-метод. Конференции. // Вестник ВГТУ. 2010. - С. 339-342.

30. Шалиткин А.В. Шаблон проектирования графического редактора. / Вестник ВГТУ. Серия: Системный анализ и информационные технологии. -2010.-С. 95-98.

31. Шалиткин А. В. Решение обобщенной задачи поиска оптимальной ER-модели на основе генетического алгоритма / А.В. Шалиткин, Н.А. Тюкачев, П.А. Цветков // Вестник ВГТУ. 2011. - С. 204-207

32. Шалиткин А.В. Применения алгоритма имитации отжига для оптимизации сетки триангуляции на основе интегральной оценки / А.В. Шалиткин, Н.А. Тюкачев // Вестник ВГТУ. 2011. - С. 202-204.

33. A. Abdul-Rahman Spatial Data Modeling for 3D GIS. / A.Abdul-Rahman, M.Pilouk Berlin: Springer, 2008. - 290 p.

34. A. Abdul-Rahman. Triangular irregular network in digital terrain relief modelling. // M. Sc. Thesis, ITC, Enschede, The Netherlands. 1992. - 80 p.

35. B. Baker Nonobtuse triangulation of polygons. / B. Baker, E. Grosse,

36. C.S. Rafferty. // Disc. And Comput. Geom. 1988. - № 3. - 168 p.

37. Bern M. Mesh generation and optimal 'triangulation. / Bern M., Eppstein

38. D. // World Scientific. 1992. - P. 23-90.

39. Bric, V. 3D vector data structures and modelling of simple objects in GIS. / M. Sc. Thesis, ITC, Enschede, The Netherland. 1993. - 107 p.

40. Censor, Y. "Pareto Optimality in Multiobjective Problems " Appl. Math. Optimiz. 1977. - Vol. 4. - P. 41-59.

41. P. Chen Entity-Relationship Approach to Information. Modeling and Analysis / Proceedings of the Second International Conference on the Entity-Relationship Approach. North-Holland. -1983. - P. 19-28.

42. L. Chew. Guaranteed-quality triangular meshes. / Technical Report TR89983. Cornell University, Computer Science Department, 1989.

43. Dereli T. A hybrid simulated annealing algorithm for 2D packing problems. / Dereli Т., Da§ G.S. // Proceedings of 5th International Symposium on Intelligent Manufacturing Systems. -2006. P. 959-966.

44. Dong F. Three-dimensional models and applications in subsurface modeling. / Department of Geomatics Engineering Reports No. 20093. -University of Calgary, 1996. 93 p.

45. Dowsland K.A. Some experiments with simulated annealing techniques for packing problems. / European Journal of Operational Research. 1993. - Vol. 68.-P. 389-399.

46. Dwyer R.A. A fast divide-and-conquer algorithm for constructing Delaunay triangulations. / Algorithmica 1987. - Vol. 2. - p. 137-151.

47. Gamma E. Design Patterns: Elements of Reusable Object-Oriented Software. / E.Gamma, R. Helm, R. Johnson, and J. Vlissides.// Boston: Addison Wesley Professional, 1994. - 395 p.

48. Evans F. Optimizing triangle strips for fast rendering. / Evans F., Skiena S., Varshney A. // Proc. IEEE Visualization. 1996. - P. 319-326.

49. Frank A.U. Cell graphs: a provable correct method for the storage of geometry. / Frank A.U., Kuhn W. // Proc. of the Second International Symposium on Spatial Data Handling. 1986. - P. 411-436.

50. GRAPP электронный толковый словарь по теории графов и ее применению в информатике. Электронный ресурс. // - URL: http://pco.iis.nsk.su/grapp. (Дата обращения: 05.09.2009)

51. Jones С.В. Data structures for three-dimensional spatial information systems in geology. / International Journal of Geographical Information Systems. -1989.-Vol.3.-P. 15-31.

52. Kampke T. Simulated, annealing: Use of a new tool in bin-packing. / Journal Annals of Operational Research. 1988. - Vol. 16. - P. 327-332:

53. Kirkpatrick S. Optimization by simulated annealing./ Kirkpatrick S., Gelatt C.D., VecchiM.P. // Science. 1983. - Vol. 220, No. 4598. - P. 671-680.

54. Lai K.K. Developing a simulated; annealing algorithm for the cutting stock problem. / Lai K.K., Chan, J.W.M. // Computers & Industrial Engineering. -1997.-Vol. 32.-P. 115-127

55. Lewis B.A. Triangulation of planar regions with applications. / Lewis B.A., Robinson J.S. // Computer Journal. 1978. - Vol; 21 - P. 324-332.

56. Maguire D.J. Functionality of GISs. / Maguire D.J., Dangermond J. // Geographical Information Systems. 1991. - Vol. 1. - P. 319-335.

57. Margalit A. An algorithm for computing the union, intersection or difference of two polygons / Margalit A., Knott G.D. // Computers & Graphics. -1989.-Vol.13.-P. 167-183.

58. Melanie M. An Introduction to Genetic Algorithms. / Cambridge: "A Bradford Book" The MIT Press, 1999. - 158p.

59. Midtb®, T. Spatial modelling by Delaunay networks of two and three dimensions: Thesis . Dr. Ing. Science / Midtb0, T. Norway: Norwegian Institute of Technology, University of Tronheim, 1993. - 147 p.

60. Mirante A. The radial sweep algorithm for constructing trianguled irregular networks. / Mirante A., Weingarten N. // IEEE Computer Graphics and Applications. 1982. - Vol. 2. - P. 11-21.

61. Mitchell S.S. Quality mesh generation in three dimensions. / Mitchell S.S and Vavasis S.A. // In Proceedings of the Eighth Annual Symposium on Computational Geometry. 1992. - P. 93-111

62. Pilouk M. Integrated Modelling for 3D GIS: Thesis . Dr. Physics Science / Pilouk M. ITC Publication, 1996: - No. 40. - 200 p.

63. Puppo E. Variable resolution triangulations / Computational Geometry Theory and Applications 1998. - Vol 11. - P. 219-238.

64. Raper J. The 3-dimensional geoscientific mapping and modelling' system: a conceptual design. / In: Raper, J (Ed.) London: Taylor & Francis, 1989.-P. 11-20.

65. Raper J. Three-dimensional GIS. / Raper. J. and Kelk. B. // In: Geographical information systems: principles and applications. D J. Maguire; M. Goodchild and D.W. Rhind (eds.) London: Longman, 1991. - P. 299-317

66. Rothlauf F. Representations for Geneticand Evolutionary Algorithms. // Berlin: Springer, 2006. - 325 p.

67. Ruppert J. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. / Submission to Journal of Algorithms. 1994. - Vol. 18. - P. 548-585.

68. Sloan S.W. A fast algorithm for constructing Delaunay triangulations in the plane. / Advanced Engineering Software 1987. - Vol 9. - P. 34-55.

69. Sutherland I.E. Reentrant polygon clipping / Sutherland I.E., Hodgman

70. G.W. // CACM. 1983. - Vol 26. - P. 868-877.

71. Watson D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. / Computer Journal. 1981'. - Vol 24. - P. 167172.

72. Weiler K. Polygon comparison using graph representation / Computer Graphics. 1980. - Vol 14. - P. 10-18.

73. Weiler K. Hidden surface removing using polygon area sorting / Weiler K., Atherton P. // Computer Graphics. 1977. - Vol 10. - P. 214-222.

74. Worboys M.F. Object-oriented data modelling for spatial databases. / Worboys M.F., Hearnshaw H.M., Maguire D.J. // International Journal of Geographical Information Systems. London: Taylor & Francis, 1990. - Vol. 4. -P. 369-383.

75. Youngman C. Spatial data structures for modeling subsurface features. / In: Raper, JF (Ed.). Three Dimensional Applications in Geographic Information Systems. London: Taylor & Francis, 1989. - P. 129-136.

76. Zadeh L.A., "Optimality and Nonscalar-valued Performance Criteria," // IEEE Trans. Automat. Contr. 1963. - Vol 8. - P. 1.