Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Последующее изложение будет относиться в основном к двумерным приложениям. Но там, где это уместно, будет дано обобщение на d-мерный случай либо о нем будет упоминаться.
8.3. Общие замечания по алгоритмам статического типа
Уникальная особенность набора изотетичных прямоугольников (или, что то же самое, двух ортогональных наборов параллельных отрезков) состоит в том, что плоскость разбивается на полосы (например, на вертикальные), в каждой из которых задача становится одномерной. (Аналогично пространство Ей можно разбить на (d — 1) -мерные бруски.) В частности, если взять абсциссы вертикальных сторон этих прямоугольников, то внутри каждой полосы, заключенной между смежной парой этих абсцисс, все вертикальные сечения будут одинаковыми и будут состоять из ординат тех горизонтальных сторон, которые пересекают эту полосу. Поэтому такие вертикальные сечения на плоскости разбиваются на классы эквивалентности (каждый из этих классов будет множеством сечений, заключенных между парой последовательных абсцисс вертикальных сторон прямоугольников). Кроме того, будет показано, что сечение, принадлежащее определенной полосе, можно получить в результате небольшой модификации сечений, принадлежащих одной или двум смежным полосам.
8.3. Общие замечания по алгоритмам статического типа
403
Некоторые из интересных с вычислительной точки зрения задач, связанных с множеством прямоугольников (таких, как определение площади их объединения, периметра этого объединения, его контура, регистрации пересечений и т. д.), обладают одним очень полезным свойством. Произвольная вертикальная прямая определяет собой две полуплоскости; решение же исходной задачи, как правило, соотносится весьма просто с решениями аналогичных подзадач для каждой из этих полуплоскостей. Это простое соотношение иногда выступает в виде теоретико-множественного объединения (для отчета о пересечениях), или арифметической суммы (для вычисления площади и периметра), или простого сцепления компонент (для контура). Во всех этих случаях пересечение разделяющей прямой с множеством прямоугольников содержит всю необходимую для комбинации частных решений информацию. Более того, предполагается, что решение, получаемое в результате реализации операций статического типа для, скажем, левой полуплоскости является окончательным (т. е. не изменяемым корректировками, возможными в будущем), так что глобальное решение можно получить последовательным расширением текущего решения вправо. Мы видим, что это типичная ситуация, когда оправданно использование метода плоского заметания, а именно: заметающая прямая параллельна одному из направлений, а движение осуществляется вдоль перпендикулярного ему направления.
Обращая внимание на характерное вертикальное сечение множества прямоугольников, которое является просто последовательностью ординат, заметим, что, поскольку пересеченные отрезки параллельны, последовательность ординат этого сечения всегда будет подпоследовательностью упорядоченной последовательности ординат всех горизонтальных отрезков. Путем предварительной нормализации, при которой множество ординат сортируется, а каждая ордината заменяется ее номером в этом упорядочении, последовательность ординат можно уподобить ряду последовательных целых чисел. Поэтому кажется, что для поддержки статуса заметающей прямой нет необходимости в повторной сортировке общей отсортированной последовательности, поскольку можно воспользоваться более эффективными структурами данных, подобранными именно для этой ситуации. Такие структуры полностью определяются (по крайней мере скелетно) множеством ординат всех горизонтальных отрезков, а каждое отдельное сечение можно получить, пользуясь «скелетной» метафорой, путем «наделения плотью» части скелета. Одним из примеров такой структуры является дерево отрезков, которое уже изучалось и использовалось ранее в данной книге (см. разд. 1.2.3.1); другой пример — де-
404
Гл. 8. Геометрия прямоугольников
рево интервалов [McCreight (1981); Edelsbrunner (1980)], которое будет описано в разд. 8.8.1.
Для удобства напомним, что каждый узел v из дерева отрезков характеризуется интервалом [В [v], Е [v] ] и некоторыми дополнительными параметрами, необходимыми для выполнения особых вычислений. Один из этих параметров C[v] — степень узла — возникает во всех приложениях, поскольку он обозначает число отрезков, отнесенных к узлу v\ другие же параметры имеют смысл только для тех или иных приложений.
Элементарными операциями на дереве отрезков являются вставка и удаление. В частности, если [Ь, е] обозначает интервал, то на узле v определены операции ВСТАВИТЬ (b, е; v) и УДАЛИТЬ (b, е; v). Обычно в следующих разделах процедура ВСТАВИТЬ будет иметь такой вид:
procedure ВСТАВИТЬ(&,е; v)
1. begin if (ft<B[o]) and (?[»]< e) then C[v]:=C[v]+ 1
2. else begin if (b < lB[v] + E[v])/2}) then
ВСТАВИТЬ(Ь,е; ЛСЫВД),
3. if d(B[v] + E[v])/2J < e) then ВСТАВИТЬ(Ь,е; ПСЫЩо])
end;
4. КОРРЕКТИРОВАТЬ(о) (* корректировка особых параметров v*)
end.
