Перетин

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

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

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