Перетин, Детальна інформація

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).

= 1 + 6 = 7 > 0

= -5 - 0 = -5 < 0

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

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

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

Означення. Відрізки s1 та s2 є порівнювальними в абсцисі x, якщо існує така вертикаль, що проходить через x, яка перетинає обидва відрізки.

Означення. 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.