Bosqich kiritish usullari Iterativ algoritmlar (1.1-1.3) Delon triangulyatsiyasini qurish uchun iterativ algoritmlarning umumiy sxemasi - Dastlabki uchta nuqtada bitta uchburchak yasang
- S to'plamning qolgan barcha nuqtalari bo'ylab aylaning
- Joriy triangulyatsiyaning nuqtasiga eng yaqin uchburchakni toping
- Agar nuqta uchburchagidan tashqarida bo'lsa, u holda eng yaqin qirraga uchburchaklar yasang.
- Agar nuqtasi uchburchak ichida bo'lsa, u holda uchburchakni uchga bo'ling.
- Agar qirrada bo'lsa, u holda qo'shni uchburchaklarni ikkiga bo'ling.
- Agar qo'shnilar uchun Delon sharti buzilgan bo'lsa, u holda qo'shni uchburchaklarni qayta joylashtiring.
Uchburchaklarni qidirishni tezlashtirish variantlari: Uchburchak (setka) keshlash - O(c) Bosqichma-bosqich tanlash usullari To'g'ridan-to'g'ri (bosqichma-bosqich) qurish algoritmlari (3) Oldindan qurilgan uchburchaklarni qayta qurmasdan birdaniga kerakli uchburchaklarni yarating. Delon triangulyatsiyasini to'g'ridan-to'g'ri qurish algoritmlarining umumiy sxemasi Qayta ishlanmagan qirralarning to'plamidan foydalanish qulay. - S nuqtalar to'plami qavariq korpusining q istalgan qirrasini toping.
- q qirrani qayta ishlanmagan stekga qo’shing.
- Qayta ishlanmagan qirralar steki bo'sh bo'lgunga qadar sikl.
- v qirrani stekdan chiqarib tashlang.
- v qirra uchun Delon shartini qanoatlantiradigan p nuqtani toping (Delonning qo'shnisi)
- Agar Delon qo'shnisi p topilsa, u holda
- v qirra bilan p nuqta uchun uchburchak yasang.
- Yangi uchburchakning yangi qirralarini qayta ishlanmagan qirralar stekiga qo'shing.
Delon qo'shnisini qidirishni tezlashtirish variantlari: - k nuqtalarni-D daraxti bo'yicha indeksatsiya qilish - O(log n)
- Nuqtalarni hujayra indeksatsiyasi - O(c)
Ikki o'tishli algoritmlari (4) - Hech bo'lmaganda qavariq triangulyatsiya yasang.
- «Yo’naltirilmagan uchburchaklar" ni qayta qurish (Delon shartini qoniqtirmaydi).
THANK YOU
that you took the time to watch
ALGORITMLARNI LOYIHALASH
Algorithm Design
Do'stlaringiz bilan baham: |
