Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Теперь посмотрим, что же происходит на самом деле при сортировке для выявления наложений. Мотивом для этого ис-
7.2. Плоские приложения
343
следования служит отсутствие естественного полного упорядочения отрезков на плоскости, поэтому на обобщение, основанное только на сортировке, не приходится рассчитывать. Однако если мы сможем понять существенные черты одномерного алгоритма, то нам удастся обобщить его и на плоский случай.
Два интервала перекрываются тогда и только тогда, когда они содержат хотя бы одну общую точку. Каждая точка на действительной оси связана с множеством, состоящим из накрывающих ее интервалов. Это соответствие определяет функцию С: R->-{0, 1}^, отображающую действительные числа на подмножества множества {1, N}. Значение функции С может меняться только на множестве из 2N концевых точек заданных интервалов. Если мощность {С{х)} превышает мощность последнего множества, то интервалы перекрываются. Чтобы обнаружить это, отсортируем концы интервалов и создадим простейшую структуру данных, состоящую всего лишь из одного целого числа, т. е. числа интервалов, накрывающих текущую абсциссу. Просматривая концы отрезков слева направо, ВСТАВЛЯЕМ интервал в эту структуру данных в тот момент, когда встречен его левый конец, и УДАЛЯЕМ его в момент встречи правого конца. Всякая попытка ВСТАВИТЬ в структуру, в которой уже хранится число один, свидетельствует о наложении; в противном случае наложений нет. Поскольку обработка каждой концевой точки при таком подходе занимает лишь константное время, то процесс проверки (после сортировки) требует не более чем линейного времени. 1
При двух измерениях необходимо определить иное отношение порядка и использовать более совершенную структуру данных'). Рассмотрим пару непересекающихся отрезков si и s2 на плоскости. Будем считать, что si и s2 сравнимы в абсциссе х, если существует такая вертикаль, проходящая через х, которая пересекает оба отрезка. Введем отношение выше в х следующим образом: s\ выше s2 в х (пишется si >xs2), если s\ и s2 сравнимы в х, а точка пересечения s\ с вертикалью х лежит выше точки пересечения s2 с ней же2). На рис. 7.15 показаны следующие отношения между отрезками s,, s2, s3 и s4:
S2>US4. $\>vS2, S2>vSli, S,>0S4.
Отрезок s3 не сравним ни с каким другим отрезком.
') Для простоты изложения предположим, что нет вертикальных отрезков и что никакие три отрезка не пересекаются в одной точке. Если нарушить любое из этих условий, то разрабатываемые алгоритмы станут длиннее в деталях, но не в асимптотической оценке времени работы.
2) Это отношение порядка и алгоритм, следующий из него, были предложены Дэном Хоуи. Доказательство корректности этого алгоритма было дано М. Шеймвсом. Оба результата были опубликованы в работе [Shamos, Ноеу (1976)].
344
Гл. 7. Пересечения
Заметим, что отношение >х задает полное упорядочение, которое изменяется по мере того, как вертикаль скользит слева направо. Отрезки входят в это упорядочение и покидают его, но оно всегда остается полным. Упорядочение может изменяться только в трех случаях:
1. Встретился левый конец отрезка s. В этом случае s надо добавить к структуре данных.
2. Встретился правый конец отрезка s. В этом случае s надо удалить из структуры данных, поскольку он больше не сравним с оставшимися отрезками.
3. Обнаружена точка пересечения отрезков s\ и s2. Тогда S\ и s2 меняются местами в структуре данных.
и и
Рис. 7.15. Отношение порядка между отрезками.
Заметим, что необходимое условие пересечения двух отрезков s\ и s2 состоит в том, что существует такая абсцисса х, в которой si и s2 смежны в упорядочении ~>х. Отсюда немедленно следует, что последовательность пересечений множества отрезков с вертикалью в х (т. е. отношение >*) содержит всю необходимую информацию для поиска пересечений отрезков и что естественным методом для решения задач этого класса является «плоское заметание» (см. разд. 1.2.2, где дана общая формулировка этого алгоритмического метода). Напомним, что в методе плоского заметания используются две главные структуры данных: статус заметающей прямой и список точек событий.
Как указано выше, статус заметающей прямой является описанием отношения >Л-; значит, он представляет собой последовательность элементов (отрезков). Если вспомнить ранее описанный механизм, в котором отношение >* изменяется на конечном множестве абсцисс при плоском заметании, то станет очевидно, что в структуре данных S?', реализующей статус заметающей прямой, должны быть предусмотрены следующие операции:
7.2. Плоские приложения 345
a. ВСТАВИТЬ (s, S). Вставить отрезок s в полное упорядочение, представленное в S?.
b. УДАЛИТЬ (s, 2?). Удалить отрезок s из S.
c. НАД(«,3?). Найти имя отрезка, расположенного непосредственно над s в SB'S.. ПОД(х,&). Найти имя отрезка, расположенного непосредственно под s в &.
Подобная структура данных известна как словарь (см. разд. 1.2.3), а все вышеописанные операции можно реализовать
х, хг х3 Xi, х5
