Реферат на тему:
Перетин
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). Визначимо векторний добуток як визначник
матриці
= 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
проекцій.
2. Якщо не можна встановити, що відрізки перетинаються, то перевіряємо,
чи перетинається кожний з цих відрізків з прямою, яка містить інший
відрізок. Відрізок перетинає пряму, якщо його кінці лежать по різні
сторони від неї або якщо один з кінців лежить на прямій. Точки p3 та p4
лежать по різні сторони від прямої p1p2, якщо вектори p1p3 та p1p4 мають
різну орієнтацію відносно вектора p1p2, тобто знаки векторних добутків
(p3 – p1) ??(p2 – p1) та (p4 – p1) ??(p2 – p1) різні.
(p3 – p1) ??(p2 – p1) 0 (p3 – p1)
??(p2 – p1) 0
= -5 – 0 = -5 0 [(A – C) ??(D – C)] * [(B
– C) ??(D – C)] 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);
if (p – лівий кінець) then
begin
s ??відрізок, кінцем якого є p;
ВСТАВИТИ(s, T);
s1 ??НАД(s, T);
s2 ??ПІД(s, T);
if (s1 перетинає s) then A ??(s1, s);
if (s2 перетинає s) then A ??(s, s2);
end;
else if (p – лівий кінець) then
begin
s ??відрізок, кінцем якого є p;
s1 ??НАД(s, T);
s2 ??ПІД(s, T);
if (s1 перетинає s2 справа від p) then A ??(s1, s2);
ВИДАЛИТИ(s, T);
end;
else /* p – точка перетину */
begin
(s1, s2) ??відрізки, що перетинаються в p; /* причому s1 = НАД(s2)
справа від p */
s3 ??НАД(s1, T);
s4 ??ПІД(s2, T);
if (s3 перетинає s2) then A ??(s3, s2);
if (s1 перетинає s4) then A ??(s1, s4);
поміняти місцями s1 та s2 в T;
end;
/* обробити знайдені точки перетину */
while (A ???) do
begin
(s, s’) ??A;
x ??спільна абсциса s та s’;
if ( ЧЛЕН(x, E) = FALSE) then
begin
print (s, s’);
ВСТАВИТИ(x, E);
end;
end;
end;
end.
Теорема. На множині з N відрізків можна знайти K перетинів за час O((N +
K) log N).
Впорядкування ребер планарного графу
Планарний граф G будемо розглядати як орієнтований граф, в якому ребра
направлені зліва направо. За графом G визначимо двоїстий граф G* :
кожній обмеженій грані f відповідає вершина f*. G* містить ще дві
додаткові вершини s* та t*, які знаходяться в необмеженій області.
Кожному ребру e ??G, суміжному з гранями f1 та f2 (грань f1 знаходиться
під гранню f2) поставимо у відповідність ребро e* = (f1*, f2*) в G*.
Якщо грань f1 (відповідно f2) є необмеженою, тоді відповідним ребром в
G* буде (s*, f2*) (відповідно (f1*, t*) ).
Граф G Двоїстий граф G*
Від ребра e до ребра e’ з G існує шлях тоді і тільки тоді, коли існує
шлях з e* до e’* у G*.
P2
P3
P4
P1
P2
P3
P4
P1
P2
P3
P4
P1
P2
P3
P4
P1
P1
P4
P3
P2
C
B
D
A
s1
s3
s2
s4
v
u
Нашли опечатку? Выделите и нажмите CTRL+Enter
