Fortunes algoritmi - Fortunes algorithm - Wikipedia

Fortune algoritmi animatsiyasi

Fortune algoritmi a supurish chizig'i algoritmi ishlab chiqarish uchun Voronoi diagrammasi yordamida tekislikdagi nuqtalar to'plamidan O (n jurnaln) vaqt va O (n) bo'sh joy.^[1]^[2] Dastlab u tomonidan nashr etilgan Stiven Fortun 1986 yilda o'z maqolasida "Voronoi diagrammalari uchun keng ko'lamli algoritm".^[3]

Algoritm tavsifi

Algoritm ikkalasini ham saqlaydi a supurish chizig'i va a plyaj chizig'i, ikkalasi ham algoritm o'sib borishi bilan tekislik bo'ylab harakatlanadi. Tozalash chizig'i - bu to'g'ri chiziq, biz uni vertikal deb o'ylaymiz va tekislik bo'ylab chapdan o'ngga harakat qilamiz. Algoritm paytida istalgan vaqtda supurish chizig'idan chap kirish nuqtalari Voronoi diagrammasiga kiritiladi, tozalash chizig'ining o'ng nuqtalari hali ko'rib chiqilmaydi. Plyaj chizig'i to'g'ri chiziq emas, balki murakkab, qismli qismlaridan tashkil topgan supurish chizig'ining chap tomonidagi egri chiziq parabolalar; u tekislikning qolgan qismidan tortib, tortish chizig'ida yana qanday nuqtalar bo'lishidan qat'i nazar, Voronoi diagrammasi ma'lum bo'lishi mumkin bo'lgan samolyot qismini ajratadi. Tozalash chizig'idan qolgan har bir nuqta uchun ushbu nuqtadan va supurish chizig'idan teng masofada joylashgan parabola aniqlanishi mumkin; plyaj chizig'i bu parabolalarning birlashishi chegarasidir. Tozalash chizig'i ilgarilayotganda, ikkita parabola kesib o'tadigan plyaj chizig'ining tepalari Voronoi diagrammasining qirralarini kesib tashlaydi. Plyaj chizig'i har bir parabola poydevorini dastlab supurish chizig'i bilan siljigan nuqtalar va supurish chizig'ining yangi holati o'rtasida to'liq yarim yo'lda ushlab turish orqali rivojlanadi. Matematik jihatdan bu shuni anglatadiki, har bir parabola supurish chizig'i sifatida ishlatilib hosil bo'ladi direktrix va kirish nuqtasi fokus sifatida.

Algoritm ma'lumotlar tuzilmalari sifatida saqlanadi a ikkilik qidiruv daraxti plyaj chizig'ining kombinatorial tuzilishini tavsiflovchi va ustuvor navbat plyaj chizig'i tuzilishini o'zgartirishi mumkin bo'lgan kelajakdagi mumkin bo'lgan voqealarni sanab o'tish. Ushbu hodisalar plyaj chizig'iga yana bir parabola qo'shilishi (tozalash chizig'i boshqa kirish nuqtasini kesib o'tganda) va qirg'oqning egri chizig'ini olib tashlashni o'z ichiga oladi (tozalash chizig'i parabolalari hosil bo'lgan uchta kirish nuqtasi orqali aylanaga tegib turganda). plyaj chizig'ining ketma-ket segmentlari). Har bir bunday tadbir birinchi o'ringa qo'yilishi mumkin x- voqea sodir bo'lgan joyda supurish chizig'ining koordinatasi. Keyinchalik algoritmning o'zi navbatdagi hodisani ustuvor navbatdan bir necha marta olib tashlash, hodisa sabab bo'lgan o'zgarishlarni plyaj chizig'ida topish va ma'lumotlar tuzilmalarini yangilashdan iborat.

O (n) ishlov berish uchun voqealar (ularning har biri Voronoi diagrammasining ba'zi bir xususiyatlari bilan bog'liq) va O (log n) hodisani qayta ishlash vaqti (har biri doimiy sonli ikkilik qidirish daraxtidan va navbatdagi navbatdagi operatsiyalardan iborat) umumiy vaqt O (n jurnal n).

Psevdokod

Psevdokod algoritm tavsifi.^[4]

ruxsat bering  ${ displaystyle * (z)}$  o'zgarish bo'lishi  ${ displaystyle * (z) = (z_ {x}, z_ {y} + d (z))}$ , qayerda  ${ displaystyle d (z)}$  orasidagi evklid masofasi  $z$  va eng yaqin joy  $T$  "plyaj chizig'i" bo'lsin  ${ displaystyle R_ {p}}$  sayt qamrab olgan mintaqa bo'ling  $p$ .let  ${ displaystyle C_ {pq}}$  saytlar orasidagi chegara nurlari bo'ling  $p$  va  $q$ .let  ${ displaystyle p_ {1}, p_ {2}, ..., p_ {m}}$  minimal bo'lgan saytlar bo'ling  $y$ - koordinatali, buyurtma qilingan  $x$ - muvofiqlashtirish ${ displaystyle Q S- {p_ {1}, p_ {2}, ..., p_ {m}}} oladi$ dastlabki vertikal chegara nurlarini yarating  ${ displaystyle C_ {p_ {1}, p_ {2}} ^ {0}, C_ {p_ {2}, p_ {3}} ^ {0}, ... C_ {p_ {m-1}, p_ {m}} ^ {0}}$  ${ displaystyle T gets * (R_ {p_ {1}}), C_ {p_ {1}, p_ {2}} ^ {0}, * (R_ {p_ {2}}), C_ {p_ {2 }, p_ {3}} ^ {0}, ..., * (R_ {p_ {m-1}}), C_ {p_ {m-1}, p_ {m}} ^ {0}, * ( R_ {p_ {m}})}$ yo'q esa IsEmpty ( $Q$ ) qil     $p$  ← DeleteMin ( $Q$ )    ish  $p$  ning  $p$  sayt  ${ displaystyle * (V)}$ : mintaqaning paydo bo'lishini toping  ${ displaystyle * (R_ {q})}$  yilda  $T$  o'z ichiga olgan  $p$ , qavs ichida  ${ displaystyle C_ {rq}}$  chapda va  ${ displaystyle C_ {qs}}$  o'ng tomonda yangi chegara nurlarini yarating  ${ displaystyle C_ {pq} ^ {-}}$  va  ${ displaystyle C_ {pq} ^ {+}}$  tagliklari bilan  $p$         almashtirish  ${ displaystyle * (R_ {q})}$  bilan  ${ displaystyle * (R_ {q}), C_ {pq} ^ {-}, * (R_ {p}), C_ {pq} ^ {+}, * (R_ {q})}$  yilda  $T$         dan o'chirish  $Q$  orasidagi har qanday kesishma  ${ displaystyle C_ {rq}}$  va  ${ displaystyle C_ {qs}}$         ichiga joylashtiring  $Q$  orasidagi har qanday kesishma  ${ displaystyle C_ {rq}}$  va  ${ displaystyle C_ {pq} ^ {-}}$         ichiga joylashtiring  $Q$  orasidagi har qanday kesishma  ${ displaystyle C_ {pq} ^ {+}}$  va  ${ displaystyle C_ {qs}}$      $p$  bu Voronoi tepaligi  ${ displaystyle * (V)}$ : ruxsat bering  $p$  ning chorrahasi bo'lishi  ${ displaystyle C_ {qr}}$  chapda va  ${ displaystyle C_ {rs}}$  o'ng tomonda ruxsat bering  ${ displaystyle C_ {uq}}$  chap qo'shnisi bo'ling  ${ displaystyle C_ {qr}}$  va ruxsat bering  ${ displaystyle C_ {sv}}$  to'g'ri qo'shnisi bo'ling  ${ displaystyle C_ {rs}}$  yilda  $T$         yangi chegara nurini yarating  ${ displaystyle C_ {qs} ^ {0}}$  agar  ${ displaystyle q_ {y} = s_ {y}}$ yoki yaratish  ${ displaystyle C_ {qs} ^ {+}}$  agar  $p$  ning yuqorisiga to'g'ri keladi  $q$  va  $s$ , aks holda yarating  ${ displaystyle C_ {qs} ^ {-}}$         almashtirish  ${ displaystyle C_ {qr}, * (R_ {r}), C_ {rs}}$  yangi yaratilgan bilan  ${ displaystyle C_ {qs}}$  yilda  $T$         dan o'chirish  $Q$  orasidagi har qanday kesishma  ${ displaystyle C_ {uq}}$  va  ${ displaystyle C_ {qr}}$         dan o'chirish  $Q$  orasidagi har qanday kesishma  ${ displaystyle C_ {rs}}$  va  ${ displaystyle C_ {sv}}$         ichiga joylashtiring  $Q$  orasidagi har qanday kesishma  ${ displaystyle C_ {uq}}$  va  ${ displaystyle C_ {qs}}$         ichiga joylashtiring  $Q$  orasidagi har qanday kesishma  ${ displaystyle C_ {qs}}$  va  ${ displaystyle C_ {sv}}$         yozuv  $p$  sammiti sifatida  ${ displaystyle C_ {qr}}$  va  ${ displaystyle C_ {rs}}$  va asosi  ${ displaystyle C_ {qs}}$         chegara segmentlarini chiqaring  ${ displaystyle C_ {qr}}$  va  ${ displaystyle C_ {rs}}$     oxirgi harftugadiqolgan chegara nurlarini chiqaring  $T$

O'lchangan saytlar va disklar

Fortune ref-da tasvirlanganidek. ^[1], supurish chizig'i algoritmining o'zgartirilgan versiyasidan qo'shimcha og'irlikdagi Voronoi diagrammasini qurish uchun foydalanish mumkin, bunda har bir saytgacha bo'lgan masofa saytning og'irligi bilan qoplanadi; Bunga teng ravishda, radiusi saytning og'irligiga teng bo'lgan joylarda joylashgan disklar to'plamining Voronoi diagrammasi sifatida qaralishi mumkin.

Voronoi diagrammalarini tuzishda Voronoi katakchalari maydonlarini boshqarish uchun vaznli joylardan foydalanish mumkin treemaps. Qo'shimcha og'irlikdagi Voronoi diagrammasida saytlar orasidagi bissektrisa, umuman vaznsiz Voronoi diagrammalaridan farqli o'laroq, giperboladir. quvvat diagrammasi u to'g'ri chiziq bo'lgan disklar.

Adabiyotlar

^ ^a ^b de Berg, Mark; van Kreveld, Mark; Overmars, Mark; Shvartskopf, Otfrid (2000), Hisoblash geometriyasi (2-tahrirdagi tahr.), Springer-Verlag, ISBN 3-540-65620-0 7.2-bo'lim: Voronoi diagrammasini hisoblash: 151-160 betlar.
^ Ostin, Devid, Voronoi diagrammalari va plyajdagi kun, Xususiyat ustuni, Amerika matematik jamiyati.
^ Stiven Fortun. Voronoi diagrammalari uchun supurgi algoritmi. Hisoblash geometriyasi bo'yicha ikkinchi yillik simpozium materiallari. Yorktown Heights, Nyu-York, Amerika Qo'shma Shtatlari, 313-322 betlar. 1986 yil. ISBN 0-89791-194-6. ACM Raqamli kutubxonasi SpringerLink
^ Kenni Vong, Hausi A. Myuller, Vortunoi diagrammalari uchun boylikning samolyotlarni tozalash algoritmini samarali amalga oshirish, CiteSeerX 10.1.1.83.5571.

Tashqi havolalar

[Mark2000-1] Berg, Mark; van Kreveld, Mark; Overmars, Mark; Shvartskopf, Otfrid (2000), Hisoblash geometriyasi (2-tahrirdagi tahr.), Springer-Verlag, ISBN 3-540-65620-0 7.2-bo'lim: Voronoi diagrammasini hisoblash: 151-160 betlar.

[2] Ostin, Devid, Voronoi diagrammalari va plyajdagi kun, Xususiyat ustuni, Amerika matematik jamiyati.

[3] Stiven Fortun. Voronoi diagrammalari uchun supurgi algoritmi. Hisoblash geometriyasi bo'yicha ikkinchi yillik simpozium materiallari. Yorktown Heights, Nyu-York, Amerika Qo'shma Shtatlari, 313-322 betlar. 1986 yil. ISBN 0-89791-194-6. ACM Raqamli kutubxonasi SpringerLink

[4] Kenni Vong, Hausi A. Myuller, Vortunoi diagrammalari uchun boylikning samolyotlarni tozalash algoritmini samarali amalga oshirish, CiteSeerX 10.1.1.83.5571.

[1]

[2]

[3]

[4]