Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Перетин

Перетин

Назва:
Перетин
Тип:
Реферат
Мова:
Українська
Розмiр:
20,09 KB
Завантажень:
30
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
Перетин

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). Визначимо векторний добуток як визначник матриці

p1 p2 = = 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). Два прямокутники перетинаються (мають спільні точки) тоді і тільки тоді, коли

x2’ x3’ and x4’ x1’ and y2’ y3’ and y4’ y1’

Перші дві умови відповідають перетину x - проекцій, другі два – y проекцій.

2. Якщо не можна встановити, що відрізки перетинаються, то перевіряємо, чи перетинається кожний з цих відрізків з прямою, яка містить інший відрізок. Відрізок перетинає пряму, якщо його кінці лежать по різні сторони від неї або якщо один з кінців лежить на прямій. Точки p3 та p4 лежать по різні сторони від прямої p1p2, якщо вектори p1p3 та p1p4 мають різну орієнтацію відносно вектора p1p2, тобто знаки векторних добутків (p3 - p1) (p2 - p1) та (p4 - p1) (p2 - p1) різні.

(p3 - p1) (p2 - p1) < 0, (p4 - p1) (p2 - p1) > 0 (p3 - p1) (p2 - p1) < 0, (p4 - p1) (p2 - p1) < 0

(p3 - p1) (p2 - p1) < 0, (p4 - p1) (p2 - p1) = 0 (p3 - p1) (p2 - p1) = 0, (p4 - p1) (p2 - p1) = 0

Кожний відрізок перетинає пряму, яка містить інший відрізок, але не перетинаються прямокутники, які обмежують ці відрізки.

Теорема. Відрізки p1p2 та p3p4 перетинаються тоді ітільки тоді, коли:

1. Перетинаються прямокутники, які їх обмежують;

2. [(p3 - p1) (p2 - p1)] * [(p4 - p1) (p2 - p1)] 0;

3. [(p1 - p3) (p4 - p3)] * [(p2 - p3) (p4 - p3)] 0.

Приклад

A(1, 2)

B(7, 5)

C(2, 5)

D(4, 4)

Чи перетинаються відрізки

AB та CD?

Прямокутник відрізка AB: (1, 2) - (7, 5).

Прямокутник відрізка CD: (2, 4) - (5, 4).

Прямокутники перетинаються.

C - A = (1, 3); D - A = (3, 2); B - A = (6, 3). A - C = (-1, -3); B - C = (5, 0); D - C = (2, -1).

(C - A) (B - A) = = 3 - 18 = -15 < 0 (A - C) (D - C) = = 1 + 6 = 7 > 0

(D - A) (B - A) = = 9 - 12 = -3 < 0 (B - C) (D - C) = = -5 - 0 = -5 < 0

[(C - A) (B - A)] * [(D - A) (B - A)] > 0 [(A - C) (D - C)] * [(B - C) (D - C)] < 0

Відповідь: відрізки не перетинаються, оскільки порушується третя умова теореми.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок