Розробка алгоритму пошуку перетину відрізків

Завдання моєї курсової роботи - розробка програми яка методом скануючої лінії визначає точки перетину відрізків.

Програма отримує скінченну множину відрізків на площині, вони задаються як координати початку і кінця відрізку. Оскільки таких відрізків дуже багато програма зчитує інформацію з текстового файлу input.txt в якому спочатку стоїть кількість відрізків, а потім координати точок початку і кінця відрізків.

В результаті своєї роботи програма виводить номера відрізків і координати точки першого знайденого перетину, повідомлення що відрізки частково співпадають або повідомлення про відсутність перетинів.

2. Вибір методу розв'язання задачі

Найпростіша дія над відрізками - перевірка перетинаються два відрізки чи ні, виявляється несподівано складним через багато особливих випадків. Існує багато способів визначення перетину.

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

Ще один метод визначення перетину це використання орієнтованої площі. Для того щоб відрізки перетиналися достатньо щоб початок і кінець одного відрізку був по різні сторони іншого, що легко визначити порівнявши знаки орієнтованої площі двох трикутників утворених двома точками першого відрізку і однією з точок другого.

Рис. 2.1 Залежність орієнтованої площі від положення точок

Крайові випадки - належність точки кінцевої точки одного відрізку прямій на якій знаходиться інший відрізок, бо в такому випадку орієнтована площа дорівнює нулю і необхідно перевіряти належність точки відрізку (для цього достатньо порівняти відповідні координати). Ще один крайовий випадок можливий коли відрізок перетинає пряму на якій лежить інший відрізок, але не перетинає сам відрізок. Цей випадок потребує перевірки, наприклад методами описаними далі.

Рис. 2.2 Крайові випадки методу орієнтованої площі

Обидва методи потребують досить складних обчислень, тому існують методи «грубої», або не точної, перевірки, такі як метод обмежуючих прямокутників.

Обмежуючий прямокутник відрізку - це найменший прямокутник який містить відрізок і його сторони паралельні координат.

Рис. 2.3 Обмежуючі прямокутники при перетині відрізків

Визначити такі обмежуючі прямокутники і факт їхнього перетину можна досить швидко. Якщо обмежуючи прямокутники не перетинаються то і відрізки не перетинаються, при їх перетині необхідно виконати додаткову перевірку.

Слід зауважити, що як видно на рисунку 2.2, перетин обмежуючих прямокутників виключає один з крайових випадків двох попередніх методів (відрізки знаходяться на одній прямій, але не перетинаються).

Беручи до уваги швидкодію і складність обробки крайових випадків в даному курсовому проекті найдоцільніше використовувати метод орієнтованої площі в поєднанні з методом обмежуючих прямокутників.

Оскільки необхідно визначити чи перетинаються між собою багато відрізків, а не два, слід обрати метод вибору відрізків, перетин яких слід перевіряти. Найпростіший варіант - метод повної перевірки перевірка перетину кожного відрізку з всіма іншим по черзі, але цей метод дуже повільний.

Більш доцільно використовувати метод скануючої лінії. Сканування на площині корисний інструмент розв'язку задач оброки геометричних об'єктів на площині. Уявна вертикальна лінія сканування пересувається з ліва на право, перетинає об'єкти. В процесі обробки лінії сканування розв'язуються задачі, які відносяться тільки до частин об'єктів зліва від лінії сканування.

При скануванні задача на площині зводиться до серії аналогічних задач в одномірному просторі (на лінії сканування). Це достатньо ефективний підхід, оскільки виникаючі одномірні задачі зазвичай розв'язувати на багато легше.

В даному випадку перевіряються на перетин лише відрізки які знаходяться один біля одного в так званих точках подій (початку чи кінці відрізку або точці перетину), що дозволяє значно прискорити роботи програми при не великій кількості точок перетину, або в задачах де необхідно знайти хоча б один перетин (перевірка простоти многокутника). Але при великій кількості перетинів, наприклад коли всі відрізки перетинаються утворюючи сітку цей метод може працювати навіть повільніше ніж метод повної перевірки.

Рис. 2.4. «Складний» випадок для методу скануючої лінії

3. Алгоритм розв'язку задачі

Алгоритм скануючої лінії складається з двох основних частин.

Перша частина - формування черги точок подій на основі отриманих даних. Абсциси кінцевих точок відрізків додаються до черги, крім того кожна точка помічається, як кінець чи початок відрізку, залежно від положення точок одна до одної. Точка відрізку з мінімальною абсцисою помічається, як початок. З максимальною помічається як кінець. Отримана черга сортується по зростанню абсцис.

Друга частина алгоритму - прохід скануючої лінії по точкам подій. Залежно від типу точки події виконується певна послідовність дій. Якщо це точка початку відрізку то відрізок додається до структури стану скануючої лінії, перевіряється перетин доданого відрізку з відрізком над ним і відрізком під ним, оскільки перетинатися можуть лише відрізки, які знаходяться поруч. Тому в структурі скануючої лінії положення відрізків відсортовано залежно від значення ординати відрізку в цій точці. При обробці точки кінця відрізку перевіряється перетин відрізків над і під поточним і поточний відрізок видаляється з структури стану.

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

Перевірка перетину відрізків відбувається в кілька етапів. Спочатку неточна перевірка методом обмежуючих прямокутників яка виконується швидко і дозволяє відкинути відрізки розташовані далеко один від одного, потім обчислюються векторні добутки і на їх основі визначається перетин, або часткове співпадіння відрізків.

Рис. 3.1 Прохід скануючої лінії по точкам подій

Рис 3.2. Блок-схема роботи алгоритму скануючої лінії

Рис 3.3 - Блок-схема функції пошуку перетину відрізків