Перетин

Означення. s1 вище s2 в x (позначимо цей факт через s1 >x s2), якщо s1 та s2 порівняльні в x, а точка перетину s1 з вертикаллю x лежить вище точки перетину s2 з вертикаллю x.

s2 >u s4, s2 >v s4, s1 >v s2, s1 >v s4

s3 не порівнювальний з жодним відрізком

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

1. Зустінеться лівий кінець відрізка s. Необхідно додати s до стуктури даних.

2. Зустінеться правий кінець відрізка s. Необхідно видалити s зі стуктури даних.

3. Зустрінеться точка перетину відрізків s1 та s2. Поміняти місціями s1 та s2 в структурі даних.

У структурі даних Т, яка реалізує статус замітаючої прямої, повинні бути реалізовані наступні операції:

1. ВСТАВИТИ(s, T). Вставити відрізок s у повне впорядкування, представлене T.

2. ВИДАЛИТИ(s, T). Видалити відрізок s із T.

3. НАД(s, T). Знайти ім’я відрізку, розташованого безпосередньо над s у T.

4. ПІД(s, T). Знайти ім’я відрізку, розташованого безпосередньо під s у T.

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

Наступні операції будуть використані в алгоритмі перетину відрізків (E – список точок подій):

1. MIN(E). Визначити найменший елемент в T та видалити його.

2. ВСТАВИТИ(x, E). Вставити абсцису x у повне впорядкування E.

3. ЧЛЕН(x, E). Чи є абсциса x членом E.

Перетин відрізків

begin

сортуємо 2*N кінців відрізків лексикографічно по x і y та розташовуємо їх у приоритетну чергу E.

A ; /* робочий параметр процедури, стек */

while (E ) do

begin

p MIN(E);