Триангуляція - реферат українською
Означення. Алгоритм називається жадним, якщо на жодному кроці не відміняється те, що вже було зроблено.
Задача. Дано множину S з N точок. Побудувати триангуляцію множини S.
Жадібна триангуляція
Породжується множина K з n * (n - 1) / 2 ребер, що сполучають точки множини S, та впорядковується за зростанням їх довжин. Далі з множини K вибирається ребро з найменшою довжиною. Якщо це ребро не перетинає жодне з ребер, які увійшли до триангуляції, то воно включається до триангуляції. Інакше ребро виключається з подальшого розглядання. Процес закінчиться або коли триангуляція вже побудована (це можна визначити підраховуючи кількість ребер у триангуляції), або коли всі ребра множини K будуть розглянуті.
Сортування ребер по довжині вимагає O(N2 log N) операцій. Потім досліджується O(N2) ребер множини K на перевірку перетинання з ребрами триангуляції. Така перевірка для кожного ребра множини K може вимагати час O(N). Отже повний час обробки дорівнює O(N3).
Підхід Джільберта прийняття рішення.
Припустимо, що поточним ребром, обраним з множини K, є p1pi. Розглянемо множину ребер, які сполучають p1 з іншими точками множини S та позначимо його ЗІРКА(p1). Проміні зірки впорядковані у порядку обхода навколо точки p1 та ділять повний кут на N - 1 кутових інтервалів (секторів). Якщо деяке ребро pkpj включене до триангуляції, то воно проходить через декілька послідовних секторів зірки з центром p1. Оскільки ребра, включені до триангуляції, не перетинаються, то ребра у кожному секторі можна вважати відсортованими. Припустимо що точка pi попала до сектора pjp1pk із ЗІРКА(p1). Для вирішення питання про занесення ребра p1pi до триангуляції слід визначити, чи перетинає воно ребра триангуляції вказаного сектора (навіть не всі ребра сектора, а лише найближче до p1 ребро). Задача перетину звелася до часткового випадку задачі визначення положення точки на площині. В кожному секторі, що визначається ЗІРКА(p1), необхідно зберігати найближче до p1 (опорне) ребро.
Теорема. Триангуляція множини з N точок жадним алгоритмом може бути побудована за час O(N2 log N) з використанням пам’яті O(N2).
Задача. Дано множину S з N точок. Побудувати триангуляцію множини S.
Жадібна триангуляція
Породжується множина K з n * (n - 1) / 2 ребер, що сполучають точки множини S, та впорядковується за зростанням їх довжин. Далі з множини K вибирається ребро з найменшою довжиною. Якщо це ребро не перетинає жодне з ребер, які увійшли до триангуляції, то воно включається до триангуляції. Інакше ребро виключається з подальшого розглядання. Процес закінчиться або коли триангуляція вже побудована (це можна визначити підраховуючи кількість ребер у триангуляції), або коли всі ребра множини K будуть розглянуті.
Сортування ребер по довжині вимагає O(N2 log N) операцій. Потім досліджується O(N2) ребер множини K на перевірку перетинання з ребрами триангуляції. Така перевірка для кожного ребра множини K може вимагати час O(N). Отже повний час обробки дорівнює O(N3).
Підхід Джільберта прийняття рішення.
Припустимо, що поточним ребром, обраним з множини K, є p1pi. Розглянемо множину ребер, які сполучають p1 з іншими точками множини S та позначимо його ЗІРКА(p1). Проміні зірки впорядковані у порядку обхода навколо точки p1 та ділять повний кут на N - 1 кутових інтервалів (секторів). Якщо деяке ребро pkpj включене до триангуляції, то воно проходить через декілька послідовних секторів зірки з центром p1. Оскільки ребра, включені до триангуляції, не перетинаються, то ребра у кожному секторі можна вважати відсортованими. Припустимо що точка pi попала до сектора pjp1pk із ЗІРКА(p1). Для вирішення питання про занесення ребра p1pi до триангуляції слід визначити, чи перетинає воно ребра триангуляції вказаного сектора (навіть не всі ребра сектора, а лише найближче до p1 ребро). Задача перетину звелася до часткового випадку задачі визначення положення точки на площині. В кожному секторі, що визначається ЗІРКА(p1), необхідно зберігати найближче до p1 (опорне) ребро.
Теорема. Триангуляція множини з N точок жадним алгоритмом може бути побудована за час O(N2 log N) з використанням пам’яті O(N2).
Скачати реферат Триангуляція
Схожі українські реферати
|
1. Реферат: Трансформація образу агасфера у сучасній художній літературі Біблію справедливо називають супутницею людства. Протягом двох тисячоліть вона є предметом вивчення і невичерпним джерелом натхнення для митців усього світу. Звернення письменників ХХ ст. до біблійних тем – явище не випадкове і не кон’юнктурне. Во... 2. Реферат: Трансформація образу Фауста у творчості Й.В. Гете та О.С. Пушкіна. Трансформацiя образу Фауста у творчостi Й.В.Гете та О.С.Пушкiна Творчий дух Фауста лине до нас iз загадкових i химерних вiкiв Середньовiччя i Вiдродження, коли людина пройнялася вiрою у свою всемогутнiсть, озброївшись силами таємничої науки а... 3. Реферат: Трансформація телевізійного сюжету в газетний текст Трансформація телевізійного сюжету в газетний текст Слово "трансформація" походить від латинського transformare - перетворювати. "Зміна, перетворення виду, форми, істотних властивостей і т. ін. чого-небудь" [10, 233]. Розглянемо трансформацію я... 4. Реферат: Трансформація технологій у рослинництві У XX столітті можна виділити три етапи удосконалення технологій вирощування сільгоспкультур. У 30–50-х рр., завдяки механізації процесів вирощування зернових, вдалося повністю позбутися важкої ручної праці, особливо під час збирання врожаю. Для бага... 5. Реферат: Трансформація форм власності і перехід до соціальної Трансформація форм власності і перехід до соціальної Розділ 1 Економічний зміст власності 1.1 Поняття та форми власності Процес виробництва є не що інше, як привласнення людиною предметів і сил природи в межах певної суспільної форми. Катего... 6. Реферат: Тренінг контролю агресивності Вирази емоцій в нашому суспільстві не схвалюється. Це починається з дитинства, коли батьки не дозволяють дітям голосно говорити, не сперечатись, не кричати. Коли ж агресивні комунікації постійно пригнічуються і блокуються людина з часом набирає тенд... 7. Реферат: Тренінги розвитку здібностей. інноваційного підходу до вирішення проблем раціоналізації трудової діяльності У процесі творчості з позиції психології велике значення має уява. За визначенням Т. Рібо, "усі речі, які ми застосовуємо, не виключаючи найпростіших і звичайних, становлять... кристалізовану уяву" . Творча фантазія має знайти вихід у конкретних вчин... 8. Реферат: Три варіанти організації аналітичного обліку продукції підприємства Три варіанти організації аналітичного обліку продукції підприємства У сучасних умовах можливі три варіанти організації аналітичного обліку продукції підприємства: Перший варіант. Окремі види або групи однорідної продукції обліковуються за фактичною... 9. Реферат: Три загальновійськові статути СТАТУТ ВНУТРІШНЬОЇ СЛУЖБИ ЗБРОЙНИХ СИЛ УКРАЇНИ 6. Внутрішня служба здійснюється з метою підтримання у військовій частині порядку та військової дисципліни, належного морально-психологічного стану, які забезпечують постійну бойову готовність та якіс... 10. Реферат: Три поділи Польщі 230 років тому, 5 червня 1772-го, повноважні представники Пруссії, Австрії та Росії підписали в Петербурзі договір про поділ польських земель. Згідно з цією угодою, Пруссія забрала Помор’я, Куяви та частину Великопольщі, Австрія – Малопольщу і Галичи...
11. Реферат: Триангуляція
Означення. Алгоритм називається жадним, якщо на жодному кроці не відміняється те, що вже було зроблено. Задача. Дано множину S з N точок. Побудувати триангуляцію множини S. Жадібна триангуляція Породжується множина K з n * (n - 1) / 2 ребер,... 12. Реферат: Тривалість життя людини Тривалість життя людини Аналізуючи середню тривалість життя людини можна бачити, що ця величина непостійна. Чим раніший етап розвитку людини, тим коротшою є середня тривалість життя. Судячи з кістяків, близько 40% неандертальців вимирали у віці... 13. Реферат: Тривалість життя тваринних і послинних організмів. Періоди індивідуального розвитку тваринних і послинних організмів (онтогенез) Періоди індивідуального розвитку тваринних і рослинних організмів (онтогенез) Ембріологія — наука, що вивчає зародковий розвиток організмів, — доводить, що процес утворення полових кліток (гаметогенез) подібний у всіх багатоклітинних: усі вон... 14. Реферат: Тривалість життя тваринних і рослинних організмів. Періоди індивідуального розвитку тваринних і рослинних організмів (онтогенез) Ембріологія — наука, що вивчає зародковий розвиток організмів, — доводить, що процес утворення полових кліток (гаметогенез) подібний у всіх багатоклітинних: усі вони починають розвиток з однієї клітки — зиготи. У всіх хребетні зародки схожі між собою... 15. Реферат: Тригонометричні вирази та їх перетворення Відношення сторін в трикутнику Розглянемо спочатку прямокутний трикутник АВС. — прямий. Рис. 1 В такому трикутнику вводять наступні співвідношення , . (1) (рис. 2). Рис. 2 позначимо радіус описаного кола. Справджується формул... 16. Реферат: Тригонометричні функції 1. Стисненням заготовки на прокатному стані називають величину де і — товщини заготовки до і після прокатування. Доведіть, що -, де d — діаметр вала і — кут захвату. Вказівка. З прямокутного трикутника АОВ: ОВ = 0,5d cos , = 2 . 2. Схили д... 17. Реферат: Трипільська культура Енеоліт - мідно-кам`яна епоха , що була перехідною від кам`яного віку до епохи бронзи . Це був якісно новий період розвитку продуктивних сил та виробничих відносин первісного суспільства ,час дальшого вдосконалення відтворюючих форм господарства – з... 18. Реферат: Тритикале у весняній ланці зеленого конвеєра господарств ???????????их насінин для тритикале і жита. Об‘єктами досліджень були: сорти тритикале — АДМ 3/5, АДМ 9, АД 52, Поліський 4, Поліський 7, Мально, Ягуар, АД 15, АД 44, АД 45, АДП 2 та озима пшениця сорту Мирич і озиме жито Саратівське 6. Результати пр... 19. Реферат: Трифазний струм, трифазне електричне коло.З'єднання зіркою. З'єднання трикутником Трифазний струм, трифазне електричне коло 3 метою заощадження електричної енергії під час її транспортування та ефективності її використання у техніці об'єднують низку кіл з незалежними джерелами живлення в одну систему. Широко використовуються тр... 20. Реферат: Трійця (Клечальна неділя) - за народним календарем відзначається на п’ятдесятий день після Великодня. Як святкували та що їли Трійця (Тройця, Троїця, Святого Духа) своїм місцем у календарі повністю завдячує Великодню. Свято має також інші назви — П’ятдесятниця (П’ятидесятниця), бо його відзначають на п’ятдесятий день після Світлого Воскресіння Христового. На ці ж дні пр... 21. Реферат: Тромбоцитопатії: патогенез, клініко-параклінічні критерії діагностики, диференційної діагностики. сучасні підходи до лікування (лекція) Лекція Тромбоцитопатії: патогенез, клініко-параклінічні критерії діагностики, диференційної діагностики. сучасні підходи до лікування Мета: удосконалити знання лікарів-інтернів про сучасні погляди на механізми розвитку, клініко-параклінічні кри... |
|