Перетин

Перетин

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 проекцій.