Пересечение набора отрезков плоскости

Сентябрь 3, 2022

Главная
Алгебра
Пересечение набора отрезков плоскости

Содержание

2. Приложения Проверка пересечения простых многоугольников Q⊂P Пересечение ребер
3. Приложения Проверка простоты многоугольника Простой Непростой
4. Одномерный случай Даны N интервалов на действительной оси. Необходимо узнать, не перекрываются ли какие-нибудь два из
5. Нижняя оценка Задача единственности элементов Проверка пересечения отрезков Преобразование задач: {xi} {[xi, xi]} Сложность задачи проверки
6. Отношение порядка между отрезками на плоскости Отрезки s1 и s2 сравнимы в абсциссе x, если вертикаль,
7. Отношение порядка между отрезками на плоскости s2 >u s4, s1 >v s2, s2 >v s4, s1
8. Метод плоского заметания Статус заметающей прямой: последовательность отрезков для текущей абсциссы События: Встретился левый конец отрезка
9. Алгоритм Бентли-Оттмана x1 Отрезок s1 добавляется в последовательность Z = (s1)
10. Алгоритм Бентли-Оттмана x2 Отрезок s2 добавляется в последовательность Z = (s1, s2 )
11. Алгоритм Бентли-Оттмана x3 Отрезок s3 добавляется в последовательность Z = (s3, s1, s2)
12. Алгоритм Бентли-Оттмана x4 Отрезок s4 добавляется в последовательность Z = (s3, s1, s2, s4)
13. Алгоритм Бентли-Оттмана x5 Отрезок s4 удаляется из последовательности Z = (s3, s1, s2)
14. Алгоритм Бентли-Оттмана x6 Отрезки s1 и s2 меняются местами в последовательности Z = (s3, s2, s1)
15. Алгоритм Бентли-Оттмана x7 Отрезок s2 удаляется из последовательности Z = (s3, s1)
16. Алгоритм Бентли-Оттмана x8 Отрезок s1 удаляется из последовательности Z = (s3)
17. Алгоритм Бентли-Оттмана x9 Отрезок s3 удаляется из последовательности Z = ()
19. Скачать презентацию

Слайд 2

Приложения
Проверка пересечения простых многоугольников
Q⊂P
Пересечение ребер

Слайд 3

Приложения
Проверка простоты многоугольника
Простой
Непростой

Слайд 4

Одномерный случай
Даны N интервалов на действительной оси. Необходимо узнать, не перекрываются

ли какие-нибудь два из них.

Сложность: O(N logN)

Слайд 5

Нижняя оценка
Задача единственности элементов
Проверка пересечения отрезков
Преобразование задач:
{xi}
{[xi, xi]}
Сложность задачи проверки пересечения

отрезков: Θ(N logN)

Слайд 6

Отношение порядка между отрезками на плоскости
Отрезки s1 и s2 сравнимы в

абсциссе x, если вертикаль, проходящая через x, пересекает оба отрезка.

u

v

s2 и s3 сравнимы в абсциссе u
s1 и s3 сравнимы в абсциссе v
s1 и s3 не сравнимы в абсциссе u
s2 и s3 не сравнимы в абсциссе v

Слайд 7

Отношение порядка между отрезками на плоскости
s2 >u s4, s1 >v s2,

s2 >v s4, s1 >v s4

s3 не сравним ни с каким другим отрезком

Отрезок s1 выше отрезка s2 в х (пишется s1 >x s2), если s1 и s2 сравнимы в х, и точка пересечения s1 с вертикалью x лежит выше точки пересечения s2 с ней же.

Слайд 8

Метод плоского заметания
Статус заметающей прямой: последовательность отрезков для текущей абсциссы
События:
Встретился

левый конец отрезка
Встретился правый конец отрезка
Обнаружена точка пересечения отрезков

Слайд 9

Алгоритм Бентли-Оттмана
x1
Отрезок s1 добавляется в последовательность Z = (s1)

Слайд 10

Алгоритм Бентли-Оттмана
x2
Отрезок s2 добавляется в последовательность Z = (s1, s2 )

Слайд 11

Алгоритм Бентли-Оттмана
x3
Отрезок s3 добавляется в последовательность
Z = (s3, s1, s2)

Слайд 12

Алгоритм Бентли-Оттмана
x4
Отрезок s4 добавляется в последовательность
Z = (s3, s1, s2, s4)

Слайд 13

Алгоритм Бентли-Оттмана
x5
Отрезок s4 удаляется из последовательности
Z = (s3, s1, s2)

Слайд 14

Алгоритм Бентли-Оттмана
x6
Отрезки s1 и s2 меняются местами в последовательности
Z = (s3,

s2, s1)

Слайд 15

Алгоритм Бентли-Оттмана
x7
Отрезок s2 удаляется из последовательности
Z = (s3, s1)

Слайд 16

Алгоритм Бентли-Оттмана
x8
Отрезок s1 удаляется из последовательности
Z = (s3)

Слайд 17

Алгоритм Бентли-Оттмана
x9
Отрезок s3 удаляется из последовательности
Z = ()