UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваПеретин відрізків (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2089
Скачало281
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Перетин

 

1. Необхідно обчислити перетин чи повідомити про перетин? З’ясування

факту перетину та знаходження точки (точок) перетину є різними задачами,

при чому друга задача є складнішою за першу і в деяких випадках не є

необхідною. Наприклад, не важливо де ми перетнулися зі стінкою, важливим

є факт перетину.

 

2. Шукається перетин прямих чи відрізків? Прямі з різним кутовим

коефіцієнтом обов’язково перетинаються в одній точці, але цього не можна

сказати про відрізки. Задача перетину відрізків є складнішою за задачу

перетину прямих.

 

3. Скільки точок перетину ми очікуємо? При розробці надвеликих

інтегральних схем важливим є факт невеликої кількості перетину відрізків

або щоб цих перетинів взагалі не було.

 

4. Чи можна бачити з точки x точку y? В кімнаті з предметами треба

встановити, чи можна бачити з одної точки іншу (задача видимості). Чи не

перетинає пряма, яка проходить через точки x та y, яку-небудь іншу

пряму?

 

5. Чи є перетинаючі об’єкти опуклими? Існують кращі алгоритми пошуку

перетину, якщо відрізки є сторонами многокутників. Ключовою задачею тоді

є визначення опуклості цих многокутників.

 

6. Чи є множина об’єктів незмінною при пошуку перетину? Якщо людина

рухається в кімнаті, то кількість можливих її зіткнень з предметами у

кімнаті при переході від однієї сцени до іншої є надзвичайно малою.

 

Означення. Дві множини називаються лінійно роздільними тоді і тільки

тоді коли існує така гіперплощина Н, яка їх розділяє.

 

Теорема. Дві множини точок лінійно роздільні тоді і тільки тоді, коли їх

опуклі оболонки не перетинаються.

 

Задача. Накладання інтервалів. Дано N інтервалів на дійсній осі та

необхідно встановити, чи не перетинаються які небудь два з них.

 

Відповідь можна отримати за час O(N2) перевіривши усі пари інтервалів.

Якщо впорядкувати 2N кінцевих точок цих інтервалів та позначити їх як

ліві та праві, то ці інтервали не перекриваються тоді і тільки тоді,

коли їх кінці утворюють чергуючу послідовність: лівий, правий, лівий,

правий, ... .Таку перевірку можна зробити за час O(N * logN).

 

Означення. Векторним добутком на площині p1 ??p2 будемо розуміти площу

паралелограма (з врахуванням знаку), утвореного точками (0,0), p1, p2,

p1 + p2 = (x1 + x2, y1 + y2). Визначимо векторний добуток як визначник

матриці

 

= x1y2 - x2y1 = - p2 ??p1

 

Якщо p1 ??p2 додатне, то найкоротший поворот p2 відносно (0, 0), який

суміщає його з p1, відбувається за годинниковою стрілкою, а якщо

від’ємне – то проти.

 

Задача. На площині дано два відрізки p1p2 та p3p4. Встановити, чи

перетинаються вони.

 

1. Якщо прямокутники, які обмежують відрізки, не перетинаються, то і

відрізки не перетинаються. Обмежуючим прямокутником геометричної фігури

будемо називати найменший із прямокутників зі сторонами, паралельними

вісям координат, що містять дану фігуру. Для відрізка їм буде

прямокутник (p1’, p2’) з лівим нижнім кутом p1’ = (x1’, y1’) та правим

верхнім кутом p2’ = (x2’, y2’), де x1’= min(x1, x2), y1’= min(y1, y2),

x2’= max(x1, x2), y2’= max(y1, y2). Два прямокутники перетинаються

-----> Page:

0 [1] [2]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ