Сәттілік алгоритмі - Fortunes algorithm - Wikipedia

Fortune алгоритмінің анимациясы

Fortune алгоритмі Бұл сыпыру сызығының алгоритмі генерациялау үшін Вороной диаграммасы көмегімен жазықтықтағы нүктелер жиынтығынан O (n журналn) уақыт және O (n) ғарыш.[1][2] Ол бастапқыда жарияланған Стивен Фортун 1986 жылы өзінің мақаласында «Вороной диаграммаларының кең алгоритмі».[3]

Алгоритмді сипаттау

Алгоритм а сыпыру сызығы және а жағажай сызығы, екеуі де алгоритм ілгерілеген сайын жазықтықта қозғалады. Тазалау сызығы - бұл түзу сызық, оны біз тік және жазықтықта солдан оңға қарай қозғаламыз деп болжай аламыз. Алгоритм кезінде кез-келген уақытта тазарту сызығының сол жақтағы кіру нүктелері Вороной диаграммасына қосылады, ал сыпыру сызығының оң жақ нүктелері әлі қарастырылмайды. Жағажай сызығы түзу емес, күрделі, кесек кесінділерінен тұратын тазарту сызығының сол жағындағы қисық параболалар; ол жазықтықтың қалған бөлігінен басқа қандай нүктелер болуы мүмкін екендігіне қарамастан Вороной диаграммасы белгілі болатын жазықтық бөлігін бөледі. Сыпыру сызығынан солға қарай әр нүкте үшін сол нүктеден және сыпыру сызығынан бірдей қашықтықта орналасқан параболаны анықтауға болады; жағажай сызығы осы параболалардың бірігуінің шекарасы. Сыпыру сызығы алға жылжып келе жатқанда, екі парабола қиылысатын жағажай сызығының шыңдары Вороной диаграммасының шеттерін сызып тастайды. Жағажай сызығы әр парабола табанын бастапқыда сыпыру сызығымен өткен нүктелер мен тазарту сызығының жаңа позициясының жартысына дейін сақтай отырып алға жылжиды. Математикалық тұрғыдан, бұл әр парабола тазарту сызығын ретінде қолдану арқылы пайда болады дегенді білдіреді директрица және фокус ретінде енгізу нүктесі.

Алгоритм мәліметтер құрылымы ретінде сақталады a екілік іздеу ағашы жағажай сызығының комбинаторлық құрылымын сипаттайтын және кезек кезегі жағажай сызығының құрылымын өзгертуі мүмкін болашақ оқиғалардың тізімі. Бұл оқиғаларға жағажай сызығына басқа парабола қосу (сыпыру сызығы басқа кіру нүктесін кесіп өткенде) және жағажай сызығынан қисықты алып тастау (сыпыру сызығы параболалары түзілетін үш кіру нүктесі арқылы шеңберге жанасқан кезде). жағажай сызығының дәйекті сегменттері). Әрбір осындай шараға басымдық берілуі мүмкін х- оқиға орын алған кезде сыпыру сызығының координаты. Алгоритмнің өзі келесі кезекті басымдылық кезегінен бірнеше рет алып тастаудан, оқиғаның жағажай сызығындағы өзгерістерін табудан және деректер құрылымын жаңартудан тұрады.

O бар болғандықтан (n) өңделетін оқиғалар (әрқайсысы Вороной диаграммасының кейбір ерекшеліктерімен байланысты) және O (журнал n) оқиғаны өңдеу уақыты (әрқайсысы екілік іздеу ағашының тұрақты санынан және кезек басымдылық операцияларынан тұрады) жалпы уақыт O (n журнал n).

Псевдокод

Псевдокод алгоритмнің сипаттамасы.[4]

рұқсат етіңіз  трансформация болу , қайда  арасындағы эвклидтік қашықтық з және ең жақын сителот Т «жағажай сызығы» болсын  сайтпен қамтылған аймақ болу керек б.let  учаскелер арасындағы шекара сәулесі болуы керек б және q.let  минималды сайттар болыңыз ж-координат, тапсырыс бойынша х- үйлестірубастапқы тік шекара сәулелерін жасаңыз ал олай емес IsEmpty (Q) істеу    б ← DeleteMin (Q)    іс б туралы б - сайт : аймақтың пайда болуын табу  жылы Т құрамында б, жақшаның көмегімен  сол жақта және  оң жақта жаңа шекаралық сәулелер жасаңыз  және  негіздермен б        ауыстыру  бірге  жылы Т        жою Q арасындағы кез келген қиылысу  және         кірістіру Q арасындағы кез келген қиылысу  және         кірістіру Q арасындағы кез келген қиылысу  және     б Вороной шыңы : рұқсат етіңіз б қиылысы болуы керек  сол жақта және  оң жақта  сол жақтың көршісі бол  және рұқсат етіңіз  дұрыс көрші бол  жылы Т        жаңа шекаралық сәуле жасаңыз  егер немесе жасаңыз  егер б жоғарыдан оң q және с, әйтпесе жасаңыз         ауыстыру  жаңадан құрылған  жылы Т        жою Q арасындағы кез келген қиылысу  және         жою Q арасындағы кез келген қиылысу  және         кірістіру Q арасындағы кез келген қиылысу  және         кірістіру Q арасындағы кез келген қиылысу  және         жазба б шыңы ретінде  және  және негізі         шекаралық сегменттерді шығару  және     соңғы әріпаяқталдықалған шекаралық сәулелерді шығарыңыз Т

Салмақталған сайттар мен дискілер

Fortune рефератта сипатталғандай. [1], тазарту сызығының алгоритмінің өзгертілген нұсқасын қосымша салмақталған Вороной диаграммасын құру үшін пайдалануға болады, онда әр торапқа дейінгі қашықтық сайттың салмағымен өтеледі; бұл балама түрде радиусы тораптың салмағына тең алаңдарда орналасқан дискілер жиынтығының Вороной диаграммасы ретінде қарастырылуы мүмкін.

Вороной диаграммаларын құру кезінде Вороной ұяшықтарының аудандарын бақылау үшін салмақты алаңдарды пайдалануға болады treemaps. Аддитивті салмақталған Вороной диаграммасында алаңдар арасындағы биссектриса, гипонбола болып табылады, ал өлшенбеген Вороной диаграммаларынан айырмашылығы қуат диаграммалары ол үшін түзу сызық болатын дискілер.

Әдебиеттер тізімі

  1. ^ а б де Берг, Марк; ван Кревельд, Марк; Мармар; Шварцкопф, Отфрид (2000), Есептеу геометриясы (2-ші редакцияланған), Шпрингер-Верлаг, ISBN  3-540-65620-0 7.2 бөлім: Вороной диаграммасын есептеу: 151–160 бб.
  2. ^ Остин, Дэвид, Вороной диаграммалары және жағажайда күн, Функция бағаны, Американдық математикалық қоғам.
  3. ^ Стивен Фортун. Вороной диаграммаларына арналған алгоритм. Есептеу геометриясы бойынша екінші жыл сайынғы симпозиум материалдары. Йорктаун Хайтс, Нью-Йорк, Америка Құрама Штаттары, 313–322 бб. 1986 ж. ISBN  0-89791-194-6. ACM Digital LibrarySpringerLink
  4. ^ Кени Вонг, Хауси А.Мюллер, Вороной диаграммалары үшін сәттіліктің ұшақ-сыпыру алгоритмін тиімді жүзеге асыру, CiteSeerX  10.1.1.83.5571.

Сыртқы сілтемелер