Darajalar to'plami (ma'lumotlar tuzilmalari) - Level set (data structures)

Yilda Kompyuter fanlari a daraja o'rnatilgan ma'lumotlar tuzilishi diskret tarzda namoyish etish uchun mo'ljallangan namuna olingan dinamik daraja funktsiyalarni o'rnatadi.

Ma'lumotlar tuzilmasining ushbu shaklidan keng foydalanishda samarali tasvir mavjud ko'rsatish. Asosiy usul a ni yaratadi imzolangan masofa maydoni chegaradan uzaygan va bu sohada chegara harakatini hal qilish uchun ishlatilishi mumkin.

Xronologik o'zgarishlar

Kuchli darajani belgilash usuli tufayli Osher va Setian 1988.^[1] Biroq, zich d-o'lchovli orqali to'g'ridan-to'g'ri amalga oshirish qator qadriyatlar, natijada vaqt va saqlashning murakkabligi ${displaystyle O (n ^ {d})}$ , qayerda ${displaystyle n}$ - domenning fazoviy o'lchamlari va ${displaystyle d}$ domenning fazoviy o'lchamlari soni.

Tor guruh

1995 yilda Adalsteinsson va Sethian tomonidan kiritilgan tor diapazonli darajani belgilash usuli,^[2] ko'p hisoblashlarni ingichka faol tasma bilan cheklab qo'ydi voksellar interfeysni darhol o'rab oladi va shu bilan vaqt o'lchamlarini uch o'lchovga kamaytiradi ${displaystyle O (n ^ {2})}$ aksariyat operatsiyalar uchun. Faol voksellar ro'yxatini tiklash uchun tor polosali tuzilmani vaqti-vaqti bilan yangilab turish zarur edi ${displaystyle O (n ^ {3})}$ butun jild bo'yicha voksellarga kirish imkoni bo'lgan operatsiya. Ushbu tor tarmoqli sxemani saqlash murakkabligi hali ham edi ${displaystyle O (n ^ {3}).}$ Tor tarmoqli domen chetidagi differentsial inshootlar eritmani barqarorlashtirish uchun ehtiyot interpolatsiya va domenni o'zgartirish sxemalarini talab qiladi.^[3]

Kam maydon

Bu ${displaystyle O (n ^ {3})}$ vaqtning murakkabligi 1998 yilda Whitaker tomonidan joriy qilingan taxminiy "siyrak maydon" darajalarini belgilash usulida yo'q qilindi.^[4] Kam darajadagi maydonlarni o'rnatish usuli interfeys atrofidagi faol ovozlarni kuzatib borish uchun bog'langan ro'yxatlar to'plamidan foydalanadi. Bu esa, zarur bo'lgan qo'shimcha xarajatlarni talab qilmasdan, faol mintaqani bosqichma-bosqich kengaytirishga imkon beradi. Doimiy ravishda ${displaystyle O (n ^ {2})}$ o'z vaqtida samarali, ${displaystyle O (n ^ {3})}$ saqlash maydoni hali ham kam maydon darajasini belgilash usuli bilan talab qilinadi. Qarang^[5] amalga oshirish tafsilotlari uchun.

Siyrak blokli panjara

Bridson tomonidan 2003 yilda kiritilgan siyrak blokli panjara usuli,^[6] o'lchamning butun hajmini ajratadi ${displaystyle n ^ {3}}$ ning kichik kub bloklariga ${displaystyle m ^ {3}}$ har biri voksellar. Katta o'lchamdagi panjara ${displaystyle (n / m) ^ {3}}$ keyin ko'rsatkichlarni faqat darajadagi to'plamning tor bandini kesib o'tadigan bloklarga saqlaydi. Blokni taqsimlash va taqsimlash yuzasi deformatsiyalarga moslashish uchun tarqalganda yuzaga keladi. Ushbu usul saqlashning suboptimal murakkabligiga ega ${displaystyle Oleft ((nm) 3 + m ^ {3} n ^ {2} ight)}$ , lekin zich tarmoqlarga xos bo'lgan doimiy vaqtni saqlaydi.

Oktri

The oktree 1999 yilda Strain tomonidan kiritilgan darajani belgilash usuli^[7] va Losasso, Gibu va Fedkiw tomonidan takomillashtirilgan,^[8] va yaqinda Min va Gibou tomonidan^[9] barglar tugunlari belgilangan masofa qiymatlarini o'z ichiga olgan ichki kubiklar daraxtidan foydalanadi. Octree darajasining to'plamlari hozirda etarli darajada aniqlik olish uchun interfeys bo'ylab bir xil aniqlikni (ya'ni tor tarmoqli) talab qiladi. Ushbu vakolatxona saqlash nuqtai nazaridan samarali, ${displaystyle O (n ^ {2}),}$ va kirish so'rovlari jihatidan nisbatan samarali, ${displaystyle O (log, n).}$ Oktree ma'lumotlar tuzilmalaridagi daraja usulining afzalligi shundaki, darajani o'rnatish usulidan foydalanadigan odatdagi erkin chegara masalalari bilan bog'liq bo'lgan qisman differentsial tenglamalarni echish mumkin. CASL tadqiqot guruhi^[10] ushbu ish yo'nalishini hisoblash materiallari, hisoblash suyuqligi dinamikasi, elektrokinetika, tasvirga asoslangan jarrohlik va boshqarish vositalarida ishlab chiqdi.

Uzunligi kodlangan

The uzunlikdagi kodlash 2004 yilda kiritilgan (RLE) darajani belgilash usuli,^[11] mintaqalarni tor chiziqdan uzoqda siqish uchun RLE sxemasini qo'llaydi, faqat ularning tor doirasini to'liq aniqlikda saqlashda. Tor diapazonning ketma-ket o'tishi maqbuldir va saqlash samaradorligi oktri darajasiga nisbatan yanada yaxshilanadi. Tezlashtirishni qidirish jadvalining qo'shilishi tezkor ishlashga imkon beradi ${displaystyle O (log r)}$ tasodifiy kirish, bu erda r - kesma bo'yicha ishlaydigan sonlar soni. RLE sxemasini o'lchovli rekursiv usulda qo'llash orqali qo'shimcha samaradorlikka erishiladi, bu usul Nielsen & Musethning o'xshash DT-Grid tomonidan joriy qilingan.^[12]

Hash Table Local Level Set

2012 yilda Brun, Guittet va Gibou tomonidan kiritilgan Hash Table Local Level Set usuli,^[13] Dar diapazonli darajani belgilash uslubida bo'lgani kabi, interfeys atrofida faqat darajadagi to'plam ma'lumotlarini hisoblab chiqadi, shuningdek ma'lumotlarni faqat shu diapazonda saqlaydi. Xash jadvali ma'lumotlar tuzilishi ishlatiladi, bu esa ${displaystyle O (1)}$ ma'lumotlarga kirish. Biroq, mualliflar, ularning usuli amalga oshirish osonroq bo'lsa ham, to'rtburchak daraxtlardan ko'ra yomonroq ishlaydi degan xulosaga kelishdi. Ular buni topishadi

qanday bo'lsa, [...] to'rtburchak ma'lumotlarning tuzilishi darajadagi algoritmlar uchun xash jadval ma'lumotlar tuzilishiga qaraganda ko'proq moslangan ko'rinadi.

Yomon samaradorlikning uchta asosiy sababi keltirilgan:

aniq natijalarga erishish uchun interfeysga yaqin joyda juda katta diapazon talab qilinadi, bu interfeysdan uzoqda joylashgan panjara tugunlarining yo'qligini muvozanatlashtiradi;
spektakllar mahalliy tarmoqning tashqi qirralarida ekstrapolyatsiya protseduralari bilan yomonlashadi va
tarmoqli kengligi vaqt qadamini cheklaydi va usulni sekinlashtiradi.

Nuqtaga asoslangan

Corbett 2005 yilda ^[14] darajani belgilash usulini joriy etdi. Darajalar to'plamidan bir xil namuna olish o'rniga, doimiy darajani belgilash funktsiyasi orqali uyushmagan nuqta namunalari to'plamidan qayta tiklanadi eng kichik kvadratchalar harakatlanmoqda.

Adabiyotlar

^ Osher, S. & Sethian, J. A. 1988. "Egrilikka bog'liq tezlik bilan tarqaladigan jabhalar: Xemilton-Yakobiformulatsiyalar asosida algoritmlar". Hisoblash fizikasi jurnali 79:12–49.
^ Adalsteinsson, D. & Sethian, J. A. 1995. "Interfeyslarni tarqatish uchun tezkor darajalarni belgilash usuli". Hisoblash fizikasi jurnali. 118(2)269–277.
^ Adalsteinsson, D; Sethian, J (1994). "Interfeyslarni targ'ib qilishning tezkor darajasi". Hisoblash fizikasi jurnali. 118 (2): 269. Bibcode:1995JCoPh.118..269A. CiteSeerX 10.1.1.46.1716. doi:10.1006 / jcph.1995.1098.
^ Whitaker, R. T. 1998. "Diapazonli ma'lumotlardan 3 darajali rekonstruksiya qilishga darajadagi yondashuv". Xalqaro kompyuter ko'rishi jurnali. 29(3)203–231.
^ S. Lankton. "Seyrek dala usuli - texnik hisobot." 2009 yil 21 aprel <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/ >
^ Bridson, R. 2003. "Dinamik sirtlarning hisoblash jihatlari (dissertatsiya)". Stenford universiteti, Stenford, Kaliforniya.
^ Strain, J. 1999. "Interfeyslarni harakatlantirish uchun daraxt usullari". Hisoblash fizikasi jurnali. 151(2)616–648.
^ Losasso, F., Gibou, F., va Fedkiw, R. 2004. Oktree ma'lumotlar tuzilishi bilan suv va tutunni simulyatsiya qilish. Grafika bo'yicha ACM operatsiyalari. 23(3)457–462.
^ Min, C. & Gibou, F. 2007. Noto'g'ri moslashuvchan kartezian panjaralarida ikkinchi darajali aniq darajani belgilash usuli. Hisoblash fizikasi jurnali. 225(1)300–321.
^ http://www1.engr.ucsb.edu/~fgibou/Research.html
^ Xyuston, B., Nilsen, M., Beti, S, Nilsson, O. va K. Muset. 2006. "Ierarxik RLE darajasi to'plami: ixcham va ko'p qirrali deformatsiyalanadigan sirtni namoyish etish." Grafika bo'yicha ACM operatsiyalari. 25(1).
^ Nilsen, M. B. va Muset K. 2006. "Dinamik quvurli tarmoq: Ma'lumotlarning samarali tuzilishi va yuqori aniqlik darajalari algoritmlari." Ilmiy hisoblash jurnali. 26(1) 1–39.
^ Brun, E., Guittet, A. & Gibou, F. 2012. "Hash jadvali ma'lumotlar tuzilmasi yordamida mahalliy darajani belgilash usuli." Hisoblash fizikasi jurnali. 231(6)2528-2536.
^ Corbett, R. 2005. "Nuqtaviy darajadagi silsilalar va uyushmagan zarralar sathiga o'tish (tezis)". Britaniya Kolumbiyasi universiteti, Kanada.

[Osher-1] Osher, S. & Sethian, J. A. 1988. "Egrilikka bog'liq tezlik bilan tarqaladigan jabhalar: Xemilton-Yakobiformulatsiyalar asosida algoritmlar". Hisoblash fizikasi jurnali 79:12–49.

[Adalsteinsson-2] Adalsteinsson, D. & Sethian, J. A. 1995. "Interfeyslarni tarqatish uchun tezkor darajalarni belgilash usuli". Hisoblash fizikasi jurnali. 118(2)269–277.

[3] Adalsteinsson, D; Sethian, J (1994). "Interfeyslarni targ'ib qilishning tezkor darajasi". Hisoblash fizikasi jurnali. 118 (2): 269. Bibcode:1995JCoPh.118..269A. CiteSeerX 10.1.1.46.1716. doi:10.1006 / jcph.1995.1098.

[Whitaker-4] Whitaker, R. T. 1998. "Diapazonli ma'lumotlardan 3 darajali rekonstruksiya qilishga darajadagi yondashuv". Xalqaro kompyuter ko'rishi jurnali. 29(3)203–231.

[Lankton-5] S. Lankton. "Seyrek dala usuli - texnik hisobot." 2009 yil 21 aprel <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/ >

[Bridson-6] Bridson, R. 2003. "Dinamik sirtlarning hisoblash jihatlari (dissertatsiya)". Stenford universiteti, Stenford, Kaliforniya.

[Strain-7] Strain, J. 1999. "Interfeyslarni harakatlantirish uchun daraxt usullari". Hisoblash fizikasi jurnali. 151(2)616–648.

[Losasso-8] Losasso, F., Gibou, F., va Fedkiw, R. 2004. Oktree ma'lumotlar tuzilishi bilan suv va tutunni simulyatsiya qilish. Grafika bo'yicha ACM operatsiyalari. 23(3)457–462.

[MinGibou-9] Min, C. & Gibou, F. 2007. Noto'g'ri moslashuvchan kartezian panjaralarida ikkinchi darajali aniq darajani belgilash usuli. Hisoblash fizikasi jurnali. 225(1)300–321.

[CASL-10] ttp://www1.engr.ucsb.edu/~fgibou/Research.html

[Houston2004-11] Xyuston, B., Nilsen, M., Beti, S, Nilsson, O. va K. Muset. 2006. "Ierarxik RLE darajasi to'plami: ixcham va ko'p qirrali deformatsiyalanadigan sirtni namoyish etish." Grafika bo'yicha ACM operatsiyalari. 25(1).

[Nielsen-12] Nilsen, M. B. va Muset K. 2006. "Dinamik quvurli tarmoq: Ma'lumotlarning samarali tuzilishi va yuqori aniqlik darajalari algoritmlari." Ilmiy hisoblash jurnali. 26(1) 1–39.

[BrunGuittetGibou-13] Brun, E., Guittet, A. & Gibou, F. 2012. "Hash jadvali ma'lumotlar tuzilmasi yordamida mahalliy darajani belgilash usuli." Hisoblash fizikasi jurnali. 231(6)2528-2536.

[Corbett-14] Corbett, R. 2005. "Nuqtaviy darajadagi silsilalar va uyushmagan zarralar sathiga o'tish (tezis)". Britaniya Kolumbiyasi universiteti, Kanada.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]