Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології

Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології

Збережено в:
Бібліографічні деталі
Дата:2009
Автор: Яцишин, А.В.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2009
Назва видання:Моделювання та інформаційні технології
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/29663
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології / А.В. Яцишин // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 7 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-29663
record_format dspace
spelling irk-123456789-296632011-12-26T12:22:07Z Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології Яцишин, А.В. 2009 Article Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології / А.В. Яцишин // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 7 назв. — укр. XXXX-0068 http://dspace.nbuv.gov.ua/handle/123456789/29663 621.039.7.001.2 uk Моделювання та інформаційні технології Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
format Article
author Яцишин, А.В.
spellingShingle Яцишин, А.В.
Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології
Моделювання та інформаційні технології
author_facet Яцишин, А.В.
author_sort Яцишин, А.В.
title Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології
title_short Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології
title_full Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології
title_fullStr Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології
title_full_unstemmed Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології
title_sort модифікація алгоритму лоуренса берклі для задач відображення трансформованих карт в задачах екології
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
publishDate 2009
url http://dspace.nbuv.gov.ua/handle/123456789/29663
citation_txt Модифікація алгоритму Лоуренса Берклі для задач відображення трансформованих карт в задачах екології / А.В. Яцишин // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 7 назв. — укр.
series Моделювання та інформаційні технології
work_keys_str_mv AT âcišinav modifíkacíâalgoritmulourensaberklídlâzadačvídobražennâtransformovanihkartvzadačahekologíí
first_indexed 2025-07-03T09:53:02Z
last_indexed 2025-07-03T09:53:02Z
_version_ 1836619013678956544
fulltext УДК 621.039.7.001.2 Яцишин А.В. МОДИФІКАЦІЯ АЛГОРИТМУ ЛОУРЕНСА БЕРКЛІ ДЛЯ ЗАДАЧ ВІДОБРАЖЕННЯ ТРАНСФОРМОВАНИХ КАРТ В ЗАДАЧАХ ЕКОЛОГІЇ Актуальність Розробка спеціальних методів візуалізації і засобів математичного моделювання систем з такими складними багатовимірними характеристиками об’єктів, як екологічні, є актуальною для глибокого дослідження структури системи як єдності компонентів і зв’язків при одночасному врахуванні великої кількості різнорідних параметрів [1, 2]. В нашому багатовимірному світі виникає необхідність аналізу і візуалізації [3] таких, що варіюють в просторі і в часі, характеристик відразу декількох явищ. Завдання істотно спрощується, якщо передбачити, що одна з цих характеристик рівномірно розподілена, а останні чинники згорнуті в інтегральні показники [1,2]. Послідовність анаморфоз передає тимчасові зміни і їх можна розглядати як окремі часові зрізи процесу або явища. В книзі [4] послідовно розкриваються секрети побудови і використання анаморфоз в науковій практиці і повсякденному житті. Постановка задачі Для проектування та реалізації модуля для зображення площинних анаморфоз [5] в задачах екологічного аналізу і прогнозу був обраний алгоритм лабораторії Лоуренса Берклі [6]. Як було зазначено [7], цей алгоритм має певні недоліки, а саме:  кінцевий результат помітно залежить від порядку, у якому беруться комірки;  збільшення помилки на кожному кроці ітерації;  втрата безперервності картографічного зображення, якщо пряма, що з’єднує центр СА комірки А с точкою Qi, містить один з відрізків границі А Модифікації алгоритму призначені зменшити або виключити вплив цих недоліків на результат. Уточнення коефіцієнта деформації комірки. На кожному кроці алгоритму виправляється площа обраної комірки, а інші комірки зміщуються без зміни площі. Але при числовій реалізації алгоритму виникають помилки (помилка обчислення, помилки від заміни кривих, у які перетворяться відрізки, відрізками або ламаними лініями), які не виправляються пізніше й накопичуються. Щоб зменшити вплив цих помилок, на кожному кроці треба уточнювати для кожної комірки коефіцієнт деформації MA. A A A A p S M p S    , (1) де Ap – густина показника в комірці А, p – середня густина показника по всій території, AS – площа комірки А, AS  – площа до якої наближується комірка А. На кожному кроці ітерації перераховується MA для всіх комірок, крім обраної. На k-ом кроці коефіцієнт деформації для i-ої комірки ,A iM вираховується по формулі (2): , , A A i A i S M S   , (1, 2,3.. );i n i k  , (2) де ,A iS – площа i-ої комірки після k-ого кроку. Наприкінці останньої ітерації підраховується погрішність по формулі (3): ,1 max |1 |A ii n M     (3) Якщо 0,01  всі операції повторюються заново, поки погрішність не стане менше 0,01 або перестане зменшуватися. Визначення порядку вибору комірок. Для однозначності анаморфози визначається порядок, у якому беруться комірки для кожного алгоритму. Комірки беруться в міру зростання відстані від центра карти до центра мас комірки. Центром карти вважається точка перетину діагоналей прямокутника, у який вписана карта. Виключення при перетинанні відрізків. Пряма, що з’єднує центр СА комірки А с точкою Qi, містить один з відрізків границі А, наприклад (ai,ai+1). Якщо відрізок (ai-1,ai+2) перетинає пряму (СА, Qi), то пряма (СА, Qi) проходить через границю комірки А і точкою перетинання будемо вважати ai. Якщо відрізок (ai-1,ai+2) не перетинає пряму (СА, Qi), то пряма (СА, Qi) проходить по дотичній до границі комірки А и точки перетину не буде. Пряма, що з’єднує центр СА комірки А с точкою Qi, містить одну з вершин границі А, наприклад ai. Якщо відрізок (ai-1,ai+1) перетинає пряму (СА, Qi), то пряма (СА, Qi) проходить через границю комірки А и точкою перетину буде ai. Якщо відрізок (ai-1,ai+1) не перетинає пряму (СА, Qi), то пряма (СА, Qi) проходить по дотичній до границі комірки А и точки перетину не буде. Реалізація алгоритму Для реалізації алгоритму лабораторії Лоуренса Берклі треба реалізувати ряд підзадач: 1) знаходження точки перетину відрізків; 2) знаходження центра мас багатокутника; 3) знаходження площі багатокутника; 4) перевірка належності точки до багатокутника. Знаходження точки перетину відрізків. Будь-яка точка, що належить прямій, має координати (x, y) 2 1 1 2 1 1 ( ) ( ) , x x x x y y y y           , (4) де (x1, y1) і (x2, y2) – точки, які визначають пряму. Якщо 0 1  , то точка лежить між (x1, y1) і (x2, y2). Для знаходження точки перетину двох прямих 1 1 2 2(( , ), ( , ))x y x y і 1 1 2 2(( , ), ( , ))x y x y    треба вирішити систему рівнянь 2 1 1 2 1 1 2 1 1 2 1 ( ) ( ) ( ) ( ) , x x x x x x y y y y y y                        (5) Рішення системи (5) має вигляд: 1 1 2 1 1 1 2 1 2 1 2 1 2 1 2 1 1 1 2 1 1 1 2 1 2 1 2 1 2 1 2 1 ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) x x y y y y x x y y x x x x y y x x y y y y x x y y x x x x y y                                    Залежно від значень  і  можна довідатися, де перебуває точка перетину: 1) якщо , [0;1]   , то відрізки 1 1 2 2(( , ), ( , ))x y x y й 1 1 2 2(( , ), ( , ))x y x y    перетинаються; 2) якщо [0;1]  або [0;1]  , то відрізки не перетинаються; 3) якщо ,   ( 2 1 2 1 2 1 2 1( )( ) ( )( ) 0y y x x x x y y         ), то відрізки лежать на одній прямій. Знаходження центру мас багатокутника. Координати центра мас (x,y) багатокутника A, маса якого рівномірно розподілена по вершинах, знаходять за формулою (6) 1 / n A i i x x n   , 1 / n A i i y y n   (6) n – кількість вершин полігона A, (xi,yi) – координата i-ої вершини полігона A. Рис. 1. Блок схема алгоритму пошуку точки перетину відрізків Знаходження площі багатокутника. Якщо координати вершин простого n-кутника рівні (xi , yi ), i = 1, ..., n, то площа багатокутника може бути обчислена за формулою (7). 1 1 1 0 1 ( )( ) 2 n i i i i i S x x y y        (7) де (x0 , y0 ) = (xn , yn ). Дотримується порядок обходу – по годинній стрілці. На вхід функції подається масив точок з номерами від 1 до n, фіктивна точка з нульовим номером додається автоматично. Реалізація модифікованого алгоритму На основі математичного опису алгоритму та запропонованих модифікацій був реалізований модифікований алгоритм лабораторії Лоуренса Берклі. Блок-схема алгоритму представлена на рис. 2-5. Початок Layer[0..n] P,p[1..m] C := центр слою Layer[0] i=1(1)m Layer[0].Pol[i].C := центр мас Layer[0].Pol[i] r[i]=(C.x-Layer[0].Pol[i].C.x)2+ (C.y- Layer[0].Pol[i].C.y)2 Впорядкування елементів Layer[0].Pol[1..m] за зростанням r[1..m] Layer[0].Pol[i].S = площа многокутника Layer[0].Pol[i] Layer[0].Pol[i].Sa=Layer[0].Pol[i].S* p[i]/P Layer[1..n] – масив слоїв, які будуть деформуватися анаморфозою; Layer[0] - слой, який анаморфуеться, складаеться з m полігонів; p[1..m] – масив значень густини для кожного полігона слоя Layer[0] P – середня значення густини Визначається порядок вибору полігонів – в порядку віддалення центра мас полігона від центра слою Layer[0].Pol[i].Sa – площа полігона Layer[0].Pol[i] після анамарфування Eprev:=10 1 * Рис. 2. Блок-схема модифікованого алгоритму np=1(1)m nl=0(1)n CurPol := Layer[0].Pol[np] lnp=1(1)Layer[nl].PolCount Points := Layer[nl].Pol[lnp].Points Count := Layer[nl].Pol[lnp].CountPoints ip=1(1)Count CurPol.C := центр масс полігона CurPol Q[1..nq] := масив точок перетину відрізка (CurPol.C,Points[ip]) з полігоном CurPol. Q[0]=Points[ip] CurPol.Ma := CurPol.Sa/CurPol.S Впорядкування масиву точок Q[1..nq] по збільшенню r2[1..nq] CurPol.Cin := знаходження CurPol.С відносно многокутника CurPol r2[0..nq] = масив квадратів відстаней від точок Q[0..nq] до CurPol.C. Уточнення коефіцієнта деформації Точки дотику не враховуються 2 ** 3 4 5 6 1 Рис. 3. Блок-схема модифікованого алгоритму (продовження) Парність nq CurPol.Cin==true ? CurPol.Cin==true ? R2:=-r2[1]+r2[2]- r2[3]+…- r2[nq]+r2[0] R2:=r2[1]- r2[2]+r2[3]- …+r2[nq] R2:=-r2[1]+r2[2]- r2[3]+…+r2[nq] R2:=r2[1]- r2[2]+r2[3]-…- r2[nq]+r2[0] f2:=(1+(CurPol.Ma-1)*R2/r2[0]) APoints[ip].x:=C.x+(Points[ip].x- C.x)*Sqrt(f2) APoints[ip].y:=C.y+(Points[ip].y- C.y)*Sqrt(f2) непарне Layer[nl].Pol[lnp]:=APoints i=1(1)m Layer[0].Pol[i].S = площа многокутника Layer[0].Pol[i] парне Ні НіТак Так 0 теж парне 7 *** 3 4 5 6 8 2 * Рис. 4. Блок-схема модифікованого алгоритму (продовження) Рис. 5. Блок-схема модифікованого алгоритму (продовження) Етапи побудови площинних анаморфоз. 1) Вибір слою, що буде анаморфуватися; 2) Вибір даних, які будуть відображати густину для кожного полігона слою, що анаморфується; 3) Вибір середньої густини, до якої буде прагнути анаморфоза; 4) Вибір слоїв, які будуть спотворюватися анаморфозою; 5) Анаморфування; 6) Вивід результату. Висновки  Розглянуто та реалізовано ряд підзадач для модифікації алгоритму Лоуренса Берклі.  На основі математичного опису алгоритму та його модифікацій блок-схему модифікованого алгоритму Лоуренса Берклі, яка була реалізовано в середовищі Borland Delphi.  Запропоновано етапи побудови площинних анаморфоз 1. Гусейн-Заде С.М., Тикунов В.С. Анаморфозы: что это такое? М.: Эдиториал УРСС, 1999. – 168 с. 2. Сердюцкая Л.Ф. Математическое моделирование влияния техногенных нагрузок на экологические системы: Автореф. дис. ... докт. техн. наук по спец. 01.05.02 – К.: – 2004. – 42 с. 3. Сердюцкая Л.Ф. Математико-картографическое моделирование в задачах экологии – Геоінформатика. –2005. –№ 2. – C. 59-75. 4. Суворов А.К. Методология картографических анаморфоз http://www- geology.univer.kharkov.ua/tik_rus.htm 5. Сердюцкая Л.Ф. Анаморфозы как инструмент пространственного анализа эколого- географических явлений / Л.Ф. Сердюцкая, Е.А. Бахмацкий, А.В. Яцишин // Геоинформатика. – К., 2008. – № 1. – С. 60–66. 6. Selven S., Merril D., Sacks S., Wong L., Bedell L., Schulman J. Transformations of maps to investigate clusters of disease. Lawrence Berkeley Laboratory, Univ. of California, 1984, 33p. 7. Яцишин А.В. Аналіз числових методів побудови площинних анаморфоз/ А.В. Яцишин // Зб. наук. праць ІПМЕ ім. Г.Є.Пухова НАН України. – К., 2009.

Схожі ресурси