Статус - заметающая прямая
Cтраница 1
 |
Ситуация, возникающая при достижении заметающей прямой левой стороны прямоугольника R. Показаны только активные прямоугольники. [1] |
Статус заметающей прямой задается пересечениями исходных прямоугольников с этой заметающей дрямой; для упрощения формулировок назовем вновь прямоугольники, пересеченные заметающей прямой, активными ( см. разд. [2]
Для проведения вышеописанных действий статус заметающей прямой реализуется на несколько усложненной структуре данных. Первичная структура организована в форме сбалансированного по высоте дерева Т, листья которого содержат концы активных интервалов. В каждом листе Т, кроме нижнего конца активного интервала, хранится указатель на вторичную структуру, являющуюся также сбалансированным по высоте деревом, в котором хранятся все активные прямоугольники в данной компоненте. Вставки ( левых сторон прямоугольников) и удаления ( их правых сторон) выполняются следующим образом. [4]
 |
Пример вычисления отношения как результата обработки вершины а В случае ( а порождается пара ( е, е2. в случае ( Ь порождаются пары (. [ ez, ( е е и ( ез, е4. [5] |
В процессе заметания сверху вниз вершины графа G просматриваются, а статус заметающей прямой корректируется так, как описано выше. Побочным результатом этого заметания является регистрация смежности всех ребер, получаемая при их вставлении или удалении. Отношение смежности, выражаемое в виде упорядоченной пары ребер ( левое, правое) ( рис. 2.25), является транзитивным сведением искомого частичного упорядочения. [6]
 |
Отношение порядка между отрезками. [7] |
Напомним, что в методе плоского заметания используются две главные структуры данных: статус заметающей прямой и список точек событий. [8]
В нашем случае, если плоское заметание проводить, скажем, снизу вверх, то моментальным статусом заметающей прямой будет упорядоченная слева направо последовательность реОер графа, пересекающих ту полосу, где находится заметающая прямая. [9]
В заключение отметим, что имеются две основные структуры данных, связанные с методом заметания плоскости, а именно: ( i) список критических точек, представляющий последовательность абсцисс, упорядоченных в порядке прохождения слева направо, и ( п) статус заметающей прямой, представляющий соответствующее описание необходимой информации относительно геометрических объектов, находящихся на заметающей прямой. Заметим, что эти структуры данных в различных ситуациях могут быть разными, а список критических точек может динамически изменяться в процессе выполнения алгоритма. Так, в рассмотренном выше примере список критических точек является фиксированным упорядоченным списком, а статус заметающей прямой реализован как сбалансированное по высоте дерево. [10]
В заключение отметим, что имеются две основные структуры данных, связанные с методом заметания плоскости, а именно: ( i) список критических точек, представляющий последовательность абсцисс, упорядоченных в порядке прохождения слева направо, и ( ii) статус заметающей прямой, представляющий соответствующее описание необходимой информации относительно геометрических объектов, находящихся на заметающей прямой. Заметим, что эти структуры данных в различных ситуациях могут быть разными, а список критических точек может динамически изменяться в процессе выполнения алгоритма. Так, в рассмотренном выше примере список критических точек является фиксированным упорядоченным списком, а статус заметающей прямой реализован как сбалансированное по высоте дерево. [11]
Адекватное означает, что это пересечение содержит информацию, полезную для данного приложения. Статус заметающей прямой обновляется в каждой точке событий, а подходящая для него структура данных должна выбираться применительно к каждому случаю. [12]
ВСТАВИТЬ и УДАЛИТЬ за время, пропорциональное логарифму его размера. В каждой точке события статус заметающей прямой корректируется и запоминается; ясно, что этот статус есть просто последовательность отрезков внутри вышележащей полосы. С точки зрения затраты ресурсов работа состоит во вставлении и удалении каждого из ребер графа - со стоимостью 0 ( ogN) на одну операцию - и в запоминании статуса; на первое уйдет 0 ( N ogN) времени, поскольку по теореме Эйлера в W-вершинном планарном графе 0 ( N) ребер, а последнее потребует 0 ( N2) памяти, как указано выше. Алгоритм предобработки будет интуитивно понятнее, если считать ребра ориентированными снизу вверх. [13]
Возвращаясь к последнему алгоритму, мы сразу же увидим, что он относится к категории плоского заметания ( см. разд. X [ l: 2N ], а статус заметающей прямой задается деревом отрезков. Подобная реализация допускает непосредственное обобщение этого метода на случаи более чем двух измерений. [14]
Обращая внимание на характерное вертикальное сечение множества прямоугольников, которое является просто последовательностью ординат, заметим, что, поскольку пересеченные отрезки параллельны, последовательность ординат этого сечения всегда будет подпоследовательностью упорядоченной последовательности ординат всех горизонтальных отрезков. Путем предварительной нормализации, при которой множество ординат сортируется, а каждая ордината заменяется ее номером в этом упорядочении, последовательность ординат можно уподобить ряду последовательных целых чисел. Поэтому кажется, что для поддержки статуса заметающей прямой нет необходимости в повторной сортировке общей отсортированной последовательности, поскольку можно воспользоваться более эффективными структурами данных, подобранными именно для этой ситуации. Такие структуры полностью определяются ( по крайней мере скелетно) множеством ординат всех горизонтальных отрезков, а каждое отдельное сечение можно получить, пользуясь скелетной метафорой, путем наделения плотью части скелета. Одним из примеров такой структуры является дерево отрезков, которое уже изучалось и использовалось ранее в данной книге ( см. разд. [15]
Страницы: 1 2