Движение прямой

Пусть имеется некая прямая (например, вертикальная), которая заметает плоскость слева направо, останавливаясь в особых точках именуемых «точками событий». Пересечение заметающей прямой с входными данными задачи содержит всю полезную для продолжения поиска информацию. Итак, мы имеем две основные структуры:

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

Статус заметающей прямой – адекватное описание пересечения этой заметающей прямой с заметаемой геометрической структурой, т.е. это пересечение содержит информацию, полезную для данного приложения. Статус заметающей прямой обновляется в каждой точке событий, а подходящая для него структура данных должна выбираться применительно к каждому случаю.

При этом структура данных, реализующая состояние дел у прямой, должна поддерживать следующие операции:

1. INSERT(s) — добавить отрезок s

2. DELETE(s) — удалить отрезок s

3. ABOVE(s) — указать отрезок, располагающийся непосредственно выше s

4. BELOW(s) — указать отрезок, располагающийся непосредственно ниже s

Итог: общий алгоритм

1 сортируем концы отрезков в порядке возрастания абсцисс

(точки с равными абсциссами идут в порядке возрастания

ординат); проверяем, нет ли совпадающих точек среди

концов (если есть — возвращаем TRUE)

2 for для каждой точки p из полученного списка do

3 if (p — левый конец некоторого отрезка s) then

4 INSERT(s)

5 if (ABOVE(s) существует и пересекает s)

или (BELOW(s) существует и пересекает s) then

6 return TRUE

7 if (p — правый конец некоторого отрезка s) then

8 if (определены ABOVE(s) и BELOW(s))

и (они пересекаются) then

9 return TRUE

10 DELETE (s)

11 return FALSE

Время работы этого алгоритма составляет O (n log n), что существенно лучше простейшего алгоритма, основанного на переборе всех пар отрезков. Кроме того, все точки пересечения найти быстрее, чем за O (n ²) не получается, поскольку их может быть O (n ²).