Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
СКТ - 5,6сем.doc
Скачиваний:
6
Добавлен:
01.05.2025
Размер:
9 Мб
Скачать
☆

Задачи локализации точки. Метод луча

Рассмотрим алгоритм для решения проблемы принадлежности точки произвольному полигону. Предположим, что необходимо определить принадлежность точки а полигону р.

Для этого из некоторой удаленной точки проведем прямую линию в точку а. На этом пути может встретиться 0 или несколько пересечений границы полигона: при первом пересечении входим внутрь полигона, при втором выходим и т.д. Т. об. каждое нечетное пересечение обозначает попадание внутрь полигона р, а каждое четное – выход из него (см. рис.).

П остроение алгоритма на основе этой идеи базируется на двух особенностях:

  1. для решения задачи подходит любой луч, начинающийся в анализируемой точке а. Поэтому, для простоты выберем правый горизонтальный луч, начинающийся в точке а и направленный вправо параллельно полуоси +Х.

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

Выделим три типа ребер полигона:

  1. касательное ребро, если оно содержит точку а (b).

  2. пересекающее ребро, если оно не горизонтально и луч пересекает его в некоторой точке, отличающейся от его нижней конечной точки (с).

  3. безразличное ребро, если оно не касательное и не пересекающее (d).

При прохождении луча через пересекающие ребра бит четности меняется и результат выдается по достижению касательного ребра или завершению обхода границы полигона.

Но при прохождении луча через вершины полигона возникают особые ситуации.

Будем считать, что ребро направленно таким образом, что внутренняя часть полигона располагается всегда справа от него.

Если луч проходит полностью через ребро полигона, то вообразив бесконечно малый поворот, можно увидеть, что если обе вершины ребра принадлежат лучу, то это ребро можно отбросить; если же ровно одна вершина лежит на луче, то пересечение будет учтено, когда эта вершина с большей ординатой (y).

Локализация точки на планарном подразбиении. Метод полос

Опр. Граф G=(V,E) (где V – множество вершин, E – множество ребер) называется планарным, если его можно уложить на плоскости без самопересечений. Прямолинейная укладка ребер планарного графа определяет разбиение плоскости, называемое планарным подразбиением. Пусть v – число вершин, e – число ребер и f – число граней (включая единственную бесконечную грань) такого подразбиения. Эти три параметра связаны формулой Эйлера:

v-e+f=2

Планарный граф всегда может быть уложен на плоскость так, что его ребра перейдут в прямолинейные отрезки. Графы, уложенные подобным образом называются плоскими прямолинейными графами (ППЛГ).

В основе локализации точки в подобной ситуации лежит дихотомия.

Пусть задан ППЛГ G. Проведем горизонтальные прямые через каждую его вершину (рис.1). Они разделяют плоскость на N+1 горизонтальных полос. Если провести сортировку этих полос по координате у как часть предобработки, то появится возможность найти ту полосу, в которой лежит точка z за время O(logN).

Рассмотрим пересечение одной из полос с графом G. Оно состоит из отрезков ребер графа G. Поскольку G есть плоская укладка планарного графа, то его ребра пересекаются между собой только в вершинах, а так как каждая вершина лежит на границе полосы, то отрезки ребер внутри полос не пересекаются.

Поэтому данные отрезки можно упорядочить слева направо и использовать двоичный поиск для определения той трапеции, в которую попала точка z, потратив на это O(log N) времени. Отсюда получаем оценку времени запроса для худшего случая, равную O(logN).

При простом подходе нужно сортировать все отрезки внутри каждой полосы. Кроме того, поскольку каждая полоса может содержать O(N) таких отрезков, то необходимы затраты: O(N2logN) – для времени и O(N2) – для памяти. Затраты памяти сократить нельзя, поскольку существуют такие ППЛГ, которые требуют квадратичную память (рис.2). Но затраты на предобработку можно сократить, воспользовавшись идеей метода заметающей прямой.

Заметим, что если ребро проходит через несколько полос, то эти полосы следуют одна за другой. Т.е. нет необходимости повторять сортировку внутри каждой полосы, а можно при переходе от одной полосы к другой исключать из списка предыдущей полосы ребра, заканчивающиеся в полосе и добавлять ребра, начинающиеся в этой полосе. Будем условно считать ребра ориентированными снизу вверх. Заметающая прямая горизонтальна, движется снизу вверх. Списком точек событий являются вершины графа, упорядоченные по ординате. А статусом является последовательность ребер данной полосы. Если статус хранить в виде сбалансированного по высоте дерева, то операции “вставить” и “удалить” будут занимать время logN.